다이나믹 프로그래밍 (DP,Dynamic Programming)

1. 다이나믹 프로그래밍이란?

• = 동적 계획법
• 큰 문제를 부분 문제로 나눈 후 문제를 해결하는 과정에서 나오는 계산된 결과를 기록하여 재활용하는 방법
• 한번 계산한 부분을 다시 계산하지 않기 때문에 속도가 빠르다
• 계산된 결과를 저장하기 위한 메모리가 필요하다

 

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

• 분할 정복
  • 분할 정복은 부분 문제가 중복되지 않는다
  • DP는 부분 문제가 중복된다
  • 분할 정복에서는 DP 사용불가
• 그리디 알고리즘
  • 그리디 알고리즘은 근사치를 구하는 방식
  • DP는 모든 방법을 확인 후 최적해 구하는 방식
  • 둘 다 적용이 가능하다면 그리디 알고리즘이 더 빠름

 

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

• 피보나치
  • 피보나치 같은 경우 아래의 그림과 같이 계산할 때 중복이 발생한다. 이를 처음 계산할 때 따로 저장해둔다면 계산을 여러번 할 필요 없이 계산된 값을 가져다가 바로 사용하면 된다.

 

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

• 타뷸레이션 (Tabulation)
  • 상향식 접근법
  • 하위 문제부터 풀면서 상위 문제로 올라감
  • 모두 계산하면서 차례대로 진행한다.
• 메모이제이션 (Memoization)
  • 하향식 접근법
  • 상위 문제에서 하위문제로 내려가면서 푼다
  • 계산이 필요한 순간 계산하며 진행한다.

public class Main {
    
    // 일반 풀이 - O(n^2)
    public static int fib(int n) {
        if (n <= 1) {
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }

    // 타뷸레이션 - O(n)
    public static int tabulation(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];
    }

    // 메모이제이션 - O(n)
    static int[] dp = new int[8];

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

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

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