"최솟값의 최댓값을 구하시오." 코테 문제를 읽다가 이 문장을 만나면 멍해지는 사람이 많다. 최소인데 최대? 뭔 소리지? 근데 이 표현, 한번만 감 잡으면 오히려 반가워진다. 파라메트릭 서치 문제의 전형적인 시그널이거든.

이분 탐색인데 배열이 없다?

이분 탐색 하면 보통 "정렬된 배열에서 특정 값 찾기"를 떠올린다. lower_bound, upper_bound 같은 것들. 근데 파라메트릭 서치는 배열을 뒤지는 게 아니라 정답 자체의 범위를 이분 탐색한다.

백준 2805번 나무 자르기를 보자. N개의 나무를 절단기로 자르는데, 절단기 높이를 H로 설정하면 H보다 높은 부분만 잘려나간다. 최소 M미터의 나무를 가져가야 할 때, H의 최댓값은?

여기서 H가 정답이다. H를 0부터 가장 높은 나무까지 하나씩 시도하면? 나무 높이가 10억까지 가능하니까 당연히 시간 초과다. 그런데 한 가지 성질이 있다 — H를 올릴수록 가져갈 수 있는 나무량은 줄어들고, 내릴수록 늘어난다. 그래프로 그리면 한쪽으로만 내려가는 곡선이 나온다. 이게 **단조성(monotonicity)**이다.

단조성이 왜 중요하냐면, 이걸 만족하는 순간 탐색 공간을 절반씩 날릴 수 있기 때문이다. mid 값에서 조건을 만족하면 그보다 작은 값들은 전부 만족한다는 보장이 생긴다. 반대로 mid에서 실패하면 그보다 큰 값은 볼 필요도 없다. 10억 개의 후보가 log₂(10⁹) ≈ 30번의 확인으로 줄어든다. 브루트포스로 몇 초씩 걸릴 문제가 눈 깜짝할 새에 끝난다.

이걸 처음 접하면 "배열도 없는데 이분 탐색이라고?" 하면서 어색하다. 근데 사실 이분 탐색의 본질은 배열이 아니라 단조성이다. 정렬된 배열은 단조성의 한 가지 사례일 뿐이고, 파라메트릭 서치는 그 본질을 정답 범위에 직접 적용하는 거다.

뼈대는 딱 하나

파라메트릭 서치 문제가 수십 개 있어도 코드 구조는 전부 이거다:

def solve(lo, hi):
    ans = lo
    while lo <= hi:
        mid = (lo + hi) // 2
        if is_possible(mid):
            ans = mid
            lo = mid + 1   # 최댓값을 찾을 때
        else:
            hi = mid - 1
    return ans

세 단계로 쪼개면:

  1. 정답이 될 수 있는 범위를 lo, hi로 잡는다

  2. 중간값 mid로 "이 값이 조건을 만족하는가?" 판별한다 (결정 함수)

  3. 만족하면 더 좋은 답이 있는 쪽으로, 아니면 반대쪽으로 범위를 좁힌다

진짜 실력이 갈리는 건 is_possible 함수다. 문제 조건을 O(N) 또는 O(N log N) 안에 판별할 수 있어야 한다. 이 결정 함수를 못 짜면 이분 탐색 틀을 알아도 소용이 없다.

"최솟값의 최댓값" vs "최댓값의 최솟값"

둘 다 파라메트릭 서치다. 차이는 이분 탐색 방향뿐이다.

최솟값의 최댓값 — 정답 후보를 키울수록 조건 만족이 어려워진다. 만족하면 lo = mid + 1. 백준 2805, 2110, 1654 전부 이 유형. 코테에서 압도적으로 자주 나온다.

최댓값의 최솟값 — 반대. 키울수록 조건이 느슨해진다. 만족하면 hi = mid - 1. 가끔 그리디랑 섞여서 등장한다.

문제를 읽었는데 이분 탐색이 안 떠오른다

당연하다. 문제에 "정렬된 배열" 같은 키워드가 없으니까. 파라메트릭 서치를 알아채는 시그널은 따로 있다:

  • "최소 ~를 만족하는 최대 X" 또는 그 반대 표현이 등장

  • X를 고정했을 때 나머지 조건을 O(N)으로 검증 가능

  • X를 증가/감소시키면 조건 만족 여부가 한 방향으로만 바뀜

세 개 다 해당되면 거의 확정이다. 특히 두 번째가 중요한데, 결정 함수를 어떻게 짤지 감이 안 오면 파라메트릭이 아닐 가능성도 있다. 그럴 땐 다른 접근법을 먼저 의심하자.

매번 틀리는 그 부분들

알고리즘 자체는 이해했는데 자꾸 틀린다면 높은 확률로 아래 세 가지 중 하나다.

초기값 설정. 나무 자르기에서 hi를 나무 높이 최댓값으로 잡으면 맞다. 나무 높이의 합으로 잡아도 답은 나온다 — 탐색 범위가 쓸데없이 넓어질 뿐. 문제는 lo 쪽이다. 습관적으로 lo = 1로 잡았는데 정답이 0인 경우, 또는 lo = 0으로 잡았는데 문제에서 "1 이상"을 명시한 경우. 문제 조건에서 정답의 하한과 상한을 정확히 읽어내야 한다. 대충 넉넉하게 잡으면 되지 않냐고 할 수 있는데, 범위가 0~10¹⁸처럼 크면 lo + hi에서 오버플로우가 터진다. 그래서 범위 설정이 "대충"이 아니라 "정확히"여야 한다.

오버플로우. Python은 정수 크기 제한이 없어서 괜찮지만, Java나 C++에서는 mid 계산부터 함정이다.

// 위험: lo + hi가 int 범위를 넘을 수 있다
int mid = (lo + hi) / 2;

// 안전
int mid = lo + (hi - lo) / 2;

이것만이 아니다. 결정 함수 안에서 곱셈이 들어가는 경우도 있다. 예를 들어 입국심사 문제에서 mid / times[i]를 전부 더하는데, mid가 10¹⁸이고 times[i]가 1이면 합산 과정에서 long 범위를 넘길 수 있다. 결정 함수 내부의 중간 연산값까지 오버플로우 체크를 해야 한다. Python 쓰면 이런 고민이 통째로 사라지긴 하는데, 코테에서 C++이나 Java를 써야 하는 상황이라면 이 부분이 당락을 가른다.

반복 조건. while (lo <= hi) vs while (lo < hi) — 이게 헷갈리면 무한 루프에 빠지거나 답이 1 차이 난다. lo <= hi를 쓰고 ans 변수를 따로 관리하는 스타일이 실수가 적다. lo < hi 방식은 경계 처리를 정확히 이해해야 해서, 아직 익숙하지 않다면 전자를 권한다.

연습 로드맵

이 순서대로 풀어보자. 백준 1654(랜선 자르기)로 입문하고, 2805(나무 자르기)로 결정 함수 변형을 익히고, 2110(공유기 설치)에서 그리디가 섞인 결정 함수를 경험하고, 프로그래머스 입국심사에서 실전 감각을 잡는다.

4번까지 다 풀었는데 감이 안 온다면, 코드를 치기 전에 종이에 결정 함수부터 써보자. "mid가 X일 때 조건을 만족하는가?"를 자연어로 정리하는 연습이 코드보다 먼저다.