배열이 아니라 답을 이진 탐색하기

"이진 탐색은 사실 배열에 관한 게 아니야. 'X에서 되면 X보다 큰 것도 전부 된다'가 성립하는 어떤 질문에나 관한 거지. 그 단조로운 모양이 보이는 순간, 답 자체를 이진 탐색할 수 있어."

일반화

이진 탐색이 진짜로 요구하는 건 '정렬된 배열'이 아니라 단조성이야. 매개변수를 키워 갈 때 답이 정확히 한 번만 아니오에서 예로 뒤집히고 다시는 안 뒤집히는 예/아니오 질문 말이야. 정렬된 배열은 그중 한 사례일 뿐이지("이 원소가 찾는 값 이하인가?"가 딱 한 번 뒤집히니까). 그런데 이 패턴은 훨씬 넓어. 작은 x에서는 거짓이고 큰 x에서는 참인, 또는 그 반대인 판정 함수 feasible(x)를 쓸 수 있다면 답의 공간을 이진 탐색해서 조건을 만족하는 가장 작은 x라는 정확한 경계를 O(log(범위) × 판정 비용)에 찾을 수 있어.

'답을 이진 탐색하기'

이게 탐색처럼 보이지도 않는 문제 장르를 통째로 열어. 대표적인 예를 보자.

D일 안에 짐 배송하기. 모든 짐을 D일 안에 실어 나를 수 있는 가장 작은 배 용량을 찾는 문제야. 용량이 크면 날짜가 줄어드니 단조지. 그러니 용량을 이진 탐색해.
코코의 바나나 먹기. H시간 안에 모든 더미를 비울 수 있는 가장 느린 먹는 속도를 찾는 문제고. 속도가 빠르면 시간이 줄어드니 단조야. 속도를 이진 탐색하면 돼.
최대 부분배열 합 최소화. k개 조각으로 나눌 때 허용 최댓값이 크면 필요한 조각 수가 줄어들지. 허용 최댓값을 이진 탐색해.

모양은 언제나 같아. "어떤 조건이 성립하는 X 중 가장 작은(또는 가장 큰) 값 찾기"이고, 그 조건이 X에 대해 단조인 거야. 배열을 탐색하는 게 아니라, 판정 테스트를 비교 삼아서 답이 될 수 있는 범위를 탐색하는 거지.

이진 탐색은 정렬된 배열만이 아니라 단조로운 술어라면 어디에나 통해. x가 커질 때 'feasible(x)'가 거짓에서 참으로, 또는 그 반대로 한 번만 바뀐다면 답의 공간을 이진 탐색해서 그 경계를 찾으면 돼. 신호는 '뭔가가 성립하는 최소 X 찾기'나 '최댓값을 최소화하기'야.

수학적 사촌

수치해석의 이분법(bisection method)은 연속 함수가 구간의 양 끝에서 서로 다른 부호를 가질 때, 중간값 정리에 기대어 그 사이에 있는 근을 좁혀 들어가. 여기서 함수가 단조일 필요는 없어. 연속성과 부호 변화가 핵심 전제거든. 반면 답 공간의 이진 탐색은 참과 거짓 판정이 단조롭게 바뀌는 그 경계를 찾는 거야. 둘 다 구간을 절반으로 줄이지만 그걸 정당화하는 전제가 서로 달라.

피파의 고백

어떤 문제가 제시간에 끝낼 수 있는 최소 먹는 속도를 물었는데, 나는 그게 이진 탐색 문제인 줄 전혀 몰랐어. 배열이 없었으니까! 아빠가 묻더라. "속도 5 가 되면, 속도 6 도 돼?" 당연히 되지. "그럼 단조야 — 속도를 이진 탐색해." 그 순간 이진 탐색이라는 개념이 통째로 열렸어. 이건 조회 도구가 아니라 어떤 단조로운 임계값이든 좁혀 들어가는 방법이었던 거야. 이제는 '되는 가장 작은 X 찾기'라는 말만 나오면 배열이 있든 없든 반사적으로 이진 탐색을 떠올려.

Code

답의 공간을 이진 탐색하기·python

import math

# 답에 이진 탐색: 더미를 H 시간에 끝낼 최소 먹는 속도.
# 정렬 배열 없음 — feasibility 확인을 비교로 써 *속도* 를 탐색.
def min_eating_speed(piles, H):
    def hours_needed(speed):
        return sum(math.ceil(p / speed) for p in piles)
    lo, hi = 1, max(piles)            # 답 범위: 1 .. 가장 큰 더미
    while lo < hi:
        mid = (lo + hi) // 2
        if hours_needed(mid) <= H:    # 됨 -> 더 *느린* 속도 시도
            hi = mid
        else:                          # 너무 느림 -> 더 빨라야
            lo = mid + 1
    return lo                          # 되는 가장 작은 속도

print(min_eating_speed([3, 6, 7, 11], 8))   # 4
# 'feasible(speed)' 가 단조: 어떤 속도가 제때 끝내면, 더 빠른 건 다 끝내.
# 그래서 배열이 아니라 속도 범위를 이진 탐색.

# bisect 로 경계 탐색: 정렬 리스트에서 값의 첫 출현.
import bisect
arr = [1, 2, 2, 2, 3, 5]
print(bisect.bisect_left(arr, 2))    # 1  — *첫* 2 의 인덱스
print(bisect.bisect_right(arr, 2))   # 4  — *마지막* 2 바로 다음 인덱스

Exercise

시간순으로 늘어선 작업 목록을 순서를 유지한 채 연속된 구간으로 잘라 워커 k명에게 나눠 주려고 해. 목표는 가장 많이 맡은 사람의 작업량을 최소화하는 거야. '최대 부하가 M 이하로 가능한가?'라는 질문이 왜 M에 대해 단조인지 설명하고, 답의 범위와 판정 방법도 같이 써 봐.

Hint

구간이 연속이고 순서가 유지된다는 전제에서, 최대 부하 M으로 가능하다면 그보다 큰 M으로도 당연히 가능해. 그러니 [가장 큰 단일 작업, 전체 합] 범위에서 M을 이진 탐색하고, 작업을 순서대로 담아 가며 필요한 워커 수가 k 이하인지 검사하면 돼.

일반화

'답을 이진 탐색하기'

수학적 사촌

피파의 고백

Code

External links

Exercise

Progress

댓글 0