컨벡스 헐 트릭 ( Convex Hull Trick )

Table of Contents

개요

변환

1차 함수 집합 관리

최소값 찾기

문제

1. 개요

 컨벡스 헐 트릭 ( Convex hull trick, Convex hull optimization)은 동적 계획법에서 특정 형태의 점화식이 사용되었을 시 시간복잡도를 획기적으로 줄여주는 기법입니다. DP 관계식을 아래와 같이 정리 가능할 때 사용할 수 있습니다.

 D[i] 는 어차피 j와 상관이 없기 때문에 상수처럼 취급하고, (i에 대한 함수) * (j에 대한 함수) + (j에 대한 함수) 으로 생각하면 쉽게 컨벡스 헐 트릭의 모양이란 걸 알 수 있습니다.

2. 변환

 우선 각각의 j 에 대해 다음과 같은 함수를 생각해봐야 합니다.

 여기에서 j 는 정해진 상수이므로 B[j], C[j] 또한 상수입니다. 그러므로 위의 함수는 y = ax+b 꼴의 1차 함수입니다. 이제 원래 식을 변형해 보면, 

 여기에서 각각의 i에 대해 D[i]는 상수입니다. 그러므로 DP[i]를 구하기 위해 우리가 구해야 할 것은 하나 뿐입니다.

 즉, 1차 함수 여러 개와 특정 값 x가 주어졌을 때, f(x)들 중 최솟값을 찾으면 되는 형태로 문제를 바꿀 수 있습니다. ( x = A[i] ) 이 최소값을 찾고 나면 D[i]를 더해주는 것으로 쉽게 DP[i]를 구할 수 있습니다.

3. 1차 함수 집합 관리

 컨벡스 헐 트릭의 핵심 중 하나는 DP[i]를 구하는데 필요한 일차함수들을 효율적으로 관리하는 것입니다. 일단 보통의 DP 상황처럼 DP[0]부터 DP[N]까지 순서대로 구한다고 해보면, 아래의 순서를 따라가게 됩니다.

step 1) DP[0] 계산

step 2) 스택에 f(x) = B[0]*x + C[0] 함수 추가

step 3) f(A[1]) 중 최솟값 찾기 (DP[1] 계산)

step 4) 스택에 f(x) = B[1]*x + C[1] 함수 추가

step 5) f(A[2]) 중 최솟값 찾기 (DP[2] 계산)

step 6) 스택에 f(x) = B[2]*x + C[2] 함수 추가

...

 이때 개요의 점화식에 있던 조건 (B[i-1]>=B[i])에 의해, 추가되는 직선의 기울기가 점점 감소하는 형태라는 것을 알 수 있습니다. 이 점을 공략하여, 함수들의 집합을 스택으로 관리하면 효율적으로 필요 없는 함수들을 잘라내면서 집합을 유지할 수 있습니다. 여기에서 필요없는 함수란 어떠한 x 에 대해서도 f(x)가 최솟값이 될 일이 없는 함수들을 의미합니다. 스택을 관리할 때 이런 함수들을 없애고, 기울기의 단조 감소를 유지해야 추후에 해야 할 최솟값 찾기를 빠르게 수행할 수 있습니다.

* 스택에 함수 추가하기

 현재 위에 그려진 함수들이 스택에 저장되어 있다고 머릿속에 그려보겠습니다. 이 중에서 필요없는 함수는 없습니다. 그러면 기울기는 나중에 들어온 함수일수록 작기 때문에 제일 끝의 함수가 top에 저장되어 있을 것입니다. 이 때, 함수를 하나 추가한다면 다음과 같은 두 가지의 경우의 수가 나오게 됩니다.

 이 두 가지의 경우는 (top에 저장된 함수) 와 (나머지 두 함수) 들의 교점의 x 좌표를 대소 비교 함으로서 구별할 수 있습니다.

왼쪽의 경우)

 top에 저장된 함수가 필요 없어졌기 때문에 일단 삭제한 후, (더 이상 top에 저장된 함수는 최솟값이 될 수 없습니다.)

 오른쪽의 경우가 나오거나 혹은 스택에 함수가 하나 남을 때까지 위의 작업을 반복합니다.

오른쪽의 경우 or 스택에 함수가 하나 이하로 남아서 비교할 게 없는 경우)

 새로운 함수를 스택에 push 하고 마무리하면 됩니다.

 일차 함수의 특징과 기울기가 점점 감소한다는 조건에 의해 이 추가 과정을 반복하면, 스택에 필요한 함수들만 기울기 순서대로 저장됨을 알 수 있습니다. 컨벡스 헐 알고리즘을 아시는 분들은 이미 눈치채셨겠지만, 이 1차 함수를 관리하는 과정은 컨벡스 헐 알고리즘과 굉장히 유사합니다.

4. 최소값 찾기

 이제 특정 x 값, 즉, A[i]에서 함수 값이 가장 낮은 함수를 스택에서 찾으면 DP[i]를 구할 수 있습니다. 이는 parametric search로 가능합니다.

 위와 같이 A[i]가 j 번째 함수와 j+1 번째 함수 교점의 x 좌표보다 크다면, 찾는 함수가 j 번째 이후에 있음을 알 수 있습니다다. ( j 번째 이전의 함수에서 나오는 값은 모두 j+1번째 함수에서 나온 값보다 큼을 증명할 수 있습니다.) 반대로 A[i]가 작다면 찾는 함수는 j+1 번째 이전에 있습니다.

 이를 이용해 parametric search로 최솟값을 내뱉는 함수를 찾으면 O(log N)에 최소값을 찾을 수 있습니다. (만일 A[i]가 증가 함수라면 two pointer랑 비슷한 느낌으로 전체 시간 복잡도를 O(N log N)에서 O(N)으로 줄이는 것도 가능합니다. 이는 아래의 코드를 참고해주시기 바랍니다.)

 아직 컨벡스 헐 트릭을 어떻게 적용시켜야 할지 감이 안 잡히신다면 문제 0 번 특공대 문제와 풀이를 꼭 읽어보시는 걸 추천합니다.

// code by RiKang, weeklyps.com
#include <stdio.h>
#include <algorithm>
#include <vector>
#define PII pair<long long, long long>
 
using namespace std;
 
const int N=1000000;
 
struct line{  // y = a*x + b
    long long a,b;
};
 
struct convexhull_trick{
    int s=0,e=0;
    int idx[N+5];
    line deq[N+5];
    double cross(int a, int b) {
        return 1.0 * (deq[a].b - deq[b].b) / (deq[b].a - deq[a].a);
    }
    void insert(line v,int line_idx){
        deq[e] = v;
        idx[e] = line_idx;
        while(s+1<e && cross(e - 2, e - 1) > cross(e - 1, e)){
            deq[e-1] = deq[e];
            idx[e-1] = idx[e];
            e--;
        }
        e++;
    }
    PII query(long long x){  // query가 증가수열일 경우
        while(s+1<e && deq[s+1].b - deq[s].b >= x * (deq[s].a - deq[s+1].a))
            s++;
        return PII(deq[s].a*x+deq[s].b,idx[s]);
    }
    PII query2(long long x){ // 일반 query
        int l = 0, r = e - 1;
        while (l != r) {
            int m = (l + r) / 2;
            if (cross(m, m + 1) <= x) l = m + 1;
            else r = m;
        }
        return PII(deq[l].a*x+deq[l].b,idx[l]);
    }
    void clear(){s = e = 0;}
}cht;

5. 문제

(0). [BOJ 4008] 특공대

풀이 링크

(1). [BOJ 10067] 수열 나누기

※ 본문의 코드들은 C++ 17 환경에서 작성되었습니다.

※ 문의 : rikang93@gmail.com