[DataStructure&Algorithm] DP, 동적 계획법

---

DP란?

DP란, Dynamic Programming의 약자로, 동적 계획법이라고합니다.

 

DP가 어떤 단어의 약자이고 그것이 어떻게 불리는지에 대해서는 알겠는데, 너무 추상적이고 뭐가 동적으로 계획된다는 건지 이해가 되지 않을 수 있습니다. DP는 큰 문제를 조그만한 문제로 나누어, 답을 구하고 계산된 결과를 기록하고 재활용하며, 문제의 답을 찾아가는 방식으로 진행됩니다. 

 

이런 구조적인 특성상 계산에서 나온 결과를 저장하기 위해서는 중간 계산 결과를 저장하기 위한 추가적인 메모리를 필요로 하게 됩니다.

최근 한국에서 코딩테스트 시험을 볼 때, 시간 복잡도에 대해서는 다소 타이트하게 주어질 수 있지만, 공간 복잡도에 대해서는 상당히 널널하게 주는 편이므로, 어떤 문제를 풀어나갈 때, 다른 방법이 존재하더라도, DP를 통해 시간 복잡도를 줄일 수 있다면, 공간 복잡도를 많이 사용하더라도 DP를 사용하는 방법이 올바를 것이라고 생각합니다.

---

특징

• Divide & Conquer(분할 정복)과 유사하다는 특성이 존재한다.
  • 공통점 : 큰 문제를 작은 문제로 쪼개어서 추가적인 과정을 거친 이후, 전체에 대한 답을 도출하는 것
  • 차이점 : 분할 정복은 큰 문제를 해결하기 어려워서, 단순히 작은 문제로 나누어 푸는 방법입니다.
    여기서 특징은, 작은 문제에서 반복이 발생하지 않는다는 점인데, DP(동적 계획법)에서는 작은 일의 반복이 발생합니다.
    DP는 이를 통해서 큰 문제를 해결해 나가는 것입니다.
• 그리디 알고리즘과의 차이
  • 그리디 알고리즘과 DP 역시 최적해를 구하는 방식 중 하나입니다. 하지만 2개의 방식에는 큰 차이점이 존재합니다.
    • Greedy Algorithm (탐욕법) : 그리디 알고리즘은 순간의 최적해를 구하는 방식입니다. 즉, 결과값이 정답이 아닌 근사치라는 것입니다.
    • DP : 동적 계획법은 모든 방법을 통해 값을 확인하고 이를 통해서 전체의 입력 값에서 최적해를 구하는 방식입니다.
• 같은 입력 값에 대해서는 반드시 같은 결과 값이 나옵니다.
  • 이를 통해서 반복을 발생시키고, 계산을 단축하여 처리하는 시간을 감소하게됩니다.
• 구현 방법에는 2가지가 존재합니다
  • Memoization(메모이제이션) : Memoization은 아까 언급했던 DP의 특징을 이용하여, 한 번 발생했던 값을 저장하고 그 다음 문제를 풀어나가면서 큰 문제를 해결하는 하향식 접근 방법입니다. 큰 문제에서 하위 문제를 확인해가면서 진행합니다. 또한, 계산이 필요한 순간에서만 계산하며 진행합니다.
  • Tabulation (타뷸레이션) : Tabulation은 Memoization과는 거의 모든 것이 반대인 접근방법입니다. 하향식 접근 방법이며, 작은 하위 문제부터 풀면서 올라갑니다. 또한, 계산이 필요한 순간에만 하는 것이 아닌, 모두 계산하면서 차례대로 진행합니다.

---

코드

 

아래의 코드에서는 간단하게 Fibonacci 수열을 재귀 호출 방법, DP의 Memoization 방법, DP의 Tabulation 방법으로 작성했습니다.

 

우선, 쉽게 사용할 수 있는 코드는 재귀 호출 방법일 것입니다. 하지만, 모든 문제를 재귀적으로 호출하면서 풀 수는 없기때문에, DP의 방법으로도 풀이해봤습니다.

 

class Main{
    // 재귀적 Fibonacci
    public static int Fibonacci(int n){
        if(n < 3){
            return 1;
        }
        return Fibonacci(n-1) + Fibonacci(n-2);
    }

    // DP - Memoization Fibonacci
    public static int FibonacciMemo(int n, int[] memo){
        if(n < 3){
            return 1;
        }
        if(memo[n] != 0){
            return memo[n];
        }
        memo[n] = FibonacciMemo(n-1, memo) + FibonacciMemo(n-2, memo);
        return memo[n];
    }
    
    // DP - Tabulation Fibonacci
    public static int FibonacciTabulation(int n){
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
    public static void main(String[] args) {
        System.out.println(Fibonacci(10));

        // DP - Memoization Fibonacci
        int[] memo = new int[100];
        System.out.println(FibonacciMemo(10, memo));
        
        // DP - Tabulation Fibonacci
        System.out.println(FibonacciTabulation(10));

    }
}

 

---

 

설명

Memoization - 하향식, 필요 부분만 계산

Memoization은 입력으로 들어온 n부터 확인하고 있습니다. 만약 존재하지 않는다면, 이전과 그 이전의 합을 memo[n]에 삽입하는 것을 확인할 수 있습니다. 이를 통해서 우리는 Memoization은 하향식 접근 방법이라는 것을 확인할 수 있습니다.

 

Tabulation - 상향식, 모두 계산

Tabulation 방식의 함수에서는 우선 0번과 1번 인덱스의 값으로 초기 값을 넣어주게 됩니다. 그 다음 항부터는 인덱스에 접근하여 해당 값들의 합으로 다음 항의 값을 입력하게 됩니다. 이를 통해서 Tabulation 방식은 아래에서부터 위까지 모든 차례의 항에 대해서 계산을 하게 되며, 아래에서부터 위로 올라가는 상향식 접근 방법으로 진행되고 있는 것을 알 수 있습니다.

---

정리

DP에서는 2가지 방법으로 문제를 풀 수 있습니다. 주어진 문제의 상황에 따라서 적절한 방법을 채택하는 것이 가장 효율적인 방법이라고 생각됩니다.

 

제가 코딩 테스트를 공부하면서 DP 문제를 풀 때, 만약 수식적으로 문제의 점화식이 세워진다는 가정하에는 Tabulation을 통해서 작은 문제부터 하나씩 처리해나가는 것이 가장 빠르게 접근할 수 있는 방법인 것 같고, 그 이외의 방식에서는 더 생각을 해봐야 어떤 방법으로 문제를 풀어갈 지 정할 수 있을 것입니다.