파라메트릭 서치

개념

최적화 문제를 결정문제로 바꿔 푸는 방법
최적화 문제--> 문제의 상황을 만족하는 최소,최대값을 구하는 문제
결정문제--> 예/ 아니오 형태의 답이 나오는 문제

특정 값의 최대/최소값을 구하려 할 때, 그 값의 범위를 이진탐색 해가며 조건에 맞는지를 계속 확인함

문제 예시

백준 나무자르기 2805 https://www.acmicpc.net/problem/2805
나무들의 길이가 주어지고 절단기를 통해 나무를 잘라서 집으로 가져가려한다. 적어도 M 미터의 나무를 집에 가져가기 위해 설정할 수 있는 절단기 높이의 최대값을 구하라
최대값을 구하는 문제이지만 절단기의 값을 이진 탐색을 통해 조절해가며 가져갈 수 있는 나무의 길이를 구하고 M이상인지(예/아니오)를 판단한다. 이를 반복하여 조건에 맞는 값을 구할 수 있다.

문제 힌트

특정 변수의 최대/ 최소를 구하라고 주어졌을 때, M의 범위를 확인해본다. M의 최대 크기가 1e9 이상일 경우 O(N) 보다 빠른 O(log N) 시간 복잡도를 가져야 하므로 파라메트릭 서치를 의심해볼 수 있다

풀이 방법

절단기의 길이를 이진탐색을 통해 정하고 해당 길이일 때 절단된 나무의 길이를 구한다. 나무의 길이가 M이상이면 절단기 길이를 늘리는 방향으로 조절하고, 그렇지 않을 경우 절단기 길이를 줄인다. 늘리거나 줄이는 방식은 이진탐색과 같다.

int main(void){
    int n, m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    cin>>trees[i];
    int answer=0;
    int start,end,mid;
    long long sum;
    start=0;end=int(1e9);
    while(start<=end){
        mid=(start+end)/2;
        sum=0;
        for(int i=0;i<n;i++){
            int temp=trees[i]-mid;
            sum+=(temp>=0? temp:0);
        }
        if(sum>=m){
            answer=max(answer,mid);
            start=mid+1;      
        }
        else{
            end=mid-1;
        }
    }
    cout<<answer<<"\n";
    return 0;
}

시간 복잡도

위 문제의 경우 절단기 길이를 조절할 때 이진탐색을 사용하므로 O(log M)의 시간이 걸리며, 절단기를 가지고 나무를 자를 때 모두 순회해야 하므로 O(N)이 걸린다. 따라서 전체 시간복잡도는 O(Nlog M) 이다.

의의

단순이 주어진 배열에서의 이진 탐색이 아닌, 특정 변수의 범위를 이진탐색함으로써 최대/최소값을 구할 수 있다.