[C++로 배우는 알고리즘과 자료구조 심화] Day 16: DP 최적화 기법 (Convex Hull Trick, Divide and Conquer Optimization)

DP 최적화 기법

동적 계획법(DP)은 많은 문제를 효율적으로 해결할 수 있는 강력한 도구입니다. 그러나 때로는 DP의 시간 복잡도를 더 최적화할 필요가 있습니다. 오늘은 두 가지 주요 DP 최적화 기법에 대해 학습하겠습니다: Convex Hull Trick과 Divide and Conquer Optimization.

Convex Hull Trick

Convex Hull Trick은 주로 함수 (y = ax + b)의 최솟값이나 최댓값을 효율적으로 찾는 문제에서 사용됩니다. 이 기법은 선형 함수들의 집합을 유지하고, 각 쿼리마다 특정 (x)에서의 최소 (y) 또는 최대 (y)를 빠르게 계산합니다.

문제 예시

다음과 같은 문제를 고려해봅시다:

• 주어진 선형 함수들의 집합 ({y = a_1x + b_1, y = a_2x + b_2, \ldots, y = a_nx + b_n})에서, 주어진 (x)에 대해 최소 (y)를 찾으세요.

Convex Hull Trick 구현

#include <iostream>
#include <deque>
#include <vector>

struct Line {
    long long a, b;
    double intersect(const Line& other) const {
        return (double)(other.b - b) / (a - other.a);
    }
};

class ConvexHullTrick {
public:
    void addLine(long long a, long long b) {
        Line newLine = {a, b};
        while (lines.size() >= 2 && newLine.intersect(lines[lines.size() - 2]) <= lines.back().intersect(lines[lines.size() - 2])) {
            lines.pop_back();
        }
        lines.push_back(newLine);
    }

    long long getMin(long long x) {
        while (lines.size() >= 2 && lines[0].a * x + lines[0].b >= lines[1].a * x + lines[1].b) {
            lines.pop_front();
        }
        return lines.front().a * x + lines.front().b;
    }

private:
    std::deque<Line> lines;
};

int main() {
    ConvexHullTrick cht;
    cht.addLine(1, 5);
    cht.addLine(-1, 3);
    cht.addLine(2, 1);

    std::cout << "x = 1에서의 최소 y: " << cht.getMin(1) << std::endl; // 예제 출력

    return 0;
}

Divide and Conquer Optimization

Divide and Conquer Optimization은 동적 계획법의 특정 유형을 분할 정복 전략으로 최적화하는 기법입니다. 이 기법은 점화식 (dp[i][j] = \min_{k < j} (dp[i-1][k] + C[k][j]))을 만족하는 DP 문제에서 사용할 수 있습니다. 여기서 비용 함수 (C[k][j])는 단조 증가 또는 감소하는 성질을 가집니다.

문제 예시

다음과 같은 문제를 고려해봅시다:

• (dp[i][j] = \min_{k < j} (dp[i-1][k] + C[k][j]))

Divide and Conquer Optimization 구현

#include <iostream>
#include <vector>
#include <climits>

void computeDP(std::vector<std::vector<int>>& dp, int i, int l, int r, int optl, int optr, const std::vector<std::vector<int>>& cost) {
    if (l > r) return;

    int mid = (l + r) / 2;
    int best = INT_MAX;
    int bestk = -1;

    for (int k = optl; k <= std::min(mid, optr); ++k) {
        int value = dp[i-1][k] + cost[k][mid];
        if (value < best) {
            best = value;
            bestk = k;
        }
    }

    dp[i][mid] = best;
    computeDP(dp, i, l, mid - 1, optl, bestk, cost);
    computeDP(dp, i, mid + 1, r, bestk, optr, cost);
}

int main() {
    int n = 5;
    int m = 3;
    std::vector<std::vector<int>> cost = {
        {0, 2, 9, 10, 1},
        {2, 0, 6, 4, 5},
        {9, 6, 0, 8, 3},
        {10, 4, 8, 0, 2},
        {1, 5, 3, 2, 0}
    };

    std::vector<std::vector<int>> dp(m, std::vector<int>(n, INT_MAX));
    for (int j = 0; j < n; ++j) {
        dp[0][j] = cost[0][j];
    }

    for (int i = 1; i < m; ++i) {
        computeDP(dp, i, 0, n - 1, 0, n - 1, cost);
    }

    std::cout << "최소 비용: " << dp[m-1][n-1] << std::endl;

    return 0;
}

 

설명

1. Convex Hull Trick:
   • addLine: 새로운 선형 함수를 추가합니다.
   • getMin: 주어진 (x)에서 최소 (y)를 찾습니다.
   • 각 선형 함수는 (y = ax + b) 형태로 표현됩니다.
   • 교차점을 계산하여 새로운 선형 함수가 기존 함수와 교차하는지 확인합니다.
2. Divide and Conquer Optimization:
   • 특정 유형의 DP 문제를 분할 정복 기법으로 최적화합니다.
   • computeDP: DP 테이블을 분할 정복 방식으로 채웁니다.
   • 각 단계에서 최적의 중간 점 (k)를 찾아 최소 비용을 계산합니다.

Convex Hull Trick과 Divide and Conquer Optimization의 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 17: 비트마스크 DP(Bitmask DP)"에 대해 학습하겠습니다.