이진 탐색이 하는 일
정렬된 배열에서 값을 찾을 때 처음부터 하나씩 보면 길이 만큼 걸린다. 이진 탐색(binary search)은 찾는 범위의 가운데 값을 하나 보고, 답이 그보다 왼쪽에 있는지 오른쪽에 있는지 판단해 범위를 절반으로 줄인다. 범위가 매번 절반이 되므로 번 안에 끝나고, time complexity 는 이다.
이 방법이 배열에만 쓰이는 것은 아니다. 범위를 절반으로 버릴 수 있는 근거는 “가운데 값 하나를 보면 답이 어느 쪽에 있는지 알 수 있다” 는 성질뿐이다. 이 성질은 배열이 정렬돼 있을 때도 생기지만, 답의 후보가 되는 수 자체에 대해 생기기도 한다. 다음 절의 답 이진 탐색이 그런 경우다.
답 이진 탐색: 조건을 만족하는 최솟값 찾기
“하루에 바나나를 몇 개씩 먹어야 기한 안에 다 먹는가” 처럼 조건을 만족하는 값 중 가장 작은 값 을 묻는 문제가 있다. 답을 직접 계산하기는 어렵지만, 값 하나를 정해 주면 그 값이 조건을 만족하는지는 쉽게 확인할 수 있는 경우가 많다.
이럴 때 답이 될 수 있는 수의 범위를 정해 두고, 그 범위에서 이진 탐색을 한다. 배열의 원소 대신 답의 후보를 탐색한다고 해서 답 이진 탐색, 또는 parametric search 라고 부른다.
판정 결과가 한 번만 바뀌어야 한다
값 가 조건을 만족하는지 참·거짓으로 돌려주는 함수를 판정 함수 라고 하자. 답 이진 탐색이 성립하려면 판정 결과가 를 키우는 동안 거짓에서 참으로 한 번만 바뀌어야 한다.
x : 1 2 3 4 5 6 7
ok(x) : F F F T T T T
↑
답 = 처음으로 T 가 되는 x
바나나를 하루에 4 개씩 먹어서 기한을 맞출 수 있으면 5 개씩 먹어도 맞출 수 있다. 이렇게 “어떤 값이 되면 그보다 큰 값도 모두 된다” 는 성질이 있으면 판정 결과가 위 그림처럼 한 번만 바뀐다. 가운데 하나를 판정해서 T 가 나오면 답은 그 자리이거나 왼쪽에 있고, F 가 나오면 답은 오른쪽에 있다. 그래서 범위를 절반씩 버릴 수 있다.
틀
lo, hi = 답이 될 수 있는 가장 작은 값, 답이 될 수 있는 가장 큰 값
while lo < hi:
mid = (lo + hi) // 2
if ok(mid):
hi = mid # mid 도 답일 수 있으므로 남긴다
else:
lo = mid + 1 # mid 는 답이 아니므로 버린다
return lohi 는 판정이 반드시 참인 값으로 잡는다. 그래야 범위 안에 답이 적어도 하나 있다.
끝나면 lo 가 답인 이유
이 틀은 반복 내내 답이 [lo, hi] 안에 있다 는 상태를 지킨다. 처음에는 lo 와 hi 를 답이 될 수 있는 범위의 양 끝으로 잡았으므로 성립한다. 반복 한 번이 이 상태를 깨지 않는지 두 경우로 나눠 본다.
ok(mid)가 참이면, 답은mid이거나 그보다 작다. 그래서hi = mid로 오른쪽을 버린다.mid자체가 답일 수 있으므로mid - 1이 아니라mid까지 남긴다.ok(mid)가 거짓이면,mid와 그보다 작은 값은 모두 답이 아니다. 그래서lo = mid + 1로mid까지 버린다.
mid 는 답의 후보로 따로 저장해 두는 값이 아니라, 범위를 어느 쪽으로 줄일지 정하려고 찔러 보는 값이다. 답은 언제나 [lo, hi] 안에 있으므로, 반복이 끝나 lo == hi 가 되면 범위에 남은 값 하나가 답이다. 그래서 ans = mid 같은 변수 없이 lo 를 그대로 반환한다.
mid 를 내림해야 반복이 끝난다
lo < hi 이면 mid = (lo + hi) // 2 는 lo 이상, hi 미만이다. 그래서 hi = mid 는 hi 를 적어도 1 줄이고, lo = mid + 1 은 lo 를 적어도 1 늘린다. 어느 쪽이든 범위가 줄어들므로 반복이 반드시 끝난다.
mid 를 올림((lo + hi + 1) // 2)으로 잡으면 lo = 4, hi = 5 에서 mid = 5 가 되고, 판정이 참이면 hi = mid = 5 로 범위가 그대로라 반복이 끝나지 않는다. 올림은 “조건을 만족하는 최댓값” 을 찾느라 lo = mid 로 갱신하는 반대쪽 틀에서 쓴다. 다음 절처럼 최댓값을 찾는 문제를 최솟값 찾기로 바꾸면 이 반대쪽 틀이 필요 없다.
조건을 만족하는 최댓값: 첫 거짓을 찾고 한 칸 앞으로
“정렬된 배열에서 이하인 값 중 마지막” 처럼 조건을 만족하는 값 중 가장 큰 값 을 묻는 문제도 있다. 이때는 판정 결과가 앞의 최솟값 문제와 반대로, 를 키우는 동안 참에서 거짓으로 한 번 바뀐다.
x : 1 2 3 4 5 6 7
ok(x) : T T T T F F F
↑ ↑
마지막 참 = 4 5 = 첫 거짓
마지막 참과 첫 거짓은 항상 붙어 있다. 그래서 마지막 참을 직접 찾는 대신, “거짓이 되는 가장 작은 ” 를 앞의 최솟값 틀로 찾고 한 칸 앞으로 물러난다. 최솟값 틀의 판정 자리에 not ok(mid) 를 넣은 것과 같다.
lo, hi = 답이 될 수 있는 가장 작은 값, 답이 될 수 있는 가장 큰 값 + 1
while lo < hi:
mid = (lo + hi) // 2
if ok(mid):
lo = mid + 1 # mid 는 참이므로 첫 거짓이 아니다
else:
hi = mid # mid 가 첫 거짓일 수 있으므로 남긴다
return lo - 1 # 첫 거짓의 한 칸 앞이 마지막 참hi를 가장 큰 후보보다 하나 크게 잡는 이유는, 모든 후보가 참이면 범위 안에 첫 거짓이 없기 때문이다. 범위 끝 바로 뒤를 “거짓인 자리” 로 쳐 두면 최솟값 틀의 “hi는 판정이 반드시 맞는 값” 이라는 조건이 지켜진다.hi자리에서ok를 부르는 일은 없다.mid는 항상hi보다 작기 때문이다.- 끝났을 때
lo - 1이 가장 작은 후보보다 작으면 조건을 만족하는 값이 하나도 없다는 뜻이다. mid는 최솟값 틀과 같이 내림이므로 반복이 반드시 끝난다.
Python 의 bisect.bisect_right(a, t) 는 정렬된 배열 a 에서 ” 보다 큰 첫 위치” 를 돌려준다. 즉 ” 이하인가” 의 첫 거짓이고, 여기서 1 을 빼면 이하인 마지막 위치다. 이 방법을 그대로 쓰는 문제가 Time Based Key-Value Store 다. 따라가 보기와 마지막 참을 직접 찾으면 생기는 문제도 그 노트에 있다.
예제: Koko Eating Bananas
LeetCode 875. Koko Eating Bananas. 바나나 더미의 크기 목록 piles 와 기한 h 시간이 주어진다. 한 시간에 바나나를 최대 k 개 먹을 수 있고, 한 시간에는 더미 하나만 먹는다. 더미에 k 개보다 적게 남았으면 그 더미를 다 먹고 남은 시간은 쉰다. h 시간 안에 다 먹을 수 있는 가장 작은 k 를 구한다.
판정 함수
속도 k 로 더미 하나를 다 먹는 데 걸리는 시간은 더미 크기를 k 로 나눠 올림한 값이다. 전체 시간은 이것을 모든 더미에 대해 더한 것이다.
| 기호 | 뜻 |
|---|---|
| 번째 더미의 바나나 개수 | |
| 더미의 개수 | |
| 한 시간에 먹는 바나나 개수 (구할 값) | |
| 속도 로 모든 더미를 먹는 데 걸리는 시간 |
판정 함수는 이다. 를 키우면 더미마다 걸리는 시간이 같거나 줄어드므로 도 같거나 줄어든다. 그래서 판정 결과가 거짓에서 참으로 한 번만 바뀐다.
범위는 lo = 1, hi = max(piles) 다. k = max(piles) 이면 모든 더미를 한 시간씩에 먹으므로 이고, 문제는 를 보장하므로 hi 는 판정이 반드시 참이다. k 를 이보다 키워도 더미당 한 시간보다 줄지 않으므로 더 볼 필요가 없다.
class Solution:
def minEatingSpeed(self, piles: list[int], h: int) -> int:
def ok(k):
return sum((p + k - 1) // k for p in piles) <= h
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
if ok(mid):
hi = mid
else:
lo = mid + 1
return lo(p + k - 1) // k 는 p / k 를 올림한 정수다. 부동소수점 math.ceil(p / k) 를 쓰지 않아도 된다.
따라가 보기
piles = [3, 6, 7, 11], h = 8 이면 답은 4 다.
lo | hi | mid | 판정 | 갱신 | |
|---|---|---|---|---|---|
| 1 | 11 | 6 | 1 + 1 + 2 + 2 = 6 | 참 | hi = 6 |
| 1 | 6 | 3 | 1 + 2 + 3 + 4 = 10 | 거짓 | lo = 4 |
| 4 | 6 | 5 | 1 + 2 + 2 + 3 = 8 | 참 | hi = 5 |
| 4 | 5 | 4 | 1 + 2 + 2 + 3 = 8 | 참 | hi = 4 |
lo = hi = 4 가 되어 반복이 끝난다. 마지막 줄에서 mid = 4 가 참이었지만 그 값을 따로 저장하지 않았다. hi 가 4 로 줄면서 범위 [4, 4] 에 남았기 때문이다.
판정 한 번에 더미 개를 보고, 판정은 번 한다. 전체는 다.
예제: Capacity To Ship Packages Within D Days
LeetCode 1011. Capacity To Ship Packages Within D Days. 화물 무게 목록 weights 를 주어진 순서대로 배에 싣는다. 배는 하루에 한 번 출발하고, 하루에 싣는 무게의 합은 배의 적재량을 넘을 수 없다. 화물 순서는 바꿀 수 없다. days 일 안에 모두 보낼 수 있는 가장 작은 적재량을 구한다.
판정 함수
적재량 cap 이 정해지면, 화물을 앞에서부터 실을 수 있는 만큼 싣고 다음 화물이 넘치면 다음 날로 넘기는 것이 가장 적은 날수를 쓴다. 오늘 더 실을 수 있는 화물을 내일로 미뤄서 날수가 줄어드는 일은 없기 때문이다.
def ok(cap):
need, load = 1, 0 # 필요한 날수, 오늘 실은 무게
for w in weights:
if load + w > cap: # 오늘은 더 못 싣는다
need += 1
load = 0
load += w
return need <= days범위는 lo = max(weights), hi = sum(weights) 다. hi 는 모든 화물을 하루에 싣는 적재량이라 판정이 반드시 참이다.
lo = max(weights) 는 판정 함수가 기대는 전제다
lo 를 875 처럼 1 로 잡아도 될 것 같지만, 그러면 틀린 답이 나온다. weights = [1, 2, 3, 1, 1], days = 4 의 답은 3 인데, lo = 1 로 시작하면 2 를 돌려준다.
원인은 판정 함수가 “어떤 화물이든 빈 배에는 실린다” 고 가정한다는 데 있다. 넘칠 때 다음 날로 넘기기만 할 뿐, 넘긴 화물이 빈 배에 들어가는지는 확인하지 않는다. cap = 2 로 위 예를 따라가면 다음과 같다.
1일차: [1] 다음 화물 2 를 더하면 3 > 2 → 다음 날로
2일차: [2] 다음 화물 3 을 더하면 5 > 2 → 다음 날로
3일차: [3] 무게 3 이 적재량 2 를 넘지만 확인하지 않는다
4일차: [1, 1]
4일이 나와서 ok(2) 가 참이 된다. 실제로는 무게 3 인 화물을 실을 수 없으므로 거짓이어야 한다.
lo = max(weights) 로 시작하면 판정 함수는 cap ≥ max(weights) 인 값으로만 불린다. 이 범위에서는 모든 화물이 빈 배에 들어가므로 판정 함수의 가정이 항상 맞는다. 즉 lo 는 탐색 범위를 줄이려는 최적화가 아니라 판정 함수가 올바르게 동작하기 위한 조건이다. 판정 함수 안에 if w > cap: return False 를 넣어도 같은 문제를 막을 수 있다.
875 에서 lo = 1 이 괜찮았던 이유도 같은 기준으로 설명된다. 올림 나눗셈은 어떤 k ≥ 1 에 대해서도 더미를 다 먹는 시간을 올바르게 계산하므로, 판정 함수가 기대는 전제가 따로 없다.
코드와 따라가 보기
class Solution:
def shipWithinDays(self, weights: list[int], days: int) -> int:
def ok(cap):
need, load = 1, 0
for w in weights:
if load + w > cap:
need += 1
load = 0
load += w
return need <= days
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = (lo + hi) // 2
if ok(mid):
hi = mid
else:
lo = mid + 1
return loweights = [1, 2, ..., 10], days = 5 이면 답은 15 다.
lo | hi | mid | 판정 | 갱신 |
|---|---|---|---|---|
| 10 | 55 | 32 | 참 | hi = 32 |
| 10 | 32 | 21 | 참 | hi = 21 |
| 10 | 21 | 15 | 참 | hi = 15 |
| 10 | 15 | 12 | 거짓 | lo = 13 |
| 13 | 15 | 14 | 거짓 | lo = 15 |
적재량 15 이면 [1, 2, 3, 4, 5], [6, 7], [8], [9], [10] 으로 5일이 걸린다. 14 이면 [1, 2, 3, 4] 부터 시작해 6일이 걸린다.
판정 한 번에 화물 개를 보고, 판정은 번 정도 한다. 전체는 다.
예제: Find Minimum in Rotated Sorted Array
LeetCode 153. 오름차순으로 정렬된 배열을 어느 지점에서 잘라 앞뒤를 바꿔 붙였다. 중복 값은 없다. 최솟값을 에 찾는다.
원래 : [0, 1, 2, 4, 5, 6, 7]
회전 후 : [4, 5, 6, 7, 0, 1, 2]
배열이 정렬돼 있지 않은데도 이진 탐색이 된다. 각 칸에 “이 값이 배열의 마지막 값보다 큰가?” 를 물으면 판정이 한 번만 바뀌기 때문이다.
값 : 4 5 6 7 0 1 2
nums[i] > 마지막 : T T T T F F F
↑
첫 거짓 = 최솟값
잘린 지점 앞쪽은 전부 마지막 값보다 크고, 최솟값부터 끝까지는 전부 마지막 값 이하다. 그래서 첫 거짓이 곧 최솟값이고, 앞의 최솟값 틀을 그대로 쓴다.
class Solution:
def findMin(self, nums: list[int]) -> int:
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[-1]:
lo = mid + 1 # 잘린 지점 앞쪽, 최솟값은 mid 뒤에 있다
else:
hi = mid # mid 가 최솟값일 수 있다
return nums[lo]- 마지막 칸은
nums[-1] > nums[-1]이 거짓이라 항상 거짓 쪽이다. 그래서hi를len(nums) - 1로 시작해도 첫 거짓이 범위 밖으로 나가지 않는다. nums[0]과 비교하면 안 된다. 회전하지 않은 배열[1, 2, 3]에서는 모든 칸이 “첫 값 이상” 이라 판정이 갈리지 않는다. 마지막 값은 회전 여부와 관계없이 항상 최솟값 쪽 구간에 속하므로 기준으로 안정적이다. 회전하지 않은 배열은 모든 칸이 거짓이 되어 첫 칸이 답으로 나온다.- 중복이 있는 LeetCode 154 에서는
nums[mid] == nums[-1]이면 어느 쪽인지 알 수 없다. 이때는hi를 한 칸만 줄이므로 최악의 경우 이 된다.
정렬이 아니라 판정이 단조로우면 된다
이진 탐색에 필요한 것은 배열이 정렬돼 있다는 사실이 아니라, 참과 거짓을 한쪽씩 몰리게 나누는 질문 하나다. 이 노트의 예제를 나란히 놓으면 이렇다.
| 문제 | 탐색 대상 | 참과 거짓을 가르는 질문 | 답 |
|---|---|---|---|
| 875 | 먹는 속도 (숫자 범위) | 이 속도로 h 시간 안에 다 먹는가? | 첫 참 |
| 1011 | 배 적재량 (숫자 범위) | 이 적재량으로 days 일 안에 다 보내는가? | 첫 참 |
| Time Based Key-Value Store | 정렬된 timestamp | 이 시각이 t 이하인가? | 마지막 참 (첫 거짓의 한 칸 앞) |
| 153 | 회전된 배열 | 이 값이 마지막 값보다 큰가? | 첫 거짓 |
875 와 1011 은 배열이 아니라 숫자 범위를 탐색하고, 153 은 정렬이 깨진 배열을 탐색한다. 처음 보는 문제에서 이진 탐색을 떠올리려면 “정렬돼 있나?” 보다 “답을 기준으로 한쪽은 전부 참, 반대쪽은 전부 거짓이 되는 질문이 있나?” 를 묻는 편이 낫다.
자주 하는 실수
- 범위 없이 탐색하기. 후보를 절반으로 줄였다가 두 배로 늘리는 식으로 오가면, 볼 수 있는 값이 처음 값을 2 로 나눈 수들로 한정되어 답을 건너뛴다. 같은 값을 오가며 끝나지 않거나 0 으로 나누는 문제도 생긴다. 이진 탐색은 항상
[lo, hi]범위를 들고 그 범위를 절반으로 줄인다. - 판정 함수 안의 올림. “바나나
p개를 속도k로 먹는 시간” 을p // k + 1로 쓰면 나누어떨어질 때 1 이 크다. 올림은(p + k - 1) // k다. - 단위가 섞인 변수 이름. 속도를
hour라는 이름에 담으면, 나중에 속도와 시간을 비교하는 코드를 써도 눈치채기 어렵다.speed,hours처럼 단위가 드러나게 짓는다. - 내림한
mid에lo = mid, 그리고 열린hi에hi = mid - 1. 각각 무한 루프 (B.4) 와 답 누락을 만든다. 따라가 보기는 Time Based Key-Value Store 의 C.2 에 있다. - 끝나고
mid를 반환하기. 마지막으로 확인한mid는 거짓일 수 있다. 답은 범위가 한 칸으로 줄어든 자리인lo다 (B.3).