파라메트릭 서치: 결정 문제를 활용한 최적해 탐색 가이드

최적화 문제를 해결하는 가장 세련된 방법 중 하나는 역발상입니다. "최댓값을 구하라"는 직접적인 질문에 답하기 어려울 때, 우리는 "특정 값 $X$가 조건을 만족하는가?"라는 결정 문제(Decision Problem)로 질문을 바꾸어 던질 수 있습니다. 이러한 논리적 전환을 이분 탐색(Binary Search)과 결합한 기법이 바로 파라메트릭 서치(Parametric Search)입니다. 본 포스팅에서는 파라메트릭 서치의 동작 원리와 성립 조건, 그리고 실제 고난도 문제에서 이 기법이 어떻게 마법처럼 최적해를 찾아내는지 상세히 기술하겠습니다.

1. 파라메트릭 서치의 정의와 이분 탐색과의 관계

파라메트릭 서치는 최적화 문제(어떤 함수를 최대로/최소로 만드는 변수 찾기)를 결정 문제(YES or NO)로 바꾸어 해결하는 기법입니다. 이분 탐색이 '정렬된 배열에서 특정 데이터의 위치'를 찾는 것이라면, 파라메트릭 서치는 '정답이 될 수 있는 값의 범위' 내에서 이분 탐색을 수행하여 조건에 부합하는 경계값을 찾아냅니다. 이는 검색 대상이 인덱스가 아니라 '정답의 후보 값'이라는 점에서 이분 탐색의 강력한 응용이라고 할 수 있습니다.

1-1. 왜 파라메트릭 서치를 사용하는가?

어떤 최적화 문제는 수식으로 바로 풀기에는 너무 복잡하거나 변수가 많습니다. 하지만 "이 값 이상이면 가능한가?"라는 질문에는 시뮬레이션을 통해 비교적 쉽게 답할 수 있는 경우가 많습니다. 파라메트릭 서치는 이러한 결정 함수의 단순함을 이용하여, $O(\log N)$번의 질문만으로 정확한 최적해를 도출해냅니다.

2. 파라메트릭 서치가 성립하기 위한 필수 조건: 단조성

이 기법을 적용하기 위해 반드시 만족해야 하는 성질은 단조성(Monotonicity)입니다. 즉, 어떤 값 $X$에 대해 조건이 '참'이라면, $X$보다 작은(혹은 큰) 모든 값들에 대해서도 조건이 반드시 '참'이어야 합니다. 그래프로 그렸을 때 결과값이 [YES, YES, YES, NO, NO]와 같이 특정 지점을 기준으로 명확히 갈려야만 이분 탐색을 통해 그 경계선(최적해)을 찾을 수 있습니다. 만약 결과가 [YES, NO, YES, YES, NO]처럼 불규칙하게 나타난다면 파라메트릭 서치는 사용할 수 없습니다.

3. 파라메트릭 서치 구현의 표준 템플릿

파라메트릭 서치는 구현 과정에서 무한 루프나 경계값 오류(Off-by-one error)가 자주 발생하므로, 정형화된 틀을 사용하는 것이 좋습니다.

• 초기 범위 설정: 정답이 될 수 있는 최소값(low)과 최대값(high)을 설정합니다.
• 중간값(mid) 검사: check(mid)라는 결정 함수를 통해 조건 만족 여부를 판단합니다.
• 범위 좁히기: 조건이 참이면 더 큰(혹은 작은) 범위를 탐색하고, 거짓이면 반대 범위를 탐색합니다.
• 정답 기록: 조건을 만족할 때마다 result = mid와 같이 현재까지의 최적해를 저장해둡니다.

4. 실전 활용 사례: 나무 자르기와 공유기 설치

파라메트릭 서치는 주로 '가장 긴', '가장 짧은', '최소한의' 등의 키워드가 포함된 문제에서 빛을 발합니다.

• 나무 자르기: 절단기 높이를 $H$로 설정했을 때 가져가는 나무의 길이가 $M$ 이상인가? $H$가 낮아질수록 나무 양은 늘어나는 단조성을 이용합니다.
• 예산 배정: 총 예산 상한액을 $X$로 정했을 때 전체 예산 합이 국가 예산 이내인가?
• 네트워크 구축: 공유기 사이의 거리를 $D$로 설정했을 때 총 $C$개의 공유기를 설치할 수 있는가?

# 파라메트릭 서치 표준 구현 (나무 자르기 예시)
def parametric_search(trees, target):
    low, high = 0, max(trees)
    result = 0
    
    while low <= high:
        mid = (low + high) // 2
        # 결정 함수: mid 높이로 자를 때 얻는 나무 양 계산
        total = sum(max(0, t - mid) for t in trees)
        
        if total >= target: # 조건을 만족하면
            result = mid    # 현재 높이를 기록하고
            low = mid + 1   # 더 높은(더 적게 자르는) 높이 시도
        else:
            high = mid - 1  # 더 낮은(더 많이 자르는) 높이 시도
    return result

[파라메트릭 서치 핵심 요약]
1. 개념: 최적화 문제를 '예/아니오'의 결정 문제로 바꾸어 이분 탐색하는 기법입니다.
2. 조건: 정답의 범위를 늘리거나 줄임에 따라 결과가 단조롭게 변하는 구조여야 합니다.
3. 강점: 직접 구하기 어려운 최적해를 $O(\log N \times \text{결정함수 복잡도})$로 정밀하게 찾아냅니다.