콘텐츠로 이동

삼분 탐색

구간 $[l, r]$에서 단봉(unimodal)인 함수 $f(x)$가 주어졌다고 합시다. 단봉 함수란 함수가 다음 두 가지 동작 중 하나를 보이는 것을 의미합니다.

  1. 함수가 처음에는 순증가하다가 (한 점 또는 한 구간에서) 최댓값에 도달한 뒤, 순감소합니다.

  2. 함수가 처음에는 순감소하다가 최솟값에 도달한 뒤, 순증가합니다.

이 글에서는 첫 번째 경우를 가정하겠습니다. 두 번째 경우는 첫 번째 경우와 완전히 대칭입니다.

목표는 구간 $[l, r]$에서 함수 $f(x)$의 최댓값을 찾는 것입니다.

알고리즘

이 구간 안의 임의의 두 점 $m_1$과 $m_2$를 생각해 봅시다: $l < m_1 < m_2 < r$. $m_1$과 $m_2$에서 함수를 계산합니다. 즉, $f(m_1)$과 $f(m_2)$의 값을 구합니다. 이제 다음 세 가지 경우 중 하나가 됩니다.

  • $f(m_1) < f(m_2)$

    두 점 $m_1$과 $m_2$가 모두 함수가 증가하는 영역에 속하거나 $m_1$만 그 영역에 속하므로, 찾고자 하는 최댓값은 $m_1$의 왼쪽, 즉 구간 $[l, m_1]$에 있을 수 없습니다. 어느 경우든 이는 최댓값을 구간 $[m_1, r]$에서 찾아야 한다는 뜻입니다.

  • $f(m_1) > f(m_2)$

    이 상황은 앞의 경우와 대칭입니다. 최댓값은 $m_2$의 오른쪽, 즉 구간 $[m_2, r]$에 있을 수 없으며, 탐색 공간은 구간 $[l, m_2]$로 줄어듭니다.

  • $f(m_1) = f(m_2)$

    두 점이 모두 함숫값이 최대가 되는 영역에 속하거나, $m_1$은 값이 증가하는 영역에, $m_2$는 값이 감소하는 영역에 속한다는 것을 알 수 있습니다(여기서 함수의 증가/감소가 순증가/순감소라는 점을 사용했습니다). 따라서 탐색 공간은 $[m_1, m_2]$로 줄어듭니다. 코드를 간단하게 하기 위해 이 경우는 앞의 두 경우 중 어느 쪽과도 합칠 수 있습니다.

따라서 두 내부 점에서의 값을 비교한 결과에 따라, 현재 구간 $[l, r]$을 더 짧은 새 구간 $[l^\prime, r^\prime]$으로 바꿀 수 있습니다. 설명한 과정을 구간에 반복해서 적용하면 임의로 짧은 구간을 얻을 수 있습니다. 결국 구간의 길이는 미리 정해 둔 어떤 상수(정확도)보다 작아지며, 그때 과정을 멈출 수 있습니다. 이는 수치적 방법이므로, 그 이후에는 마지막 구간 $[l, r]$의 모든 점에서 함수가 최댓값에 도달한다고 가정할 수 있습니다. 일반성을 잃지 않고 $f(l)$을 반환값으로 삼을 수 있습니다.

점 $m_1$과 $m_2$의 선택에는 아무런 제약을 두지 않았습니다. 이 선택에 따라 구현의 수렴 속도와 정확도가 결정됩니다. 가장 일반적인 방법은 두 점이 구간 $[l, r]$을 세 개의 같은 부분으로 나누도록 고르는 것입니다. 따라서 다음을 얻습니다.

$$m_1 = l + \frac{(r - l)}{3}$$
$$m_2 = r - \frac{(r - l)}{3}$$

$m_1$과 $m_2$를 서로 더 가깝게 고르면 수렴 속도가 약간 빨라집니다.

실행 시간 분석

$$T(n) = T({2n}/{3}) + O(1) = \Theta(\log n)$$

다음과 같이 시각화할 수 있습니다. 점 $m_1$과 $m_2$에서 함수를 계산할 때마다, 사실상 구간의 왼쪽 또는 오른쪽 약 3분의 1을 버리는 것입니다. 따라서 탐색 공간의 크기는 원래 크기의 ${2n}/{3}$이 됩니다.

마스터 정리를 적용하면 원하는 복잡도 추정치를 얻습니다.

정수 인자의 경우

$f(x)$가 정수 매개변수를 받는다면 구간 $[l, r]$은 이산적이 됩니다. 점 $m_1$과 $m_2$의 선택에 아무런 제약을 두지 않았으므로 알고리즘의 정당성은 영향을 받지 않습니다. $m_1$과 $m_2$는 여전히 $[l, r]$을 대략 같은 크기의 3부분으로 나누도록 선택할 수 있습니다.

차이는 알고리즘의 종료 조건에서 발생합니다. 삼분 탐색은 $(r - l) < 3$일 때 멈춰야 합니다. 그 경우에는 서로 다르면서 $l$ 및 $r$과도 다른 $m_1$과 $m_2$를 더 이상 선택할 수 없고, 이로 인해 무한 루프가 발생할 수 있기 때문입니다. $(r - l) < 3$이 되면, 최댓값 $f(x)$를 만드는 점을 찾기 위해 남은 후보 점들 $(l, l + 1, \ldots, r)$을 모두 확인해야 합니다.

경우에 따라 $f(x)$를 계산하는 것이 꽤 느릴 수 있지만, 정밀도 문제 때문에 반복 횟수를 줄이는 것은 불가능합니다. 다행히도 (첫 번째 반복을 제외한) 각 반복에서 $f(x)$를 단 한 번만 계산하는 것이 가능합니다.

이를 어떻게 하는지 알아보기 위해 $m_1$과 $m_2$의 선택 방법을 다시 살펴봅시다. $\varphi$가 어떤 상수일 때, $\frac{r - l}{r - m_1} = \frac{r - l}{m_2 - l} = \varphi$가 되도록 $[l, r]$ 위에서 $m_1$과 $m_2$를 선택한다고 가정합시다. 계산량을 줄이기 위해, 다음 반복에서 새로운 평가 점 $m_1'$, $m_2'$ 중 하나가 $m_1$ 또는 $m_2$와 일치하도록 하는 $\varphi$를 선택하고자 합니다. 그렇게 하면 이미 계산한 함수 값을 재사용할 수 있습니다.

이제 현재 반복 후에 $l = m_1$로 설정한다고 가정합시다. 그러면 점 $m_1'$은 $\frac{r - m_1}{r - m_1'} = \varphi$를 만족합니다. 이 점이 $m_2$와 일치하기를 원하므로, $\frac{r - m_1}{r - m_2} = \varphi$이어야 합니다.

$\frac{r - m_1}{r - m_2} = \varphi$의 양변에 $\frac{r - m_2}{r - l}$을 곱하면 $\frac{r - m_1}{r - l} = \varphi\frac{r - m_2}{r - l}$을 얻습니다. $\frac{r - m_1}{r - l} = \frac{1}{\varphi}$이고 $\frac{r - m_2}{r - l} = \frac{r - l + l - m_2}{r - l} = 1 - \frac{1}{\varphi}$임에 유의하십시오. 이를 대입하고 $\varphi$를 곱하면 다음 방정식을 얻습니다:

$\varphi^2 - \varphi - 1 = 0$

이는 잘 알려진 황금 분할 방정식입니다. 이를 풀면 $\frac{1 \pm \sqrt{5}}{2}$를 얻습니다. $\varphi$는 양수여야 하므로 $\varphi = \frac{1 + \sqrt{5}}{2}$를 얻습니다. $r = m_2$로 설정하고 $m_2'$이 $m_1$과 일치하기를 원하는 경우에도 같은 논리를 적용하면 마찬가지로 동일한 $\varphi$ 값을 얻습니다. 따라서 $m_1 = l + \frac{r - l}{1 + \varphi}$와 $m_2 = r - \frac{r - l}{1 + \varphi}$로 선택하면, 각 반복에서 이전 반복에 계산한 $f(x)$ 값 중 하나를 재사용할 수 있습니다.

구현

double ternary_search(double l, double r) {
    double eps = 1e-9;              //set the error limit here
    while (r - l > eps) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        double f1 = f(m1);      //evaluates the function at m1
        double f2 = f(m2);      //evaluates the function at m2
        if (f1 < f2)
            l = m1;
        else
            r = m2;
    }
    return f(l);                    //return the maximum of f(x) in [l, r]
}

여기서 eps는 사실 절대 오차입니다(함수의 부정확한 계산으로 인한 오차는 고려하지 않습니다).

r - l > eps라는 기준 대신, 고정된 상수 횟수만큼 반복하는 것을 종료 기준으로 선택할 수 있습니다. 반복 횟수는 요구되는 정확도를 보장하도록 선택해야 합니다. 일반적으로 대부분의 프로그래밍 대회에서 오차 한계는 ${10}^{-6}$이므로 200 - 300회의 반복이면 충분합니다. 또한 반복 횟수는 $l$과 $r$의 값에 의존하지 않으므로, 반복 횟수는 요구되는 상대 오차에 대응합니다.

연습 문제