동적 계획법, DP(Dynamic Programming) c++

 

동적 계획법( 다이나밍 프로그래밍 ) 이란?

---

• 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법
• 먼저 입력 크기가 작은 부분 문제들(subproblems)을 모두 해결한 후, 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘

---

동적 계획법, 다이나믹 프로그래밍, DP 모두 같은 말이므로 쉽게 DP라고 통일하겠습니다!

 

 

DP는 이전 부분 문제의 최적해를 기록해놓으므로 완전 탐색 알고리즘보다 빠릅니다.

하지만 해당하는 문제가 최적 부분 구조를 가져야만 DP 알고리즘을 적용할 수 있습니다.

 

 

최적 부분 구조는 무엇일까요?

최적 부분 구조(optimal substructure)란 다음과 같습니다.

• 큰 문제의 최적해에 작은 문제의 최적해가 포함
• 순환식(재귀적)으로 표현 가능

DP 예)

• 피보나치 수열

$F_0 = 0$

$F_1 = 1$

$F_n = F_{n-1} + F_{n-2} (n \in \left\{ 2,3,4,\cdots \right\})$ 

 

최적 부분 구조를 가지고 있다면 이 구조를 순환식으로 정의하고,

이 순환식을 memoization(top-down) 또는 bottom-up 방식으로 풀이하면 됩니다.

두 기법 모두 재귀 호출이 심하게 반복되는 문제를 예방합니다!

 

피보나치 코드로 보는 memoization과 bottom-up의 차이 입니다.

 

• memoization

fib(n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
 
    if (f[n])
        return f[n];
 
    f[n] = fib(n - 1) + fib(n - 2);
    return f[n];
}

• bottom-up

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

 

이미지출처:https://www.educative.io/answers/what-is-dynamic-programming