동적 계획법 (Dynamic Programming) 정의 및 구현 방법

안녕하세요. 두부입니다.

다양한 알고리즘 문제를 해결하다 보면 깊이 우선 탐색, 너비 우선 탐색, 동적 계획법 등 다양한 문제 해결 방법을 접할 수 있는데요. 이번에 알아보고자 하는 건 동적 계획법 (DP)입니다.

 

동적 계획법 정의

하나의 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용해서 큰 문제를 해결하는 방식으로 피보나치 수열에서 시작되었다.

 

Q. 일반적인 재귀 방식과 매우 유사한 동적 계획법을 사용하는 이유는 뭘까?

A. 일반적인 재귀 방식을 사용할 경우 동일한 작은 문제들이 여러 번 반복되며 비효율적인 계산으로 빠질 수 있다. 동적 계획법은 작은 문제들을 재활용해서 사용하는 방식이기 때문에 이러한 문제에서 일반적인 재귀 방식보다 유리하다.

 

Q. 동적 계획법의 사용 조건은 무엇인가요?

A. 동적 계획법을 사용하기 위해선 두 가지 조건을 만족해야한다. 

1. Overlapping Subproblems (겹치는 부분)

부분 문제의 결과를 저장하여 재계산하지 않을 수 있어야하는데 해당 부분 문제가 반복적으로 나타나지 않으면 사용이 불가능하다.

 

2. Optimal Substructure (최적 부분)

부문 문제에서 구한 최적 결과가 천제 문제에서도 동일하게 적용되어 결과가 변하지 않을 때 사용할 수 있다.

 

동적 계획법 구현 방법

1. Bottom-Up 방식

아래에서부터 위로 계산을 수행하면서 큰 문제를 해결하는 방식이다.

메모를 위해서 dp라는 배열을 만든 후 출발점 dp[0] 부터 dp[n]까지 차근차근 구해나가는 방법

 

2. Top-down 방식

재귀함수로 구현하는 대부분의 경우가 Top-down 방식이다. 큰 문제를 풀 때 작은 문제가 아직 풀리지 않았다면 그제서야 작은 문제를 해결하게 된다.

 

30번째 피보나치 수열 계산 코드를 통해서 일반적인 재귀 방식과 동적 계획법의 소요 시간을 알아보겠다. 

public class Fibonacci{
    
    static int[] topDown_memo; 
    static int[] bottomup_table;
    
    public static void main(String[] args){
        int n = 30;
        topDown_memo = new int[n+1];
        bottomup_table = new int[n+1];
        
        long startTime = System.currentTimeMillis();
        System.out.println(naiveRecursion(n));
        long endTime = System.currentTimeMillis();
        System.out.println("일반 재귀 소요 시간 : " + (endTime - startTime));
        
        System.out.println();
        
        startTime = System.currentTimeMillis();
        System.out.println(topDown(n));
        endTime = System.currentTimeMillis();
        System.out.println("Top-Down DP 소요 시간 : " + (endTime - startTime));
        
        System.out.println();
        
        startTime = System.currentTimeMillis();
        System.out.println(bottomUp(n));
        endTime = System.currentTimeMillis();
        System.out.println("Bottom-Up DP 소요 시간 : " + (endTime - startTime));
    }
    
    // 단순 재귀를 통해 Fibonacci를 구하는 경우
    // 동일한 계산을 반복하여 비효율적으로 처리가 수행됨
    public static int naiveRecursion(int n){
        if(n <= 1){
            return n;
        }
        return naiveRecursion(n-1) + naiveRecursion(n-2);
    }
    
    // DP Top-Down을 사용해 Fibonacci를 구하는 경우
    public static int topDown(int n){
        // 기저 상태 도달 시, 0, 1로 초기화
        if(n < 2) return topDown_memo[n] = n;
        
        // 메모에 계산된 값이 있으면 바로 반환
        if(topDown_memo[n] > 0) return topDown_memo[n];
        
        // 재귀를 사용하고 있음
        topDown_memo[n] = topDown(n-1) + topDown(n-2);
        
        return topDown_memo[n];
    }
    
    // DP Bottom-Up을 사용해 Fibonacci를 구하는 경우
    public static int bottomUp(int n){
        // 기저 상태의 경우 사전에 미리 저장
        bottomup_table[0] = 0; bottomup_table[1] = 1;
        
        // 반복문을 사용하고 있음
        for(int i=2; i<=n; i++){
            // Table을 채워나감
            bottomup_table[i] = bottomup_table[i-1] + bottomup_table[i-2];
        }
        return bottomup_table[n];
    }
}

/*
832040
일반 재귀 소요 시간 : 4

832040
Top-Down DP 소요 시간 : 0

832040
Bottom-Up DP 소요 시간 : 0
*/

참고: https://hongjw1938.tistory.com/47?category=909529