[알고리즘] 동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming)이란?

큰 문제를 여러 개의 부분 문제로 나누어 이를 해결하고, 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 문제해결방법이다.

■ 분할 · 정복(Divide & Conquer) 알고리즘이랑 비슷한데?
큰 문제를 여러 부분 문제로 나눈다는 점에서 분할 정복 알고리즘과 유사하다.
하지만, 이 두 방법 간에 가장 큰 차이점은 부분 문제의 중복 여부이다.
분할 · 정복 알고리즘은 부분 문제들 간에 중복이 없고 각각의 부분 문제는 독립적이지만, 동적 계획법에서 부분 문제 간에 중복이 존재하고, 해결한 부분 문제의 정답을 저장(Memoization)해 두었다 재활용해 문제를 해결한다.

---

 동적 계획법의  사용 조건

1. 중복된 부분 문제 (Overlapping Subproblems) :

동적 계획법은 부분문제의 답을 재활용해 전체 문제를 해결하기 때문에 동일한 부분 문제들이 반복하여 나타나는 경우에 사용할 수 있다.

 

2. 최적 부분 구조 (Optimal Substructure) :

부분 문제의 최적 해결 방법으로 전체 문제의 최적 해결 방법을 구성할 수 있을 때, 최적 부분 구조가 있다 말하는데,

이러한 최적 부분 구조가 존재할 때 동적 계획법을 사용할 수 있다.

---

동적 계획법의 접근 방식

1. Top - Down

최상위부터 바로 호출을 시작하여 재귀호출을 통해 하위 부분문제로 전이해 문제를 해결하는 방식이다.

각 부분 문제의 해결 결과를 저장(Memoization)하여 중복 계산을 피하고 재활용한다.

public static int fibonacci(int n, int[] memo) {
        if (n <= 1)
            return n;

        if (memo[n] != -1)
            return memo[n];

        memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
        return memo[n];
    }

 

2. Bottom - Up

작은 부분 문제부터 시작하여 전체 문제를 해결하는 방식이다. 작은 부분 문제들을 먼저 해결하고, 누적된 결과를 이용하여 전체 문제를 해결하는 방식이다.

public static int fibonacci(int n) {
        if (n <= 1)
            return n;

        int[] dp = new int[n + 1];
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }