동적계획법 (DP:Dynamic Programming)

복잡한 문제를 작은 하위 문제로 나누어 푸는 알고리즘 기법

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

다른 알고리즘과의 차이점

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

방법

타뷸레이션(Tabulation)

• 상향식 접근 방법(Bottom-Up)
• 작은 하위 문제부터 풀면서 올라감
• 모두 계산하면서 차례대로 진행
• 반복문(Iteration) 사용

// 시간 복잡도 - O(n)
public class FibonacciDP {
    static int fib(int n) {
        if (n <= 1) return n;
        int[] dp = new int[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];
    }

    public static void main(String[] args) {
        System.out.println(fib(10)); // 55
    }
}

메모이제이션(Memoization)

• 하향식 접근 방법(Top-Down)
• 큰 문제에서 하위 문제를 확인해가며 진행
• 계산이 필요한 순간 계산하며 진행
• 재귀(Recursion) + 캐싱(Memoization)

// 시간 복잡도 - O(n)
public class FibonacciMemo {
    static int fib(int n) {
    	int[] memo = new int[n+1];
        if (n <= 2) return 1;
        
        if (memo[n]!=0) return memo[n];
        
        memo[n] = fib(n - 1) + fib(n - 2);
        return memo[n];
    }

    public static void main(String[] args) {
        System.out.println(fib(10)); // 55
    }
}