동적계획법, DP

동적 계획법(Dynamic Programming, DP)은 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다. 최적값을 구할때 주로 사용한다.

큰 문제를 작은 문제로

동적계획법의 핵심은 큰 문제를 작은 문제로 나눠서 푼다이다. 분할 정복(Divide and Conquer)과 비슷하지만 분할 정복은 계산한 부분 문제를 한번만 쓰기 때문에 메모이제이션이 필요하지 않다. 하지만 동적계획법에서는 메모이제이션이 필요하다는 점에서 두 가지 방식이 다르다.

메모이제이션(Memoization)

동적계획법 알고리즘의 대표적인 예는 이항 계수(nCr)의 계산이다.
bino(a, b) = bino(a-1, b) + bino(a-1, b-1)일 경우, bino(4,2)를 호출했을 때,

(a)에서 bino(2,1)는 bino(3,1)과 bino(3,2)에서 모두 호출된다. bino(2,1)은 bino(1,0), bino(1,1)을 재귀 호출하여 이 경우도 두 번씩 호출된다. 동적 계획법에는 이처럼 중복된 계산을 막기 위해 저장된 결과를 배열에 저장한뒤, 다음에 계산이 필요할 때는 저장된 값을 불러와서 중복을 없애면 (b)처럼 함수 호출이 줄어드는 것을 알 수 있다. 따라서, 시간 복잡도도 훨씬 줄어들게 된다. 이러한 기법을 메모이제이션이라고 한다.

TOP-DOWN(재귀 방식)

재귀와 같은 방식으로 위에서 아래로 내려오는 방식. 함수 호출을 줄이기 위해, 메모이제이션을 사용한다.

//일반 재귀
long long fib(long long n) {
    if(n == 1 || n == 2) 
        return 1;

    return fib(n-1) + fib(n-2);
}

//메모이제이션을 적용한 TOP-DOWN 방식 DP
long long fib(long long n) {
    if(n == 1 || n == 2)
        return 1;

    if(!cache[n])
        return cache[n];

    cache[n] = fib(n-1) + fib(n-2);
    return cache[n];
}

 

BOTTOM-UP(반복문 방식)

TOP-DOWN 방식과 달리, 반복문을 이용해서 처음값부터 다음값을 계산해 나가는 방식이다.

long long fib(int n) {
    cache[0] = 0;
    cache[1] = 1;

    for(int i = 2; i <= n; i++)
        cache[i] = cache[i-1] + cache[i-2];

    return cache[n];
}

 

DP 기반의 알고리즘 동작 방식

1. 궁극적으로 해결하고자 하는 문제를 작은 부분 문제로 나눈다.
2. 가장 작은 부분 문제(base case, 주로 0 또는 1일 때)부터 푼 뒤 값을 저장한다. => 메모이제이션
3. 메모이제이션된 부분 문제들의 해를 이용하여 차례로 더 큰 상위 문제의 답을 구한다.
4. 3번의 과정을 반복하여 궁극적으로 해결하고자 하는 문제를 해결할 때까지 반복한다.

DP 문제 해결 가이드라인

1. 몇 개의 차원(=변수 개수) DP를 할 것인가?
2. 변수 개수(=차원)가 정해졌으면 각각의 변수가 무슨 의미인가?
3. DP값이 어떤 의미인가?
4. 어떤 DP값과 다른 DP값의 관계가 있는가? 있으면 어떤 관계인가? (DP 테이블을 직접 채워본다.)
5. 4의 점화식을 이용하여 TOP-DOWN 방식이나 BOTTOM-UP 방식으로 해결한다.

DP의 초기화

이미 계산한 것을 다시 계산하지 않기 위해 계산한 것과 계산하지 않은 것의 차이가 있어야 한다. 계산하지 않은 초기값(초기화한 값)은 그대로이고 계산한 값은 바뀌어 있어야 하기 때문에 그것으로 구분한다. 따라서 DP에서 계산한 값의 범위를 대략적으로 알아내서 그 범위에 있지 않은 값으로 초기화를 해주어야 한다. 계산된 값이 0일 수 있는 DP의 경우에는 보통 -1(또는 무한대)을 사용하고 계싼된 값이 0일 수 없는 경우에는 전역변수로 선언한다.

TOP-DOWN vs BOTTOM-UP

탑다운 방식에 메모이제이션을 했으면 시간 복잡도는 같다. 하지만 일반적으로 탑다운 방식이 더 계산 시간이 오래 걸린다. 재귀 DP의 장점은 점화식 그대로 호출이 되기 때문에 형식/순서에 얽매이지 않는다. for문 DP의 장점은 시간이 상대적으로 적게 걸린다.

---

백준 참고문제 : 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052, 2751, 11650, 11651, 10814, 10825, 10989, 11652, 11004, 10828, 9012, 10799, 10845, 10866, 10808, 10809, 10820, 2743, 11655, 10824, 11656, 1406, 1158, 1168, 10430, 2609, 1934, 1850, 9613, 11005, 2745, 1373, 1212, 2089, 11576, 1978, 1929, 6588, 11653, 10872, 1676, 2004