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

 DP알고리즘은 복잡한 문제를 여러 개의 작은 부분 문제(Sub-Problem)로 나누어 해결하는 방법이며 핵심은 Memoization 기법이라고 볼 수 있다. 

Memoization(메모이제이션)

호출시 이전 계산한 값을 다시 계산하지 않도록 저장하여 전체적인 실행 속도를 향상시키기 위한 기술이다. (배열과 같은 자료구조에 계산된 값을 저장 -> 인덱스값을 통한 불러오기)

예시로는 피보나치 수열을 들 수 있다.

피보나치 수열을 구할때 f(5)값을 구하려면 f(4)와 f(3)이 필요하고 f(4)를 구하려면 f(3)과 f(2)가 필요하다 이러한 중복적인 값을 구할때 이미 구한값들을 Memoization 기법을 통해 배열등에 저장한후 불러오면 중복값을 다시 풀지 않고 불러올 수 있다. 피보나치 수열을 그냥 풀게 되면 O(2^n)의 시간을 갖지만 메모이제이션을 이용하면 O(n)으로 확 줄 수 있다.

 

DP문제를 풀때 두가지 방식으로 접근할 수 있다.

• Top-Down
• Bottom-Up

Top-Down

가장 큰 문제에서부터 작은 문제를 호출하면서 답을 구하는 방식으로 Memmoization과 재귀함수를 이용해 구현하는 경우가 많다. Top-Down 방식은 설계가 쉽다는 장점이 있지만 재귀함수를 사용함으로써 퍼포먼스가 좋지 않을 수 있다.

 

 

public class Test {
    static Integer[] dp;
    public static void main(String[] args) {
        int n = 10;
        dp = new Integer[n+1];
        int fib = fibonacci(n);
        System.out.println(fib); // 55
    }
    public static int fibonacci(int n ){
        dp[0]=0; dp[1] = 1;

        if (dp[n] == null) {
            if (n > 1) {
                dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
            }
        }

        return dp[n];
    }
}

 피보나치 수열을 Top-Down 방식으로 푼 코드이다. 재귀 호출을 통해 1부터 n까지의 수를 dp 배열에 저장하게 됨으로써 실행 시간이 매우 줄었다.

Bottom-Up

작은 문제부터 차례로 구해나가는 방식으로 반복문과 Memmoization 기법을 이용해 구현하는 방식이다. Bottom-Up 방식은 재귀함수를 사용하지 않아 시간과 메모리 사용량을 줄일 수 있지만, 모든 작은 문제를 해결해야 한다는 단점이 있다.

public class Test {
    static Integer[] dp;
    public static void main(String[] args) {
        int n = 10;
        dp = new Integer[n+1];
        int fib = fibonacci(n);
        System.out.println(fib); // 55
    }
    public static int fibonacci(int n ){
        dp[0]=0; dp[1] = 1;

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

        return dp[n];
    }
}

 

 

• https://www.acmicpc.net/workbook/view/7836

문제집: 좋은 DP문제들 (khanjhy)

DP에 대한 감을 찾기 위해 위 사이트에서 위에부터 차례로 풀면 된다.