Dynamic Programming

https://hongjw1938.tistory.com/47

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

 

DP란?

DP는 하나의 큰 문제를 여러 개의 작은 문제로 나눠서 결과를 저장하여 큰 문제를 해결할 때 사용하는 문제해결 패러다임이다. 쉽게 표현하면 큰 문제를 작은 문제로 쪼개서 답을 저장해두고 재활용하는 것이다. 

장점

DP는 재귀와 유사하다. 재귀의 단점은 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산을 할 수 있다는 것이다.

DP는 재귀의 이러한 단점을 해결한다. 한번 구한 작은 문제의 답을 저장해놓고 재사용한다. 

사용조건

1. 겹치는 부분 문제

동일한 작은 문제들이 반복하여 나타나는 경우에 사용 가능하다. 

출처 : https://hongjw1938.tistory.com/47

f(3), f(2), f(1)이 여러번 반복되어 나타난다. 이럴 경우 값을 저장해놓고 사용할 수 있다. 

2. 최적 부분 구조 

부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있어야 한다.  즉 부분 문제에서 구한 답이 전체 문제에 사용될 수 있다는 뜻이다. 

출처 : https://hongjw1938.tistory.com/47

A->X의 최단거리와 X->B의 최단거리를 구하는 부분 문제의 답은 각각 AX2와 BX2이다. 전체 문제 A->B의 최단거리는 부분문제 2개의 최단거리의 합으로 구할 수 있다. 즉 부분문제의 답을 적용할 수 있다. 전체문제에 적용한다고 해서 A->X의 최단거리가 AX1이 된다거나 하는 변경이 없다. 

DP 적용하기

DP는 알고리즘이 아닌 방법론이므로 다양한 문제해결에 쓰일 수 있다. 먼저 DP를 적용할 수 있는 문제인지 알아내고 적용해야 한다. DP를 사용하는 과정은 이렇다.

1. DP 적용가능 문제인지 확인 
2. 문제 변수 파악
3. 점화식 작성
4. 메모하기(memoization or tabulation)
5. 초기값 구하기 
6. 구현하기 

1. DP 적용가능 문제인지 확인 

위에서 언급한 사용조건에 해당되는 문제인지 파악해야 한다. 일반적으로 데이터 내 최대화/최소화 계산, 특정 조건 내 데이터 세기, 확률 계산 등 문제가 해당된다.

2. 문제 변수 파악 

DP에서는 현재 문제 변수에 따른 결과 값을 찾고 그것을 재사용한다. 문제 내 변수는 여러개일 수 있다. 

예를 들어, n번째 피보나치 수를 구하는 문제에서는 n이 변수다. 

3. 점화식 작성 

점화식을 작성해야 반복/재귀를 통해 문제를 해결할 수 있다. 

피보나치 수열에서는 f(n)=f(n-1)+f(n-2)가 이에 해당한다. 

4. 메모하기 

변수값에 따른 결과를 저장하고 재사용해야 한다. 결과를 저장하는 것을 Memoization이라 한다. 

배열을 미리 만들고, 결과를 배열에 저장하고, 추후에 재사용한다. 

5. 초기값 구하기  

초기값을 구해야 한다. 피보나치수열에서는 f(0)=0, f(1)=1이 초기값이다. 이 값을 미리 파악하고 배열에 저장해놓는다. 

6. 구현하기 

구현은 2가지 방식으로 가능하다.

 

Bottom Up 방식 (Tabulation, 반복문 사용)

아래에서부터 계산을 수행하고 누적시켜 큰 문제를 해결한다. 기저 상태 dp[0]로부터 목표 상태 dp[n]까지 반복문을 통해 점화식으로 결과를 낸다. 이 과정에서 값을 재할용한다. 

Bottom Up 방식에서는 Meomization이 아닌 Tabulation이라고 부른다. 

 

Top Down 방식 (Memoization, 재귀 사용)

목표 상태dp[n]부터 시작해 dp[0]까지 내려간다. 재귀를 통해 결과 값을 전이시켜 재활용한다. 

 

두 방법에 대한 추상적인 설명으로는 잘 이해가 가지 않는다. 소스코드로 확인해보자.

(코드 출처 : https://hongjw1938.tistory.com/47)

packge com.test;

public class Fibonacci{
    // DP 를 사용 시 작은 문제의 결과값을 저장하는 배열
    // Top-down, Bottom-up 별개로 생성하였음(큰 의미는 없음)
    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
일반 재귀 소요 시간 : 9

832040
Top-Down DP 소요 시간 : 0

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

 

두가지 방법 중 뭐가 더 나은지는 상황에 따라 다르다. 그리고 한가지 방법만 사용 가능한 문제도 있다.