Parametric Search

정렬된 배열에서 값을 찾는 일반 이분탐색은 익숙한 도구다. 그런데 효율성 문제에서 자주 마주치는 형태는 “최소 속도”, “최대 거리”, “최소 시간” 같이 답 자체를 찾는 문제다. 답이 배열에 들어 있지 않으니 직접 탐색은 안 된다. 그래도 “X 가 답으로 가능한가?” 는 단조적으로 판단할 수 있을 때가 많고, 그러면 답 자체를 이분탐색할 수 있다. 이 사고를 parametric search 라 부른다.

parametric search 는 두 가지 조건 위에서 동작한다. 결정 함수 can(x) 가 정의된다. 답 후보 x 를 받아 “이 값으로 문제를 풀 수 있는가?” 를 boolean 으로 답하는 함수다. 그리고 can 이 단조적이다. x 가 어떤 방향으로 갈수록 항상 True 가 되거나 항상 False 가 된다. 두 조건이 만족되면 답 후보 영역은 가능 영역과 불가능 영역으로 나뉘고, 그 경계가 우리가 찾는 답이다.

block-beta
    columns 8
    a1["x = lo"]
    a2[" "]
    a3[" "]
    a4["x*"]
    a5[" "]
    a6[" "]
    a7[" "]
    a8["x = hi"]

    style a1 fill:#FFCDD2
    style a2 fill:#FFCDD2
    style a3 fill:#FFCDD2
    style a4 fill:#C8E6C9
    style a5 fill:#C8E6C9
    style a6 fill:#C8E6C9
    style a7 fill:#C8E6C9
    style a8 fill:#C8E6C9

빨간 영역은 can(x) == False, 초록 영역은 can(x) == True. 우리는 초록 영역의 첫 값 x* 를 찾고 싶다. 이 경계를 직접 계산할 수는 없지만 이분탐색으로 좁혀 들어갈 수 있다. 일반 이분탐색이 “정렬된 배열에서 값을 찾는다” 면, parametric search 는 “단조 결정 함수의 경계를 찾는다” 가 된다.

의사결정 흐름

코드보다 먼저 정해야 하는 결정이 네 가지다. 이걸 짚어두면 코드는 거의 자동으로 따라온다.

단조성 방향 — x 가 커질수록 쉬워지는가, 어려워지는가. 답이 가능 영역의 최솟값인지 최댓값인지가 여기서 결정된다.
결정 함수 — can(x) -> bool 의 본체. 결정 함수가 짧고 빠를수록 전체 풀이가 깔끔해진다.
lo, hi — 답이 존재할 수 있는 범위. 각각의 값에 한 줄 근거가 붙는다.
수렴 방향 — can(mid) == True 일 때 hi 를 줄일지 lo 를 키울지. 최솟값을 찾으면 hi 를 줄이고, 최댓값을 찾으면 lo 를 키운다.

flowchart TD
    A[답이 배열에 없는 문제] --> B{x 가 변하면
일관되게 쉬워지는가}
    B -->|예| C["결정 함수 can(x) 정의"]
    B -->|아니오| Z[다른 접근]
    C --> D["lo, hi 정당화"]
    D --> E["수렴 방향
(find_min vs find_max)"]
    E --> F[이분탐색]

예제 — 시간당 K 개 먹기

문제는 단순하다. 더미 배열 piles 와 제한 시간 h 가 주어지고, 시간당 정수 k 개씩 먹을 수 있다. 한 시간에 한 더미만 먹을 수 있고, 더미 크기가 k 미만이면 다 먹고 다음 시간으로 넘어간다. h 시간 안에 모두 먹어 치울 수 있는 k 의 최솟값을 구하면 된다 (LeetCode 875).

k 를 1부터 차례로 시도하면 max(piles) 가 클 때 시간이 모자란다. 그런데 k 가 커질수록 한 시간에 더 많이 먹을 수 있어서 총 시간이 줄어든다 — 단조성이 명확하다. 결정 함수와 골격을 분리하면 다음과 같다.

def can_eat_in_time(piles, k, h):
    return sum((p + k - 1) // k for p in piles) <= h


def min_eating_speed(piles, h):
    lo, hi = 1, max(piles)
    answer = hi
    while lo <= hi:
        mid = (lo + hi) // 2
        if can_eat_in_time(piles, mid, h):
            answer = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return answer

lo = 1 은 0개씩 먹으면 영원히 못 먹기 때문이다. hi = max(piles) 은 한 시간에 한 더미 이상 먹을 수 없으니 k 를 그 이상으로 키워도 시간이 더 줄지 않기 때문이다. 결정 함수의 (p + k - 1) // k 는 math.ceil(p / k) 와 같다. k - 1 을 미리 보태면 배수가 아닐 때 floor 가 한 칸 올라간다. 정수 연산만 쓰므로 float 정밀도 문제와 변환 비용을 동시에 피한다.

lo / hi 정당화

lo 와 hi 는 답의 가능 영역 경계다. 너무 좁게 잡으면 답을 놓치고, 너무 넓게 잡으면 탐색 횟수가 늘어난다. 자주 마주치는 패턴이 정해져 있다.

시간당 K 개 먹기: lo = 1, hi = max(piles) — 한 시간에 한 더미 이상 먹지 못한다
배달 용량 결정: lo = max(weights), hi = sum(weights) — 단일 짐도 못 실으면 불가능, 다 실으면 하루
공유기 거리 / 두 공 사이 최소 거리: lo = 1, hi = max(positions) - min(positions) — 양 끝 배치가 물리적 상한
입국 심사 시간: lo = 1, hi = max(times) * n — 가장 느린 심사관이 혼자 n 명을 처리

평균을 기반으로 hi 를 줄이려는 시도는 corner case 위험이 있다. floor 손실로 답을 한 칸 놓치는 경우가 생기기 때문이다. 라이브 코딩에서는 안전한 상한을 먼저 잡고, 시간이 남으면 tight 하게 조이는 순서가 낫다.

부등호 매핑

parametric search 의 결정 함수는 부등호 1글자가 정합성을 좌우한다. 문제 지문의 한국어 표현을 코드 부등호로 정확히 매핑해야 한다.

지문	코드
이상	`>=`
이하	`<=`
초과	`>`
미만	`<`

결정 함수를 작성한 직후 작은 입력으로 손 trace 한 번을 권장한다. piles = [3, 6, 7, 11], h = 8 정도면 충분하다. k = 4 일 때 결정 함수가 True 를 돌려주는지, k = 3 일 때 False 를 돌려주는지 확인하면 부등호 실수가 즉시 드러난다.

답이 정렬된 배열에 들어 있지 않은 문제도 답 자체를 이분탐색하면 풀리는 경우가 많다. 단조성 방향을 확인하고, can(x) 를 정의하고, lo 와 hi 의 근거를 한 줄씩 짚는다. 이 세 결정이 끝나면 이분탐색 골격은 거의 자동이다. parametric search 가 풀어 주는 범위는 좁지 않다. 한 시간에 몇 개를 먹어야 하는지, 한 번에 얼마나 실어야 하는지, 사람과 사람 사이의 최소 거리는 얼마인지 — 결정 함수로 환원하는 사고를 익혀두면 이런 문제들이 같은 골격으로 풀린다.