이제부터는 여러 가지 DP 최적화(DP Optimization) 방법에 대해서 알아보기로 한다. DP 최적화는 DP 식이 특수한 형태로 존재할 때 그 식의 특성을 이용해서 시간복잡도를 줄이는 기법들을 의미한다. 그중 가장 먼저 살펴볼 내용은 컨벡스 헐 트릭(Convex Hull Trick, CHT)이며, DP 식이 다음과 같은 형태일 때 사용할 수 있다($\min$ 대신 $\max$가 들어갈 수도 있고 이 경우 $a_i$의 부등호 방향이 반대로 변함):
$$S_i = \min_{j < i}(a_j \times b_i + S_j)$$
$$a_1 > a_2 > \ldots > a_{n - 1} > a_n$$
이 식에서 $S_n$을 구하는 것이 목표라고 하면, $S_n$을 구하기 위해서는 $S_1$부터 $S_{n - 1}$까지를 모두 알아야 하는데 $S_1$부터 $S_{i - 1}$까지를 알고 있는 상태에서 $S_i$를 나이브하게 구하는 데는 $O(i)$ 시간이 걸리기 때문에 나이브한 방법으로 $S_1$부터 $S_n$까지를 구하면 $O(n^2)$ 시간이 걸린다. 이때 CHT를 이용하면 시간복잡도를 $O(n \lg n)$으로 줄일 수 있다. 어떻게 하는지 살펴보자.
위에 나온 식을 살펴보면 일차식의 형태로 되어 있다는 것을 알 수 있다. 즉, $a = a_j, b = S_j, x =b_i, y = S_i$라고 하면 위 식은 $y = ax + b$라는 일차식의 기본 형태가 되고, $1 \le j < i$를 만족하는 $(i - 1)$개의 $j$ 각각에 일차식 하나가 대응한다고 생각하면 이 $(i - 1)$개의 일차식 중 $x = b_i$일 때 값이 최소가 되는 함수를 찾아야 한다. 그리고 $j$가 증가할수록 일차식의 기울기가 감소한다는 제한이 주어졌다. 여기서 일차식들의 그래프를 그려 보면 다음과 같이 된다.
여기서 함수값이 최소가 되는 부분들을 표시하면
볼록 껍질 형태가 나타난다. 이 트릭의 이름이 이렇게 붙은 이유이기도 하다.
$j$가 증가할수록 함수의 기울기는 감소하므로 이 볼록 껍질을 다각형으로 본다면 $x$축을 제외하고 나머지 변들을 이루는 일차식은 $j$가 증가하는 순서대로 나타난다.
위 그림에는 $7$개의 일차식이 있다. 여기에 여덟 번째 일차식을 추가하는 방법을 알아보자. 이때 $a_8 = -2.9, b_8 = 20$이고, $S_8$은 알아내야 하는 값인데 $S_8$을 알아내려면 이미 있는 일차식들 중 $x = 20$일 때 $y$의 최솟값을 찾아야 한다.
위 그림을 그리기 위해 사용된 일차식들은 다음과 같다.
$$L_1: y = 6x$$
$$L_2: y = 1.7x + 14$$
$$L_3: y = 0.6x + 25$$
$$L_4: y = 0.1x + 42$$
$$L_5: y = -0.4x + 66$$
$$L_6: y = -0.7x + 85$$
$$L_7: y = -1.9x + 191$$
그리고 이 일차식들 중 같은 $x$에 대해 $y$가 최소가 되는 점들, 즉 위의 그림에 있는 볼록 껍질을 식으로 나타내면 이렇게 된다.
$$y = \begin{cases}6x & (x < x_1) \\ 1.7x + 14 & (x_1 \le x < x_2) \\ 0.6x + 25 & (x_2 \le x < x_3) \\ 0.1x + 42 & (x_3 \le x < x_4) \\ -0.4x + 66 & (x_4 \le x < x_5) \\ -0.7x + 85 & (x_5 \le x < x_6) \\ -1.9x + 191 & (x_6 \le x)\end{cases}$$
$x_1$부터 $x_6$까지는 두 일차함수의 교점을 구하는 방식으로 각각 상수 시간에 구할 수 있다. 그러면 $x = 20$이 어느 구간에 속하는지를 이분 탐색으로 찾을 수 있다. 여기서는 $x_2 = 10, x_3 = 34$이므로 $x = 20$일 때 $y$의 최솟값은 $0.6 \times 20 + 25 = 37$이다.
따라서 새로 추가할 일차식은 $L_8: y = -2.9x + 37$이고 좌표평면에 추가하면 다음과 같다.
이 일차식을 추가했을 때 더이상 최솟값이 되는 구간이 없는 일차식들은 볼록 껍질에서 제거해야 한다. 이 예시의 경우 오른쪽의 $5$개 일차식이 제거되고 그 다음 일차식은 일부가 잘린다. 그림으로 나타내면 다음과 같다.
실제로 구현할 때는 std::vector 등으로 직선들을 관리하면 된다. 직선을 추가할 때 마지막 교점에서 vector의 마지막 일차함수와 새로 추가하는 일차함수 중 어느 함수값이 작은지 확인하고 새로 추가하는 일차함수의 함수값이 더 작거나 같을 경우 마지막 일차함수를 vector에서 제거한다. 헷갈리는 부분이 있다면 구현 예시를 통해 이해하자.
#import<bits/stdc++.h>
using namespace std;
struct Line{int a, b; double p;}; // y = ax + b, 이 일차식이 최솟값이 되는 구간은 x = p에서 시작함
int a[100005], b[100005], s[100005];
vector<Line> v;
int getIdx(int x)
{
int bx = 0, by, bz = v.size() - 1;
for(;bx < bz;)
{
by = bx + bz + 1 >> 1;
if(v[by].p > x)bz = by - 1;
else bx = by;
}
return bx;
}
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)cin >> a[i];
for(int i = 1; i <= n; i++)cin >> b[i];
v.push_back({a[1], 0, -INF}); // 첫 번째 일차식은 따로 처리해 준다
for(int i = 2; i <= n; i++)
{
int id = getIdx(b[i]);
s[i] = v[id].a * b[i] + v[id].b;
for(;;)
{
double px = v.back().p;
double v1 = v.back().a * px + v.back().b, v2 = a[i] * px + s[i];
if(v1 >= v2)v.pop_back(); // 더이상 필요 없는 일차식 제거하기
else break;
}
v.push_back({a[i], s[i], (double)(s[i] - v.back().b) / (v.back().a - a[i])}); // 새 일차식 추가
}
}첫 번째 일차식을 따로 처리하는 이유는 vector에 아무것도 없을 때 이분 탐색으로 일차식을 찾으려고 하면 에러가 발생하기 때문이다. 또한 $b_i$가 단조증가하는 순서대로 입력되는 경우 $x = b_i$에서 값이 최소인 일차함수를 찾기 위해 이분 탐색을 사용하지 않아도 그 함수의 포인터를 관리하는 등의 방식으로 상수 시간(amortized)에 일차함수를 찾을 수 있다. 또한 위 코드에서는 쉬운 이해를 위해 double형을 사용했지만 분수 형태를 관리하게 하면 실수 오차 없이 구현할 수 있다. 이에 대한 구현은 여기서는 다루지 않았다.
[연습문제]
BOJ 13263. 나무 자르기 (Platinum II)
CHT 기본 문제로 가장 많이 알려진 문제이다. $i$번째 나무의 높이를 $0$으로 만드는 최소 비용을 $dp[i]$라고 하면 DP 식이 CHT를 적용할 수 있는 형태가 된다.
내적 식을 아무 변수 하나로 나누면 연립일차식을 일차식의 형태로 변형할 수 있고, 이 구조에서 CHT를 적용할 수 있게 된다. DP라고 보기에는 약간 애매한 감이 있지만 CHT의 핵심은 여러 일차식 중 함수값이 최소나 최대가 되는 지점을 빠르게 찾을 수 있다는 것이므로 이 문제도 그렇게 풀 수 있다. 약간 머리를 쓰면 조금 다르게 풀 수도 있는 것 같다.
누적 합을 이용해 식정리를 하면 DP 식이 CHT를 적용할 수 있는 형태가 된다.
'Algorithm > J. Optimization' 카테고리의 다른 글
| 196. Counting Points in Triangle (0) | 2024.07.12 |
|---|---|
| 195. Small to Large Technique (0) | 2024.07.11 |
| 194. Optimization Intro (2) | 2024.07.08 |
