[C++] 다이나믹 프로그래밍

다이나믹 프로그래밍(Dynamic Programming)은 문제를 작은 하위 문제로 나누어 해결하고, 그 결과를 저장하여 중복 계산을 방지하는 기법, 최적 부분 구조와 중복된 하위 문제가 있는 문제에 적합

 

---

재귀 방식의 비효율성

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

=> 중복된 하위 문제를 반복 계산

---

1. 메모이제이션(탑다운 방식)

재귀 호출 중 계산 결과를 저장(캐싱)하여 중복 계산을 방지

#include <iostream>
#include <vector>
using namespace std;

vector<int> dp(100, -1); // -1로 초기화 (아직 계산되지 않음)

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (dp[n] != -1) return dp[n]; // 이미 계산된 값 반환
    dp[n] = fibonacci(n - 1) + fibonacci(n - 2); // 계산 후 저장
    return dp[n];
}

int main() {
    int n;
    cin >> n;
    cout << fibonacci(n);
    return 0;
}

2. 타뷸레이션(바텀업 방식)

작은 문제부터 순차적으로 계산하여 저장

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    cout << dp[n];
    return 0;
}

---

두 방식의 비교

1. 메모이제이션:
   • 재귀 호출을 통해 계산을 진행
   • 이미 계산된 값은 캐시에 저장하여 재사용
   • 적은 공간을 사용하지만, 스택 오버플로우 가능성 있음
2. 타뷸레이션:
   • 반복문을 통해 작은 문제부터 순차적으로 계산
   • 스택 사용 없이 모든 결과를 배열에 저장
   • 공간이 더 필요하지만, 스택 오버플로우가 발생하지 않음

---

다이나믹 프로그래밍의 시간복잡도

위 두 방식 모두 점화식의 결과를 한 번만 계산하므로 시간 복잡도는 O(n)O(n)

이는 재귀 방식의 O(2n)O(2^n)에 비해 매우 효율적