알고리즘 - 다이나믹 프로그래밍(DP)

다이나믹 프로그래밍(동적 계획법, DP; Dynamic Programming)

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

 

다른 알고리즘과의 차이점

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

 

다이나믹 프로그래밍 예시

 

다이나믹 프로그래밍 방법

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

 

 

 

다이나믹 프로그래밍 코드 구현

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

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)); // 13
        System.out.println(fibDP(7)); // 13
        System.out.println(fibDP2(7)); // 13
    }
}