정답 후보를 절반씩 버려 로그 시간에 찾는 방법
데이터가 정렬되어 있거나 ‘이 값 이하는 가능, 그 이상은 불가능’ 같은 단조성이 있을 때 탐색 범위를 매번 절반으로 줄입니다. 수백만 개 후보도 약 20번 비교로 좁힐 수 있습니다.
코드를 생각하지 말고, 아래 상황이 어떤 순서로 움직이는지만 따라가 보세요.
1부터 100 중 정답이 73일 때 50보다 큰지 묻고, 다음에는 75보다 작은지 물으며 범위를 절반씩 줄입니다.
M 근처를 펼쳤는데 찾는 단어가 S로 시작하면 앞쪽 절반은 더 볼 필요가 없습니다.
코딩 테스트의 장난감 예제를 넘어, 실제 시스템에서 같은 원리가 어디에 숨어 있는지 연결해 보세요.
타임스탬프 배열에서 특정 시점의 첫 로그를 찾습니다.
제한 시간 안에 처리 가능한 최대 배치 크기를 찾습니다.
정확도 조건을 만족하는 최소 threshold를 찾습니다.
정렬된 빈 시간 목록에서 원하는 시각 이후의 첫 예약 가능 시간을 찾습니다.
문제가 처음 발생한 릴리스 버전을 절반씩 좁혀 찾아냅니다.
왼쪽과 오른쪽 경계의 중간값을 검사한 뒤, 정답이 있을 수 없는 절반을 버립니다. 경계의 의미를 끝까지 동일하게 유지하는 것이 핵심이며 시간 복잡도는 O(log n)입니다.
| 연산 | Python 표현 | 시간 |
|---|---|---|
| 정확한 값 찾기 | binary search | O(log n) |
| 첫 위치 | bisect_left | O(log n) |
| 삽입 위치 찾기 | bisect | O(log n) |
| 리스트 중간 삽입 | insort | O(n) |
mid = 2, 값 5 → 목표가 더 큼왼쪽 경계를 3으로 이동값 7 → 목표 발견인덱스 3 반환left <= right와 left < right를 섞으면 무한 루프나 누락이 생깁니다.설명을 닫고 먼저 풀어본 뒤, 막히는 지점에서 어떤 연산이 필요한지 다시 떠올려 보세요.
Easy 연습 1 / 7
Python으로 풀기Easy 연습 2 / 7
Python으로 풀기Easy 연습 3 / 7
Python으로 풀기Easy 연습 4 / 7
Python으로 풀기Easy 연습 5 / 7
Python으로 풀기Easy 연습 6 / 7
Python으로 풀기Easy 연습 7 / 7
Python으로 풀기Medium 연습 1 / 3
Python으로 풀기Medium 연습 2 / 3
Python으로 풀기Medium 연습 3 / 3
Python으로 풀기