다이나믹 프로그래밍은 주어진 문제를 하위 문제(subproblem)로 나누어 푸는 방법입니다. 중복된 계산을 피하기 위해 작은 하위 문제의 결과를 저장하고 재활용합니다. 문제가 최적 부분 구조(optimal substructure)와 중복되는 하위 문제(overlapping subproblems)를 갖고 있을 때 적용 가능합니다.

다이나믹 프로그래밍의 특징

• 작은 하위 문제의 해결을 통해 전체 문제의 해결이 가능합니다.
• 하위 문제의 결과를 저장하고 재활용하기 때문에 중복 계산을 피할 수 있습니다.
• 일반적으로 탑다운(top-down) 방식(메모이제이션(Memoization))과 바텀업(bottom-up) 방식(타뷸레이션(Tabulation))으로 구현할 수 있습니다.

다른 알고리즘과의 차이점

• 분할 정복과의 차이
  • 분할 정복은 부분 문제가 중복되지 않음
  • DP는 부분 문제가 중복되어 재활용에 사용
• 그리디 알고리즘과의 차이
  • 그리디 알고리즘은 순간의 최선을 구하는 방식(근사치)
  • DP는 모든 방법을 확인 후 최적해 구하는 방식

다이나믹 프로그래밍의 장단점

장점

• 중복된 계산을 피해 시간 복잡도를 줄일 수 있습니다.
• 문제를 나누어 해결하기 때문에 복잡한 문제도 해결이 가능합니다.

단점

• 모든 문제가 다이나믹 프로그래밍에 적합하지는 않습니다.
• 메모리를 많이 사용할 수 있습니다.

시간 복잡도

• 다이나믹 프로그래밍의 시간 복잡도는 하위 문제의 개수와 각 하위 문제를 해결하는 데 걸리는 시간에 따라 달라집니다.
• 일반적으로 다이나믹 프로그래밍 알고리즘의 시간 복잡도는 $O(n^2)$ 이하입니다.

구현 방법 및 예제

• 피보나치
  

// 알고리즘 - 다이나믹 프로그래밍

public class Main {
    // 피보나치 수열 (일반 풀이 - O(n^2))
    // 계산했던 부분도 다시 계산
    public static int fib(int n) {
        if(n <= 1){
            return n;
        }else{
            return fib(n - 1) + fib(n - 2);
        }
    }

    // 피보나치 수열(DP 풀이 - 타뷸레이션 - O(n))
    public static int fibDP(int n) {
        int[] dp = new int[n < 2 ? 2 : n + 1];
        dp[0] = 0;
        dp[1] = 1;

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

        return dp[n];
    }

    // 피보나치 수열 (DP 풀이 - 메모이제이션 - O(n))
    static int[] dp = new int[8];

    public static int fibDP2(int n) {
        if(n <= 2){
            return 1;
        }

        if(dp[n] != 0){
            return dp[n];
        }

        dp[n] = fibDP2(n - 1) + fibDP2(n - 2);
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(fib(7));
        System.out.println(fibDP(7));
        System.out.println(fibDP2(7));
    }
}