배열만이 아니라 답에 이진 탐색

"이진 탐색은 사실 배열에 관한 게 아니야. 'X 가 되면, X 너머 전부도 된다' 인 어떤 질문에든 관한 거야. 그 단조 모양을 보는 순간, 답 자체를 이진 탐색할 수 있어."

일반화

이진 탐색의 진짜 요구는 '정렬된 배열' 이 아니라 — 단조성이야: 매개변수를 키울 때 답이 정확히 한 번 아니오에서 예로 뒤집히고, 절대 다시 안 뒤집히는 예/아니오 질문. 정렬된 배열은 한 예일 뿐 ("원소 ≤ target?" 이 한 번 뒤집힘). 근데 패턴은 훨씬 커: 작은 x 엔 거짓, 큰 x 엔 참 (또는 반대) 인 feasibility 확인 feasible(x) 를 쓸 수 있으면, 답 공간을 이진 탐색해 정확한 경계 — 되는 가장 작은 x — 를 O(log(범위) × 확인-비용) 에 찾아.

'답에 이진 탐색'

이게 탐색처럼 전혀 안 보이는 문제 장르 전체를 열어. 정석 예:

D 일에 패키지 배송: 모든 패키지가 D 일 안에 맞는 가장 작은 배 용량 찾기. 더 큰 용량 → 더 적은 일 (단조). 용량을 이진 탐색.
코코의 바나나 먹기: H 시간에 모든 더미를 끝낼 가장 작은 먹는 속도. 더 빠른 속도 → 더 적은 시간 (단조). 속도를 이진 탐색.
최대 부분배열 합 최소화 (k 부분으로 쪼갤 때): 더 큰 허용-최대 → 더 적은 부분 필요. 허용 최대를 이진 탐색.

모양은 늘: "어떤 조건이 성립하는 X 의 가장 작은/큰 값 찾기", 조건이 X 에 단조. 배열을 탐색하는 게 아니라 — feasibility 테스트를 비교로 써서 가능한 답의 범위를 탐색하는 거야.

이진 탐색은 정렬 배열만이 아니라 어떤 단조 술어에든 작동해. x 가 커질 때 'feasible(x)' 가 거짓-그다음-참 (또는 반대) 이면, 경계를 찾으려 답 공간을 이진 탐색해. 신호: '뭔가 되는 최소 X 찾기' 또는 '최대를 최소화'.

수학적 사촌

이 아이디어는 수학에서 연속 함수가 0 을 가로지르는 곳을 찾는 이분법 (bisection method) 으로 오래됐어: f 가 한 끝에서 음, 다른 끝에서 양이면, 근이 그 사이라, 구간을 절반 내고 재귀. 같은 절반 내기, 같은 단조-가로지르기 로직 — 알고리즘 이진 탐색이 수학자가 몇 세기 쓴 수치 기법의 이산 버전이야. 이진 탐색을 '정렬 리스트에서 찾기' 가 아니라 '단조 경계로 절반 내기' 로 알아보는 게 그걸 쓰는 데서 휘두르는 데로의 업그레이드야.

피파의 고백

한 문제가 제때 끝낼 최소 먹는 속도를 물었고, 난 그게 이진 탐색인지 전혀 몰랐어 — 배열이 없었거든! 아빠가 물었어, "속도 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

시간순 정렬된 n 작업 리스트를 k 워커에게 나눠 한 워커가 받는 최대 작업량을 최소화해야 해. '최대-부하 ≤ M 으로 될 수 있어?' 가 왜 M 에 단조인지, 그게 어떻게 M 을 이진 탐색하게 하는지 논증해. 탐색할 답 범위가 뭐고, feasibility 확인이 뭘 해?

Hint

최대-부하 M 이 달성 가능하면, 더 큰 M 도 그래 (단조) — 여유 더 있으면 늘 적어도 그만큼 잘해. M 을 범위 [최대 단일 작업, 모든 작업 합] 에서 이진 탐색; feasibility 확인이 작업을 워커에 탐욕적으로 채워 그 M 에 ≤ k 워커면 충분한지 세.

일반화

'답에 이진 탐색'

수학적 사촌

피파의 고백

Code

External links

Exercise

Progress

댓글 0