동적 계획법(DP) 최적화 기법의 이해와 적용

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$개의 상자에 나누어 담는 문제와 동일한 모델로 치환될 수 있습니다.

태그: DynamicProgramming SegmentTree DecisionMonotonicity bitset AlgorithmOptimization

11월 1일 20:58에 게시됨