Binary Search

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/43238 문제 해설 Idea Binary Search answer에 대한 이진탐색 수행 (1 <= answer <= max(times)*n) 매 탐색마다 answer 시간 동안 심사관들이 심사할 수 있는 사람의 수를 계산 심사한 사람의 수가 n명 이상일 경우 최대 범위를 조정하고 재탐색 심사한 사람의 수가 n명 미만일 경우 최소 범위를 조정하고 재탐색 n명 이상의 사람을 심사할 수 있는 가장 작은 answer를 반환 Time Complexity Binary Search: O(M Log N^N) = 6,000,000 Data Size n: 1 <= int <= 1,000,000,000 times: int(1,000,000,000) * 100,000 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 def solution(n, times): answer = 0 start, end = 1, max(times)*n while start <= end: mid = (start+end)//2 passed = 0 for time in times: passed += mid // time if passed >= n: break if passed >= n: answer = mid end = mid-1 elif passed < n: start = mid+1 return answer

문제 링크 https://www.acmicpc.net/problem/2805 개요 이분 탐색으로 해결할 수 있는 문제이다. Python3을 사용하면 시간초과가 발생하므로 PyPy3를 사용한다. 문제 조건 일정 높이에 대해 모든 나무를 잘랐을 때, 조건을 만족하는 절단기의 최대 높이(H)를 구하는 문제이다. 잘린 나무의 길이의 합은 상근이가 필요로 하는 나무의 길이(M)보다 크거나 같아야 한다. 문제 해설 나무의 수(N)의 최댓값이 1,000,000이므로 모든 범위에 대해 반복하는 순차 탐색을 이용할 경우 시간초과가 발생한다. 시간 복잡도가 O(log n)인 이분 탐색을 이용하면 시간 복잡도가 O(n)인 순차 탐색을 쓰는 것보다 훨씬 빠르다....