1. 최장 증가 부분 수열(LIS)의 로그 시간 최적화
기존 $O(N^2)$의 시간 복잡도를 갖는 최장 증가 부분 수열 문제는 세그먼트 트리나 이진 인덱스 트리(BIT), 또는 이분 탐색을 활용하여 $O(N \log N)$으로 단축할 수 있습니다. 각 단계에서 계산된 $DP[i]$ 값을 자료구조에 삽입하고, 현재 값보다 작은 원소들 중 최대 DP 값을 쿼리하는 방식으로 전이 속도를 높입니다.
2. 세그먼트 트리를 이용한 구간 DP 최적화
DP 전이식이 구간에 대한 최댓값, 최솟값 또는 합을 요구하는 경우 세그먼트 트리를 도입하여 $O(N)$의 전이를 $O(\log N)$으로 개선할 수 있습니다.
[예제] 연속 구간 분할 문제
길이가 $n$인 배열 $a$를 합이 $m$ 이하가 되는 연속된 구간들로 나눌 때, 각 구간의 최댓값들의 합을 최소화하는 문제입니다.
전이식: $f[i] = \min_{s[i]-s[j] \le m} \{ f[j] + \max(a_{j+1 \dots i}) \}$
단순히 세그먼트 트리로 관리하기 까다로운 이유는 $\max$와 $\min$이 공존하기 때문입니다. 하지만 $a_i$가 추가될 때 영향을 받는 $g_j = \max(a_{j \dots i})$의 범위는 스택을 이용해 찾을 수 있는 '자신보다 큰 이전 원소의 위치'까지입니다. 이를 통해 세그먼트 트리에서 $f[j]$와 $g_{j+1}$의 합을 추적하며 구간 업데이트와 쿼리를 수행합니다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const long long INF = 1e18;
const int MAX = 100005;
struct Node {
long long f_val, sum_val, lazy;
} tree[MAX << 2];
void pull(int node) {
tree[node].f_val = min(tree[node * 2].f_val, tree[node * 2 + 1].f_val);
tree[node].sum_val = min(tree[node * 2].sum_val, tree[node * 2 + 1].sum_val);
}
void push(int node) {
if (tree[node].lazy == 0) return;
long long v = tree[node].lazy;
tree[node * 2].lazy = tree[node * 2 + 1].lazy = v;
tree[node * 2].sum_val = tree[node * 2].f_val + v;
tree[node * 2 + 1].sum_val = tree[node * 2 + 1].f_val + v;
tree[node].lazy = 0;
}
void update_max(int node, int start, int end, int l, int r, long long val) {
if (l <= start && end <= r) {
tree[node].lazy = val;
tree[node].sum_val = tree[node].f_val + val;
return;
}
push(node);
int mid = (start + end) / 2;
if (l <= mid) update_max(node * 2, start, mid, l, r, val);
if (r > mid) update_max(node * 2 + 1, mid + 1, end, l, r, val);
pull(node);
}
void update_dp(int node, int start, int end, int idx, long long val) {
if (start == end) {
tree[node].f_val = val;
tree[node].sum_val = val + tree[node].lazy;
return;
}
push(node);
int mid = (start + end) / 2;
if (idx <= mid) update_dp(node * 2, start, mid, idx, val);
else update_dp(node * 2 + 1, mid + 1, end, idx, val);
pull(node);
}
long long query(int node, int start, int end, int l, int r) {
if (l > r || l > end || r < start) return INF;
if (l <= start && end <= r) return tree[node].sum_val;
push(node);
int mid = (start + end) / 2;
return min(query(node * 2, start, mid, l, r), query(node * 2 + 1, mid + 1, end, l, r));
}
3. 누적 합 및 결합 법칙을 통한 최적화
DP 상태 전이에서 특정 변수가 독립적으로 계산되거나, 접미사/접두사의 합 형태로 나타날 경우 식을 재구성하여 복잡도를 낮출 수 있습니다. 예를 들어, 3중 루프 형태의 DP에서 내부 루프가 이전 상태의 특정 구간 합만을 필요로 한다면, 누적 합 배열을 미리 계산하여 차수를 하나 줄이는 것이 가능합니다.
4. 결정 단조성(Decision Monotonicity) 최적화
최적의 선택을 하는 지점(결정점) $opt[i]$가 $i$의 증가에 따라 단조 증가하는 성질을 가질 때 사용할 수 있습니다. $f[i] = \min_{j < i} \{ f[j] + w(j, i) \}$ 형태에서 $w$가 사각부등식(Quadrangle Inequality)을 만족하면 결정 단조성이 성립합니다.
이 기법은 주로 '분할 정복 최적화' 또는 '이분 탐색과 큐를 이용한 방법'으로 구현됩니다. 후자의 경우, 특정 결정점이 최적에 해당하는 구간 $[l, r]$을 삼원조 $(j, l, r)$ 형태로 관리하여 큐에 유지합니다.
struct Decision {
int pos, l, r;
};
void compute_monotone_dp(int n) {
vector<Decision> q;
q.push_back({1, 1, n});
for (int i = 2; i <= n; i++) {
// 큐에서 현재 i에 해당하지 않는 앞쪽 결정점 제거
int idx = lower_bound(q.begin(), q.end(), i, [](const Decision& d, int val) {
return d.r < val;
}) - q.begin();
// 현재 i에 대한 최적값 계산
dp[i] = calculate(q[idx].pos, i);
// 새로운 결정점 i를 큐에 삽입하며 기존 구간 갱신
int last_valid = n + 1;
while (!q.empty() && is_better(i, q.back().l, q.back().pos)) {
last_valid = q.back().l;
q.pop_back();
}
if (!q.empty()) {
int split = find_split_point(q.back(), i);
if (split <= q.back().r) {
last_valid = split;
q.back().r = split - 1;
}
}
if (last_valid <= n) q.push_back({i, last_valid, n});
}
}
5. 비트셋(Bitset)과 무작위성을 결합한 최적화
다차원 DP에서 상태가 불린(boolean) 값인 경우 std::bitset을 사용하여 전이 속도를 워드 크기($\omega$)만큼 향상시킬 수 있습니다. 특히 상태 공간이 매우 큰 경우, 상태의 분포가 특정 영역에 집중된다는 점(예: 무작위 보행에서의 중심 극한 정리)을 이용하여 탐색 범위를 제한하거나 순서를 섞음으로써 평균적인 성능을 극대화할 수 있습니다.
6. 조합론적 모델로의 변환
격자 경로 계산과 같이 특정 DP 전이식이 조합론적 의미를 갖는 경우, 식을 직접 계산하는 대신 조합수($nCr$)나 포함-배제의 원리를 적용하여 $O(1)$ 또는 $O(N)$에 해결할 수 있습니다. $k$번의 누적 합 계산은 $n$개의 공을 $k$개의 상자에 나누어 담는 문제와 동일한 모델로 치환될 수 있습니다.