[Algorithm] Parametric Searching

개요

매개변수 탐색은 정해진 범위 내에서 어떤 조건 P(x)를 만족하는 x의 최대 혹은 최소값을 구하는 알고리즘이다.
탐색범위내에서 임의로 x를 선택하여 해당 x가 문제의 조건을 만족시키는 값인지 검증하고 최적의 값을 찾는 방향으로 범위를 좁혀나가는 방법이다.
탐색방법으로 이분탐색을 사용하는데, 이분탐색 과정에서 선택된 x가
- 조건 P(x)를 만족한다면 : x보다 최적인 범위를 다음 탐색 범위로 설정한다.
- 조건 P(x)를 만족하지 않는다면 : x보다 좋지않은 범위를 다음 탐색 범위로 설정한다.

Parametrix Searching Code

// 조건을 만족하는 최소값을 구하는 경우
// min : 매개변수 범위의 최소값
// max : 매개변수 범위의 최대값
int Minimum_Parametric_Searching(int min, int max)
{
    // min과 max가 같아지는 시점에 종료된다.
    while (min < max)
    {
        int pivot = (min + max) / 2; // .5 내림으로 교착상태를 막는다.

        if (P(pivot) == true) // 조건을 만족한다면,
            max = pivot;      // pivot을 포함하면서 pivot보다 작은 값을 찾을수 있는 범위로 좁혀나간다.        
        else                  // 조건을 만족하지 않는다면,
            min = pivot + 1;  // pivot을 제외하면서 pivot보다 큰 값을 찾을수 있는 범위로 좁혀나간다.
    }

    return min;
}

// 조건을 만족하는 최대값을 구하는 경우
// min : 매개변수 범위의 최소값
// max : 매개변수 범위의 최대값
int Maximum_Parametric_Searching(int min, int max)
{
    // min과 max가 같아지는 시점에 종료된다.
    while (min < max)
    {
        int pivot = (min + max + 1) / 2; // .5 올림으로 교착상태를 막는다.

        if (P(pivot) == true) // 조건을 만족한다면,
            min = pivot;      // pivot을 포함하면서 pivot보다 큰 값을 찾을수 있는 범위로 좁혀나간다.        
        else                  // 조건을 만족하지 않는다면,
            max = pivot - 1;  // pivot을 제외하면서 pivot보다 작은 값을 찾을수 있는 범위로 좁혀나간다.
    }

    return max;
}

Complexity

P(x)를 결정하는 알고리즘 D(x)가 있다면
$Time(D(x))\ast log(max-min)$ 시간으로 구할 수 있다.

여담

이분탐색이라 그런지 실제 문제에서는 범위가 이상할정도로 크게 설정된다. 예를들어 범위가 몇억.. 이러면 매개변수 탐색방법을 생각해볼만 하다.

3079번: 입국심사