동적 계산법

동적 계획법 (Dynamic Programming, DP)은 복잡한 문제를 작은 하위 문제들로 나누어 풀고, 그 결과를 저장해 재사용하여 주어진 문제를 최적화하는 방법이다.

이는 '분할 정복' 알고리즘의 기본적인 원리를 따르지만, 동적 계획법은 각 하위 문제들이 중첩되어 있는 경우에 특히 효과적이다. 그래서, 동적 계획법은 공통의 하위 문제들을 여러 번 다시 풀지 않도록 이를 메모이제이션 (memoization)하여, 알고리즘의 계산 효율성을 대폭 향상시킨다.

동적 계획법은 일반적으로 두 가지 기본 단계를 거친다.

1. 하향식 접근법(Top-down): 문제를 하위 문제로 나눈다. 만약 하위 문제가 이미 해결되었다면, 저장된 결과를 사용한다. 아니라면, 문제를 해결하고 결과를 저장한다.
2. 상향식 접근법(Bottom-up): 가장 작은 하위 문제부터 시작하여, 작은 하위 문제들의 해결을 바탕으로 큰 문제의 해결책을 구성해 나간다.

동적 계획법은 최단 경로 문제, 0-1 배낭 문제, 피보나치 수열 등 다양한 문제에 적용될 수 있다. 그러나 동적 계획법이 모든 최적화 문제에 효과적인 것은 아니다. '최적 부분 구조(Optimal Substructure)'와 '중복된 하위 문제(Overlapping Subproblems)' 조건을 만족하는 문제에 대해서만 동적 계획법을 적용할 수 있다.

public class Main {
    public static long fib(int n) {
        long[] dp = new long[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)); // 10 번째 피보나치 수를 출력
    }
}

dp라는 이름의 long형 배열은 메모이제이션을 위한 저장 공간으로 사용된다. 각 n에 대한 피보나치 결과가 이 배열에 저장된다. 이미 계산된 결과를 재사용할 수 있게 되어 중복 계산을 피하고 효율성을 높일 수 있다.