문제 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 설계 - 이분탐색 - 백준 [2805. 나무자르기] 문제와 연결하니 좀 더 쉽게 접근할 수 있었다. N = int(input()) arr = list(map(int, input().split())) M = int(input()) start, end = 1, max(arr) switch = 1 while switch: mid = (start + end) // 2 sumV = 0 for i..
문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 설계 - 처음에는 내음대로 풀었으나 시간초과 - 투포인터 학습 후 접근 - start와 end 설정이 중요하다. N, M = map(int, input().split()) arr = list(map(int, input().split())) arr.sort() start = 1 end = max(arr) while start mid: # 높이보다 큰 나무..
문제 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 설계 - 처음에는 2중 for문을 이용하여 확인했으나 시간초과로 실패 - sort를 활용하여 접두어를 i와 i+1만 검사하면 된다. T = int(input()) for tc in range(T): result = 'YES' n = int(input()) arr = [input() for _ in range(n)] arr.sort() for i in range(n-1)..
문제 https://www.acmicpc.net/problem/14606 14606번: 피자 (Small) 예제1의 입력이 1이므로, 게임 시작부터 갑이 분리할 수 있는 피자탑이 없습니다. 따라서 갑이 얻는 즐거움은 0입니다. 예제2의 정답 3은 다음과 같은 과정을 통해 얻어집니다. 먼저 놀이를 시작 www.acmicpc.net 설계 - 재귀, 피보나치 응용 n = int(input()) result = 0 def cal(level): global result if level == n: return result += level cal(level+1) cal(0) print(result)
문제 https://www.acmicpc.net/problem/14494 14494번: 다이나믹이 뭐예요? (1, 1)에서 (n, m)에 도달하는 경우의 수를 구하여라. 단, 경우의 수가 엄청 커질 수 있으므로 경우의 수를 1,000,000,007(=109+7)로 나눈 나머지를 출력한다. www.acmicpc.net 설계 - DP 문제 - 피보나치와 동일한 개념 적용, 2중 for문 - 직접 그림을 그려 규칙을 찾아냈다. x, y = map(int, input().split()) arr = [[1]*(y+1) for _ in range(x+1)] for i in range(2, x+1): for j in range(2, y+1): arr[i][j] = arr[i-1][j] + arr[i][j-1] + a..
문제 https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 설계 - bfs while문 안에서 pop(0)을 해야하는데 pop()으로 잘못 적어 오류를 찾는데 꽤나 고생했다. q에 append 하기 전에 visit 체크를 하면 시간이 덜 걸린다고 하니 참고하자. def bfs(x, y, cnt): global maxV q = [] q.append((x, y, 0)) visit = [[0] * b for _ in range(a)] visit[x][y] =..
문제 https://www.acmicpc.net/problem/19949 19949번: 영재의 시험 컴퓨터공학과 학생인 영재는 이번 학기에 알고리즘 수업을 수강한다. 평소에 자신의 실력을 맹신한 영재는 시험 전날까지 공부를 하지 않았다. 당연하게도 문제를 하나도 풀지 못하였지만 다행 www.acmicpc.net 설계 - DFS, 백트래킹 - level(수준): 10 / branch: 5 백트래킹을 적용했으나 파이썬으로 제출했을 경우 시간초과에 걸렸다. pypy 로 제출하여 통과했으나 메모리나 시간이 많이 소요되어 시간복잡도를 좀 더 줄여야 하는 코드라고 생각한다. def dfs(level): global cnt if level == 10: score = 0 for i in range(10): # 10문제..
문제 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 설계 - 완전탐색 + BFS 처음 문제를 읽은 후 안전한 영역 개수가 잘 이해되지 않아 문제 이해에만 오랜 시간이 소요되었다. 코드가 조금 지저분해보이는데 조금 더 간결하게 쓰는 코드를 써보도록 노력해야겠다. import copy N = int(input()) arr = [list(map(int, input().split())) for _ in range(N)] visit = [[0]*N for _..
이름이 없는 동물의 아이디 https://programmers.co.kr/learn/courses/30/lessons/59039 코딩테스트 연습 - 이름이 없는 동물의 아이디 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr SELECT ANIMAL_ID FROM ANIMAL_INS WHERE NAME IS NULL ORDER BY ANIMAL_ID; 이름이 있는 동물의 아이디 https://programmers.co.kr/learn/co..
고양이와 개는 몇 마리 있을까 https://programmers.co.kr/learn/courses/30/lessons/59040 코딩테스트 연습 - 고양이와 개는 몇 마리 있을까 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr SELECT ANIMAL_TYPE, COUNT(*) AS count FROM ANIMAL_INS GROUP BY ANIMAL_TYPE ORDER BY ANIMAL_TYPE; 동명 동물 수 찾기 https://p..
