백준[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(..
백준[16496] 큰 수 만들기 (Python3)
생각보다 쉬운 문제 파이썬이 아닌 언어로 풀었으면 조금 돌아가야 했을 것이다. 시도한 방법 1 입력된 수들을 가장 긴 자릿수만큼 자신의 일의자리 수를 더해준다. 예를 들어 입력이 432, 9999 가 들어온다면, 4322, 9999로 맞춰준다. 그다음 내림차순 정렬을 해, 원본 수를 이어붙인다. 반례로 98, 9888889가 들어오면 98이 먼저 와야 하는데 뒤로 가야 하는 문제가 발생했다. 다른 사람 코드 보는 과정에서 알았는데, 끝자리 수만 추가해주는게 아니라 해당 수를 적당히 이어붙이고, 앞에 10개만 가져와서 비교하면 됐었다. (10개만 가져오는 이유는, 수의 범위가 10억 이하이기 떄문) 시도한 방법 2 두 수 A, B가 있을 때, AB와 BA의 값을 비교한 다음 위치를 바꾼다. N의 범위가 매..
