백준[1981] 배열에서 이동 (Python3)
완전 탐색 배열을 모두 순회하는데 O(100 * 100) 이 필요하다. 최대 - 최소의 경우, 차이가 1이라 할 때, 차이가 1이 되는 최대, 최소의 쌍은 (1, 2), (2, 3), (3, 4), ... (199, 200) 식이다. 차이가 최대 200까지 발생하니, 쌍을 구하는 것에 대한 시간 복잡도는 (199 + 198 + 197 + ... + 0) = 약 20,000 정도 된다. 총 시간 복잡도는 O(100^2) * O(199 + 198 + ... + 0) = 2억으로 시간 초과가 발생한다. 완전 탐색 최적화 배열을 일부만 탐색할 수는 없으니, 쌍을 구하는 과정에서 최적화를 수행해야 한다. 하지만, 어떤 최대, 최소의 차이 A를 구하기 위해선, 이를 만족하는 모든 경우를 확인해야만 한다. 따라서, ..
백준[1561] 놀이 기구 (Python3)
완전 탐색 매 분마다 놀이 기구들의 남은 시간을 확인한다. 이 경우 N = 2,000,000,000, M = 1, M[0] = 30 인 경우 60,000,000,000번의 연산이 필요해 시간 초과가 발생한다. 완전 탐색 최적화 연산 횟수를 줄이기 위해선 탐색하는 빈도를 줄이는 방향으로 갔다. 관찰 결과 아이들이 M 명 이하로 남았을 때를 보면 된다 생각했다. 그중에서도 모든 아이들이 놀이 기구를 타기 직전의 상황을 보면 더 빠르게 문제를 해결할 수 있다고 생각했다. 이분 탐색 임의의 시간 X에 놀이 기구 A는 a 번을 타고, B는 b 번을 타는 식으로 해서 Z는 z 번을 탄다. 이 a + b + c + ... + z를 더한 뒤 아이들의 전체 수인 N과 대소를 비교한다. 시간 X를 정할 때, 최악의 경우 ..
백준[21278] 호석이 두 마리 치킨 (Python3, bfs)
분석하고 보니 플로이드 문제였지만, 시간 복잡도를 계산해 보니 시간이 충분해서 bfs로 풀었다. bfs로 풀 수 있다 생각한 이유 치킨집의 쌍을 구하면 (1, 100), (2, 100) ... (99, 100)로 약 5,000개의 쌍이 생긴다. 간선이 생길 수 있는 개수도 최대가 약 5000개다. 치킨집으로 정한 두 인덱스를 기준으로 bfs 탐색을 진행하면 최악의 경우에 각각 전체를 탐색해야 하고 이러면 10,000번의 탐색이 진행된다. 각 쌍이 10,000번의 탐색을 수행한다 하면 5,000 * 10,000 = 50,000,000 번의 탐색 즉, 약 0.5초 만에 결과를 낼 수 있단 것을 발견해, bfs로 풀이했다. 코드 더보기 from collections import deque N, M = map(..
