39. Ternary Search

삼분 탐색(Ternary Search)은 어떤 데이터가 극값 하나를 가지는 형태로 나열되어 있을 때 그 극값을 빠르게 찾을 수 있는 탐색 방법이다. 일반적으로 데이터 자체를 삼분 탐색으로 찾을 일은 거의 없고, 어떤 함수의 개형이 특정 구간에서 볼록함수로 나타내어질 때 극값을 찾기 위해 삼분 탐색이 사용되는 경우가 많다. 삼분 탐색을 삼진 탐색이라고 하는 경우도 있으나 삼진 탐색이라는 용어는 잘 쓰이지 않는 것으로 보인다.

 

다음과 같은 함수 $f(x)$의 극값을 찾는 상황을 생각해 보자. $f(x)$가 극값을 갖는 $x$의 범위를 알고 있고, 임의의 $x$에 대해 $f(x)$를 구할 수 있다고 가정한다.

이 함수는 주어진 구간에서 하나의 극값을 가지므로 삼분 탐색을 사용할 수 있다. 먼저 주어진 구간을 셋으로 분할한다.

여기서 $f(a)$와 $f(b)$를 비교하면 세 구간 중 극값이 존재할 수 없는 구간을 알아낼 수 있다. 위로 볼록한 함수를 기준으로, 이 그림에서는 $f(a)$가 $f(b)$보다 약간 더 크다. 따라서 $f(x)$가 극값을 갖는 $x$는 $b$보다 클 수 없다. 만약 $f(a) > f(b)$이고 $f(x)$가 $x > b$인 구간에서 극값을 갖는다고 가정하면, 이 함수가 주어진 구간에서 극값을 하나만 가지므로 $x < b$인 구간에서 $f(x)$는 증가해야 한다. $f(x)$가 이 구간에서 증가할 경우 $f(a)$는 $f(b)$보다 클 수 없고, 이것은 처음의 가정과 모순이다. 따라서 $f(a) > f(b)$인 경우 $f(x)$는 $x < b$인 구간에서 극값을 갖는다.

 

이와 비슷한 방법으로 $f(a) < f(b)$인 경우 $f(x)$는 $x > a$인 구간에서 극값을 가짐을 확인할 수 있다. 또한 $f(a) = f(b)$인 경우 $f(x)$는 $a < x < b$인 구간에서 극값을 갖게 된다. 함수가 아래로 볼록할 경우에도 비슷하게 적용이 가능하다.

 

따라서 $f(a)$와 $f(b)$의 비교를 통해 극값이 존재할 수 있는 구간의 길이를 줄일 수 있다. 따라서 이 방법을 반복적으로 사용하면서 구간의 크기를 지수적으로 줄여 나갈 수 있다. 만약 $x$가 정수값만 가지거나 이산적으로 존재할 경우 하나의 $x$가 정해지게 되고, $x$가 연속적으로 존재할 수 있을 경우 하나의 $x$가 정해지지 않지만 몇십 번의 반복으로도 구간의 크기가 매우 작아지게 되므로 그렇게 줄어든 구간에서 임의의 $x$를 고르더라도 극값과의 오차가 매우 작아서 일반적으로 적당한 실수 오차가 허용되는 문제를 푸는 데에는 지장이 없다. 허용되는 오차의 범위가 매우 작거나, 반올림을 해서 하나로 결정되는 답을 얻어야 하는 문제의 경우 일반적인 실수 자료형으로 오차를 줄이기 어렵다면 python의 decimal 모듈을 이용하는 것이 좋다.

 

삼분 탐색을 사용하기 전에 주의해야 할 점은 함수의 기울기가 $0$인 구간이 존재하는지의 여부이다. 함수의 기울기가 $0$인 구간이 존재하지 않을 경우(이런 함수를 유니모달(Unimodal)한 함수라고 한다)에는 문제없이 삼분 탐색을 사용할 수 있었다. 하지만 함수의 기울기가 $0$인 구간이 존재하고 그때의 함수값이 극값이 아니라면 삼분 탐색을 사용할 수 없다. 다음과 같은 함수를 생각해 보자. $f(a) = f(b)$이다.

함수의 기울기가 $0$인 부분이 존재하지 않을 경우 $f(x)$는 $a < x < b$인 구간에서 극값을 갖지만 이 경우에는 그렇지 않다. 이 그래프의 좌우를 뒤집은 그래프도 나타날 수 있다는 것을 생각하면 별다른 정보가 없을 경우 $f(a)$와 $f(b)$의 대소 비교만으로는 극값이 존재하는 구간을 줄일 수 없음을 알 수 있다.

 

반면 함수의 기울기가 $0$인 구간이 극값(사실 이런 경우는 극값이라고 말하기가 약간 애매하다)에서만 존재하는 경우에는 삼분 탐색을 사용할 수 있다. 다음과 같은 함수를 생각해 보자. 역시 $f(a) = f(b)$이다.

이때는 단순히 극값이 존재할 수 있는 구간을 줄여나가도 된다.

 

삼분 탐색에서는 구간이 셋으로 나뉜 다음 양 끝 구간 중 한쪽이 잘려나가는 과정이 반복된다. 또한 각각의 구간의 크기는 $0$보다 크기만 하면 되기 때문에, 구간을 나눌 때는 가운데 구간의 길이를 최대한 줄이고 양 끝 구간의 길이는 비슷하게 하는 것이 좋다. 따라서 $x$가 정수값을 갖는 경우 가운데 구간의 길이는 $1$로 두는 것이 유리하다.

int a, b;
while(l < r)
{
    a = (l + r) / 2;
    b = a + 1;
    if(f(a) > f(b))r = b;
    else l = a;
}

 

흔히 구간을 $\frac{1}{3}$씩 나누는 방식으로 많이 구현하고 원래 이 블로그에서도 그렇게 구현하는 것을 소개했는데, 위와 같이 구현하면 한 차례에 구간의 길이가 절반으로 줄기 때문에 반복 횟수가 줄어들고, 시간복잡도를 계산할 때 상수가 작아지는 효과가 있다.

 

삼분 탐색 역시 이분 탐색과 마찬가지로 무한루프가 생기지 않도록 구현하는 것이 중요하다. 위에 나온 코드는 $x$가 정수값을 갖는 함수 $f(x)$의 극대값을 찾는 코드인데, $r - l$이 $1$이나 $2$일 때 문제가 생긴다. while문의 종료 조건을 다음과 같이 수정하면 일단 무한루프가 생기는 문제는 해결할 수 있다.

int a, b;
while(l + 2 < r)
{
    a = (l + r) / 2;
    b = a + 1;
    if(f(a) > f(b))r = b;
    else l = a;
}

 

하지만 극대값을 완전히 찾은 것이 아니기 때문에 가능한 함수값을 계산해서 비교하는 과정이 필요하다. $f(l)$과 $f(r)$, 그리고 $r - l = 2$인 경우 $f(l + 1)$까지가 비교 대상이 되며, 이중 최대값이 함수의 극대값이 된다.

 

$x$가 연속적으로 존재할 수 있는 함수의 경우는 대부분 무한루프를 고려하지 않아도 된다. 하지만 이번에는 가운데 구간의 길이가 새로운 고려 대상이 된다. 이때는 가운데 구간의 길이를 전체 구간에 대한 비율로 정해서 맞추는 것이 비교적 간단한 해결책이 된다. 가운데 구간의 길이를 전체 구간의 $2\%$로 둘 경우 다음과 같이 구현할 수 있다.

double a, b;
while(l + 1e-6 < r)
{
    a = 0.51 * l + 0.49 * r;
    b = 0.49 * l + 0.51 * r;
    if(f(a) > f(b))r = b;
    else l = a;
}

때때로 이 코드에서 구한 극값과 실제 극값과의 오차는 상당히 커질 수 있다. 코드를 다음과 같이 수정할 경우 오차 문제는 대부분 해결할 수 있다.

double a, b;
while(l + 1e-9 < r)
{
    a = 0.51 * l + 0.49 * r;
    b = 0.49 * l + 0.51 * r;
    if(f(a) > f(b))r = b;
    else l = a;
}

하지만 이번에는 $l$과 $r$이 어느 정도 이상으로 커지면 부동소수점 오차로 인해 소수 부분 일부가 잘려나가면서 무한루프가 발생할 수 있다는 문제점이 생긴다. 그래서 $x$가 실수값을 가질 수 있는 경우의 반복문은 보통 아래와 같이 일정한 횟수만큼 반복하는 식으로 구현한다.

double a, b;
for(int i = 0; i < 100; i++)
{
    a = 0.51 * l + 0.49 * r;
    b = 0.49 * l + 0.51 * r;
    if(f(a) > f(b))r = b;
    else l = a;
}

$\frac{51}{100}^{100} =$ 약 $5.715 \times 10^{-30}$이므로 오차 문제는 사실상 없으며 반복문의 종료도 보장할 수 있다.

 

[연습문제]

 

BOJ 8986. 전봇대 (Platinum V)

$x_0 = 0$으로 고정되어 있기 때문에 전봇대들의 간격이 모두 같을 경우 $x_i = ki$ ($k$는 양의 정수) 이다. 이때 원래 상태에서 전봇대들의 간격이 모두 $k$가 되도록 할 때 전봇대의 이동 거리의 최솟값을 $f(k)$라고 하면 $f(k)$는 아래로 볼록한 함수이며, $f(k)$의 극소값을 삼분 탐색으로 구할 수 있다.

 

삼분 탐색은 사용되는 빈도는 높지 않지만 적절하게 잘 사용하면 미분이 필요한 문제를 미분 없이 해결할 수 있는 경우도 존재한다.

 

→ solved.ac tag: ternary_search