Memoization, Top-down and Bottom-up

DP의 핵심요소는 메모이제이션(캐싱)이라고 할 수 있다. 이미 계산한 결과를 저장하는 재귀라고도 할 수 있다. 기억 공간을 반복될 계산결과의 저장에 할당함으로써 귀중한 연산시간을 절약하는 것이다. DP를 이용해 해결할 수 있는 대표적이며 가장 간단한 예로 피보나치 수열이 있다. 어떻게 이 문제가 재귀, top-down DP, bottom-up DP, 그리고 그 기억공간을 추가로 절감하는 방식으로 수행되는지를 살펴본다.

재귀

피보나치 수열은 수학적으로 다음 점화식(recurrence relation)으로 정의된다.

$$ f_n = f_{n-1} + f_{n-2} $$

$$ f_0 = 0; \ f_1 = 1 $$

n번째 수를 구하기 위해서는 n-1번째, n-2번째 수를 알아야 하고, 그들을 알기 위해서는 다시 점화식을 풀어야 하므로 결국 base case인 f(0), f(1) 까지 가야 점화식의 전개가 끝나고 답을 구할 수 있다. 점화식을 컴퓨터 프로그래밍에서 구현한 것이 재귀(recursion)이라고 할 수 있다. 다음 예를 보자.

 

def fib(n):
    if n == 0 or n == 1: f = n
    return fib(n - 1) + fib(n - 2)

 

이 식의 시간복잡도는 O(2^n) 이 된다.

 

Top-down DP

코드를 먼저 보자.

 

memo = {}
def fib(n):
    if n in memo: return memo[n]
    if n == 0 or n == 1: f = n
    else: f = fib(n - 1) + fib(n - 2)
    memo[n] = f
    return f
# [Source] MIT 6.006, Lec 19 (2011)

 

여기서는 위 코드와 다른 부분으로서 캐시를 활용하는 부분이 추가되었다. 즉, 캐시(memo)안에 n에 대한 피보나치 수가 저장되어 있다면 그것을 돌려준다. 만일 그렇지 않다면, n in (0, 1)인 경우에 f에 n을 저장하거나 그 밖의 경우에는 f에 재귀식을 사용해 값을 계산해 저장한다(만일 재귀식을 호출했는데 그 값은 memo 안에 저장된 것이 있다면 그것을 활용해서 계산해 돌려줄 것이다). f를 새로 계산했으므로 이것은 나중에 활용하기 위해 memo 안에 저장한다. 마지막으로 계산한 f값은 돌려준다.

memo를 직접 하지 않고 @cache나 @lru_cache를 활용하는 방법은 https://algoship.tistory.com/8 에서 소개했으므로 이를 참고하라.

 

Bottom-up DP

상향식 DP는 재귀와 캐시를 사용하지 않고 바로 테이블에 저장한 뒤 마지막 값을 돌려준다.

 

def fib(n):
    table = [0 for _ in range(n+1)]   # 0, 1, 2, ..., n
    for i in range(n+1):
        if i in (0, 1):
            table[i] = i
        else:
            table[i] = table[i - 1] + table[i - 2]
    return table[n]

 

이 경우 바로 array에 값들을 저장하고 불러오는데 이것은 재귀호출과 캐싱을 한 것과 효과가 같다. Bottom-up DP는 재귀를 위한 스택을 준비하지 않아도 되므로 때때로 Top-down DP보다 속도가 더 빠른 장점이 있으나, 만일 Top-down 이었을 경우에 base case까지 도달하기 위한 총 스택의 수를 미리 계산하여 전체 array의 기억공간을 배정해줘야 하는 점이 까다로운 부분이다 (단순히 memo = {} 로 설정했던 Top-down과 비교해보라).

그러나, 이 경우 기억공간이 O(n) 까지 필요가 없을 수 있다. 왜냐하면 현재의 피보나치 수를 위해선 직전과 직직전의 값만이 필요하기 때문이다. 그러므로 아래와 같이 바꾸어 O(1)으로 풀 수 있다. 이러한 공간 절약은 재귀시와는 달리 bottom-up에서 가능하다.

 

def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

# [Source] https://stackoverflow.com/questions/36948082/bottom-up-fibonacci-in-python-using-o1-space

 

Bottom-up은 Topological Sort이라고 할 수 있다. f(n-2) -> f(n-1) -> f(n) 이면서 f(n-2) -> f(n) 이기 때문이다. 즉, f(n)이 그 전단계에 영향을 미치지 않는다. 그러므로 DAG (directed acyclic graph) 와 같은 형태이다.