[Algorithm/C++] 삼분 탐색(Ternary search) (백준 8986 전봇대)

1. 알고리즘 설명

삼분 탐색은 어떤 unimodal한 그래프에서, 최댓값 or 최솟값을 $log$ 시간 안에 찾아주는 알고리즘입니다.

이때 unimodal이란, uni(하나의) + mode(봉우리)라는 뜻으로, 이차함수 그래프처럼 봉우리가 하나인 그래프를 의미합니다. (bimodal은 'W'모양의 그래프처럼 봉우리가 두 개, multimodal은 봉우리가 여러 개인 경우입니다)

이분 탐색과 비교하자면, 이분 탐색은 함수의 값이 '/', '\'모양처럼 쭉 단조 증가 or 단조 감소하는 경우에만 사용할 수 있고,

탐색하려는 구간의 길이가 $n$일 때, 매 탐색 과정에서 구간이 1/2 크기로 줄어들기 때문에 시간복잡도는 $log_2(n)$입니다.

 

삼분 탐색은 함수의 값이 'V'모양처럼 쭉 단조 증가하다가, 어느 순간부터 쭉 단조 감소하는 경우에만 사용할 수 있고,

탐색하려는 구간의 길이가 n일 때, 매 탐색 과정에서 구간이 2/3 크기로 줄어들기 때문에 시간복잡도는 $log_{3/2}(n)$입니다. 어차피 $Big-O$ 표기법에서 $log$의 밑은 상수의 곱으로 떼어낼 수 있기 때문에, 두 탐색의 시간복잡도는 $log(n)$으로 같습니다.

삼분 탐색 구현과 자세한 설명은 맨 아래 코드 설명의 'ternary_search()' 함수에 대한 설명을 참고하시면 됩니다.

 

2. 예제 문제

백준8986 - 전봇대

8986번: 전봇대

 

3. 문제 풀이

$x_0$전봇대의 위치가 0으로 고정이므로, 두 전봇대 사이의 거리를 $d$라고 한다면, $i$번째 전봇대의 도착 위치는 $d*i$로 정해집니다.

$i$번째 전봇대의 초기 위치를 $x[i]$, $g(i) = i$번째 전봇대가 이동해야 할 거리라 하면, $g(i)$는 아래와 같습니다.

$$g(i)= \begin{cases}-d*i+x[i], & \mbox{if} (-d*i<=x[i]) \\d*i-x[i], & \mbox{otherwise} \end{cases}$$

도착 위치가 초기 위치보다 왼쪽에 있는 경우, $g(i)$는 기울기가 음수인 일차함수의 형태고,

도착 위치가 초기 위치보다 오른쪽에 있는 경우, $g(i)$는 기울기가 양수인 일차함수의 형태입니다.

$d$가 엄청 작을 때 $g(i)$ 의 기울기는 음수일 것이고, (d가 작을 때, 단조 감소)

$d$가 엄청 클 때 $g(i)$ 의 기울기는 양수일 것입니다. (d가 클 때, 단조 증가)

따라서 $g(i)$는 unimodal 그래프이고, 우리가 구해야 할 값 $f(d) = \sum_{i=1}^{n} g(i)$라고 하면, unimodal 그래프의 합 역시 unimodal하다는 특성 때문에 $f(d)$역시 unimodal합니다. 따라서 $d$에 대해 삼분 탐색을 해주면 됩니다.

 

4. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<ll> x;
ll f(ll d){//두 전봇대 사이의 거리가 d일 때, 이동 거리의 합
    ll ret=0;
    for(ll i=0;i<x.size();i++)
        ret+=abs(x[i]-d*i);
    return ret;
}

ll ternary_search(){
    ll l=1,r=1e9,lmid,rmid;
    while(l+3<r){
        lmid=(l+l+r)/3,rmid=(l+r+r)/3;
        if(f(lmid)<f(rmid))r=rmid;
        else l=lmid;
    }
    ll ans=LLONG_MAX;
    for(ll i=l;i<=r;i++)ans=min(ans,f(i));
    return ans;
}

int main(){
    int n;scanf("%d",&n);
    x.resize(n);
    for(int i=0;i<n;i++)scanf("%lld",&x[i]);
    printf("%lld",ternary_search());
    return 0;
}

 

5. 코드 설명

ll f(ll d){//두 전봇대 사이의 거리가 d일 때, 이동 거리의 합
    ll ret=0;
    for(ll i=0;i<x.size();i++)
        ret+=abs(x[i]-d*i);
    return ret;
}

문제 풀이에서 $g(x)$에 해당하는 부분을, 4번째 줄처럼 간단하게 표현할 수 있습니다. 

ll ternary_search(){
    ll l=1,r=1e9,lmid,rmid;
    while(l+3<r){
        lmid=(l+l+r)/3,rmid=(l+r+r)/3;
        if(f(lmid)<f(rmid))r=rmid;
        else l=lmid;
    }
    ll ans=LLONG_MAX;
    for(ll i=l;i<=r;i++)ans=min(ans,f(i));
    return ans;
}

초기에 $l$을 엄청 작은 값, $r$을 엄청 큰 값으로 잡으면, $l, r$은 'V'자 그래프($f(d)$)의 양 끝에 있는 상황이고, 극값을 향해 미끄러져 내려오는 상황이라고 생각할 수 있습니다.

이제 $l, r$의 1/3, 2/3 지점을 각각 $lmid, rmid$로 잡습니다.

만약 $f(lmid)<f(rmid)$ 라면, $rmid$가 아직 덜 내려온 겁니다. $[rmid\sim r]$에는 $f(lmid)$값보다 작은 값이 없습니다. 따라서 $r=rmid$로 오른쪽 1/3구간을 날려주시면 됩니다.

반대의 경우에는 $[l\sim lmid]$에는 $f(rmid)$값보다 작은 값이 없는 경우이고, $l=lmid$로 왼쪽 1/3구간을 날려줍시다.

이때 주의해야 할 점이 있는데, 이분탐색때와 같이 $while(l<r)$ 로 코드를 짜면 무한 루프에 빠질 수 있습니다.

예를 들어, $l=2, r=4 => lmid=2, rmid=3$ 인 경우에 $l=lmid$ 를 반복한다면, $l$이 갱신되지 않아 $l<r$ 조건을 계속 만족합니다.

따라서 위와 같이 적당한 $[l\sim r]$구간에서 멈추고 직접 찾아주셔야 합니다.