삼분탐색 (알고리즘)

안녕하세요. 오늘은 삼분탐색을 할 거예요.

삼분탐색이란?

삼분탐색은 볼록함수, 즉 증가하다가 감소하는 함수 또는 감소하다가 증가하는 함수에서 최대/최소를 찾을 때 씁니다.

알고리즘만 설명하자면
1. 범위 [left,right]가 주어진다.
2. 범위를 삼등분해서 [left,llr],[llr,lrr],[lrr,right]로 나눈다.
3. 최솟값을 구하려면 f(llr)<=f(lrr)인 경우 [lrr,right]는 범위가 제외된다. 반대로 f(llr)>f(lrr)인 경우 [left,llr]은 범위가 제외된다. 최댓값을 찾을때에는 부등호만 반대로 하면 된다.
4. right-left가 3이상이면 계속 하고 아니면 끝낸다.
5. 이분탐색과 달리 값이 아닌 범위가 주어지므로 남은 1개 혹은 2개의 값들중 최소/최대를 구하면 된다.

이해가 안되면 간단히 이차함수 또는 그냥 볼록한 함수를 그려서 생각해보면 됩니다.

삼분탐색 조건

생각보다 조건이 까다롭습니다.
최솟값이 아닌데 평평한 구간이 있는 함수? -> 불가능

볼록하고 최솟값이 아닌 값에서 평평하지 않은, 즉 삼분탐색 조건에 만족하는 함수를 유니모달(unimodal)하다고 합니다. unimodal한 함수의 특징은 아래로 볼록한 함수끼리의 max값을 표현한 새로운 함수도 unimodal하고 반대로 위로 볼록한 함수끼리의 min값을 표현한 새로운 함수도 unimodal합니다. 또한 볼록한 방향이 같으면 더해도 unimodal합니다.

삼분탐색 코드

간단히 이 문제 코드를 올리겠습니다.

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

ll junbotdae[101010] = { 0 }, N;
ll val(ll x) //간격이 x일때의 최솟값
{
    ll ans = 0;
    for (ll i = 0; i < N; i++)
        ans += abs(i * x - junbotdae[i]);
    return ans;
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll i, left = 0, right = 2e9;
    cin >> N;
    for (i = 0; i < N; i++)
        cin >> junbotdae[i];

    while (right - left >= 3)
    {
        ll llr = (left * 2 + right) / 3, lrr = (left + right * 2) / 3;
        if (val(llr) <= val(lrr)) right = lrr;
        else left = llr;
    }

    ll ans = 1e18;
    for (i = left; i <= right; i++)
        ans = min(ans, val(i));

    cout << ans;
}

감사합니다.