Algorithm

문제 링크 https://www.acmicpc.net/problem/7569 문제 해설 Idea BFS 7569번 토마토 문제에서 하나의 차원이 추가된 버전입니다. 차원이 늘어난만큼 N의 최대 길이가 감소했기 때문에 여전히 BFS로 해결할 수 있습니다. 익은 토마토의 기준에서 전체 상자를 BFS로 완전탐색하면서 안익은 토마토까지의 최소 거리를 기록합니다. 최소 거리의 최댓값이 곧 토마토들이 모두 익는 최소 일수이며, 모든 토마토가 다 익었을 경우에 최소 일수를 출력하고, 그렇지 않은 경우엔 -1을 출력합니다. Time Complexity O(N^3) = 1,000,000 Data Size M,N: 2 <= int <= 100 H: 1 <= int <= 100 t in [1,0,-1] 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 from collections import deque import sys input = sys....

문제 링크 https://www.acmicpc.net/problem/7576 문제 해설 Idea BFS를 활용한 시뮬레이션을 통해 모든 토마토가 익을 떄까지 걸리는 최소 기간을 계산 초기엔 안익은 토마토의 기준에서 매번 익은 토마토까지의 최단거리를 탐색하여, O(N^4)의 시간 복잡도로 시간 초과가 발생 이후 익은 토마토의 기준에서 시뮬레이션을 단 한번만 수행하여 각각의 칸에 도달하는데 걸리는 거리값을 갱신 모두 익지 못하는 상황에 대해 1안에선 에러를 발생시켜 처리했고, 2안에선 종료 코드를 실행해 처리 Time Complexity O(N^2) = 1,000,000 Data Size M,N: 2 <= int <= 1,000 t in [1,0,-1] 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 from collections import deque import sys input = sys....

문제 링크 https://www.acmicpc.net/problem/18870 문제 해설 Idea Sort 집합을 통해 압축한 unique한 좌표 목록을 정렬시키고, 정렬된 리스트 내에서 좌표와 인덱스를 딕셔너리로 맵핑 Time Complexity O(N Log N) = 13,000,000 Data Size N: 1 <= int <= 1,000,000 X: -10^9 <= int <= 10^9 해설 코드 1 2 3 4 N = int(input()) X = list(map(int, input().split())) xtoi = {x:i for i,x in enumerate(sorted(set(X)))} print(' '.join(map(lambda x: str(xtoi[x]), X)))

문제 링크 https://www.acmicpc.net/problem/1931 문제 해설 Idea Sliding Window 슬라이딩 윈도우의 전형적인 문제로, 끝 시간을 기준으로 시간을 정렬해서 겹치지 않는 수를 계산 Time Complexity O(N) = 100,000 Data Size N: 1 <= int <= 100,000 t1,t2: 0 <= int <= 2^31-1 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 import sys input = sys.stdin.readline N = int(input()) times = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: [x[1],x[0]]) count, end_time = 0, 0 for t1,t2 in times: if t1 >= end_time: count += 1 end_time = t2 print(count)

문제 링크 https://www.acmicpc.net/problem/15686 문제 해설 Idea Combinations 최대 집의 개수가 100, 최대 치킨집의 개수가 13으로 매우 적은 경우의 수를 가지고 있기 때문에, 모든 조합에 대한 완전탐색을 통해 최소 거리를 계산 초기에는 집에 대한 치킨 거리가 작은 치킨집을 우선적으로 선발해서, 폐업하지 않은 치킨집에 대한 치킨 거리의 최소 합을 계산했지만 틀림 이후 combinations 모듈을 활용한 완전탐색을 통해 통과 Time Complexity O(N * nCr) ~ 100,000 Data Size N: 2 <= int <= 50 M: 1 <= int <= 13 cell in (0, 1, 2) count(house): 1 <= int < 2N count(chicken): M <= int <= 13 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 from itertools import combinations import sys input = sys....