[알고리즘] DP 박살내기 0. 기본 개념

김학재·2020년 10월 16일

알고리즘

목록 보기

5/10

다이나믹 프로그래밍 뭔지 알겠다! → 코테 박살내러 간다! → 하지만 박살나는 건 나였다

아는 것 같은데 항상 시도할 때마다 벽을 느꼈던 다이나믹 프로그래밍
기본기가 부족하다고 항상 느껴왔던 터라 이참에 알고리즘의 기본들을 하나하나 박살내보기로 마음먹었다.

LeetCode 에서 문제를 풀던 중 좋은 참고 문서를 찾아 직접 번역해가며 공부해보기로 함.
GeeksforGeeks - Overlapping Subproblems Property
GeeksforGeeks - Optimal Substructure Property

DP란?

DP는 기본적으로 recursion을 활용한 최적화 방법이다. 문제를 여러 개의 부분 문제로 나누어 해결하고 이를 저장해 둠으로써 다시 계산할 필요 없이 나중에 사용할 수 있게 한다. 가장 간단한 예로는 피보나치 문제가 있다.

recursion을 사용한 경우

int fib(int n) {
    if (n <= 1)
        return n;
    return fib(n-1) + fib(n-2);
}

                          fib(5)   
                      /            \
               fib(4)                fib(3)   
             /        \              /       \ 
         fib(3)      fib(2)         fib(2)   fib(1)
        /    \       /    \        /      \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /     \
fib(1) fib(0)

실행 단계에 따라 계산 횟수가 기하급수적으로 증가함.
T(n) = T(n-1) + T(n-2)

DP를 사용한 경우
f[0] = f[1] = 0;
for(i = 2; i <= n; i++) {
    f[i] = f[i-1] + f[i-2];
}
return f[n];
시간 복잡도가 linear하게 증가함.

문제 구조 파악하기

DP가 뭔지는 알겠는데 어떤 문제의 경우 DP를 사용할 수 있을까?

1. Overlapping Subproblem

DP의 장점은 부분 문제를 재계산할 필요가 없음에서 나온다. 즉 공통의, 겹치는 부분 문제가 문제에서 보이지 않는다면 DP를 사용할 이유가 없다.

당장 위에서 예시로 든 피보나치 문제의 경우에도 같은 계산이 여러 번 수행되는 것을 확인할 수 있다.
이를 해결하기 위해 값을 저장해두는데 총 두 가지의 방식이 존재한다.

1.1 Memoization(Top down)
계산을 수행하기 전 값이 저장된 테이블(lookup table)을 살펴본 뒤 값이 존재하면 이를 사용하고, 값이 존재하지 않으면 추후에 재사용할 수 있도록 계산된 결과를 저장하는 방식이다.

def fib(n, lookup):
    if n <= 1:
        lookup[n] = n
        
    # 계산된 값이 존재하지 않는다면
    if lookup[n] is None:
        lookup[n] = fib(n-1 , lookup)  + fib(n-2 , lookup)
        
    return lookup[n]

1.2 Tabulation(Bottom up)
원하는 계산 결과를 얻기 위해 가장 아래부터 채워나가는 방식이다.

피보나치 문제에서 먼저 fib(0)을 구하고 fib(1), fib(2) ··· 을 구해나가는 방식이다.

def fib(n):
    f = [0] * n
    f[1] = 1
    
    for i in range(2, n+1):
        f[i] = f[i-1] + f[i-2]
    return f[n]

두 방식이 얼핏 보기에는 비슷하지만 그 접근 방식에서 차이가 있다.
Memoization 방식은 fib(n),fib(n-1) ··· fib(0) : Top-down 방향으로 진행되고,
Tabulation 방식은 fib(0), fib(1), ··· fib(n) : Bottom-up 방향으로 진행된다.