Dynamic Programming (동적 프로그래밍)

1. 다이나믹 프로그래밍 (DP)

• 큰 문제를 부분 문제로 나눈 후 답을 찾아가는 과정에서, 계산된 결과를 기록하고 재활용하며 문제의 답을 구하는 방식
• 중간 계산 결과를 기록하기 위한 메모리가 필요
• 한번 계산한 부분을 다시 계산하지 않아 속도가 빠름

2. 다른 알고리즘과의 차이점

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

3. 다이나믹 프로그래밍 예시

4. 다이나믹 프로그래밍 방법

• 타뷸레이션 (Tabulation) - BottomUp
  • 상향식 접근 방법
  • 작은 하위 문제부터 풀면서 올라감
  • 모두 계산하면서 차례대로 진행
• 메모제이션 - TopDown
  • 하향식 접근 방법
  • 큰 문제에서 하위 문제를 확인해가며 진행
  • 계산이 필요한 순간 계산하며 진행

(실습 : 피보나치 수열)

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

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) {
        // Test code
        System.out.println("일반풀이 : " + fib(7));
        System.out.println("타뷸레이션 : " + fibDP(7));
        System.out.println("메모이제이션 : " + fibDP2(7));
    }
}