파라매트릭 서치(Parametric Search)

도입

다음과 같은 문제를 푼다고 생각해보자. 

자동차 경주대회가 있었다. 먼저들어온 순서대로 N대의 자동차들에 대한 평균 속력이 주어진다. 하지만 이 차들중에 평균속력이 K이상인 차들은 우승자격이 박탈된다. 어떤 차가 우승하게 될까?

파라메트릭 서치란?

파라메트릭 서치(Parametric Search)는 기본적으로 이분탐색을 베이스로 깔고 들어간다. 나는 Parametric Search를 "조건내 최대(최소)를 찾는 문제를 log의 시간복잡도를 사용해 결정문제로 바꾸는 테크닉"이라고 말하고 싶다. 이 말만 들어서는 의미를 제대로 파악하기 힘들고 도입의 문제를 이용해 이 말을 풀어나가보려고 한다. 

파라메트릭 서치의 역할

도입의 문제를 보면 K미만의 숫자 중 가장 큰 숫자를 찾는 문제가 된다. 하지만 Parametric Search는 질문을 통해 답을 알아내는 방식이다. N대의 차들 중 가운데 차에 물어본다.
"넌 우승자격이 박탈되었니?" 만약 그 차가 우승자격이 박탈되었다면 내가 찾는 차는 가운데 이후에 들어온 차이다. 만약 박탈되지 않았다면 그 차, 혹은 더 빨리 들어온 차이다. 

좀 더 일반적으로 이야기 하자면 1~i까지가 A그룹이고 i+1~N까지가 B그룹일때 계속해서 중앙에 질문을 던져서 A그룹과 B그룹의 경계를 알아내는 것이 목표이다.

문제에서 원하는 것은 "우승조건이 있는 차들 중~~" 이었지만, 우리는 파라메트릭 서치를 활용해서 원하는 내용을 "너는 우승 조건이 있니?"로 바꾸었다. 이것이 결정문제이다. 

N개의 범위에서 이분탐색처럼 중앙에 질문을 던지므로 시간복잡도는 $O($(질문의 시간복잡도)$*lgN)$이 된다.

사용 경우

지금은 기존 문제도 쉽게 풀 수 있지만, 그냥 문제는 어려운데 조건 판별 문제는 빠르고 쉽게 되는 경우가 있으면 그 때 파라메트릭 서치 기법을 사용하게 된다. 이 테크닉은 거의 항상 정렬된 자료에서 사용되어지게 된다. 

코딩

BOJ 2512 예산 문제의 코드를 가져왔다.

#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
ll n, a[10000], m, lo, hi, ma, s;
int main() {
    scanf("%lld", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
        ma = max(a[i], ma);
        s += a[i];
    }
    scanf("%lld", &m);
    if (m >= s) {
        printf("%lld\n", ma);
        return 0;
    }
    lo = 0;
    hi = 21000000000;
    while (lo < hi) {
        ll mid = (lo + hi) >> 1;
        ll r = 0;
        for (int i = 0; i < n; i++) {
            if (mid >= a[i])
                r += a[i];
            else
                r += mid;
        }
        if (r <= m)
            lo = mid + 1;
        else
            hi = mid;
    }
    printf("%lld\n", lo - 1);
    return 0;
}
 
 

20번째 줄부터 33번째 줄까지 Parametric Search를 실시하는 구간이다. 전체 구간중 가운뎃 값에 대해 질문을 던지고, 그 질문의 결과에 따라 다음구간을 설정하는 방식이다.

유의사항

짜는 스타일이 사람마다 다 다르다. 그리고 특히 +1,-1 차이로 굉장히 많이 오류가 나고, 무한반복이 되기도 하고 틀리기도 한다. 문제마다 다 다르기도 하다. 머리를 써가면서, 부딪혀가면서 문제에 맞는 유동적인 Parametric Search 실시와 답 찾기가 필요하다. 

추천문제

BOJ 2512 예산

BOJ 2805 나무자르기

BOJ 1654 랜선 자르기

BOJ 17976 Thread Knots