메모이제이션(Memoization)과 다이나믹 프로그래밍(Dynamic Programming)

메모이제이션(Memoization)과 다이나믹 프로그래밍(Dynamic Programming)

글. 수알치 오상문 sualchi@daum.net 

메모이제이션과 다이나믹 프로그래밍은 순환식을 계산하는 방법이고 동적 계획법에 포함할 수 있습니다. 둘의 차이점은, 메모이제이션은 하향(Top down) 방식이고 필요한 하위 문제를 해결한다(흔히 말하는 동적 계획법)는 것입니다. 반면에 다이나믹 프로그래밍은 상향(Bottom up)이며 재귀 호출 부담이 적습니다.


예를 들어, 피보나치 수를 계산할 때 재귀 함수를 사용할 수 있는데, 이 때 중간 과정에서 중복되는 계산이 많이 들어갑니다. 즉, 같은 연산이 반복된다는 것은 시간이 올래 걸리므로 효율이 떨어집니다. 만약 중복 계산을 줄일 수 있다면 속도가 훨씬 빨라지는데 이러한 방식으로 사용할 수 있는 것이 메모이제이션이나 다이나믹 프로그래밍 기법입니다.


재귀호출을 이용하여 피보나치 수를 계산할 때는 중복되는 계산이 많으므로 이런 경우에는 메모이제이션 기법을 활용하면 좋습니다(아니면 그냥 반복문을 이용하여 구현하는 것이 더 빠릅니다). 메모이제이션은 이미 계산한 결과를 저장하고 나중에 다시 사용하는 기법입니다. 그러므로 정보를 저장할 메모리 공간(버퍼, 캐시)을 미리 준비해야 합니다. 그리고 그 메모리 버퍼를 -1로 초기화하면 아직 계산하지 않았다는 것을 의미합니다. 만약 이미 계산한 부분이라면 -1이 아닐 것입니다(초기값-1과 결과값 -1이 혼동될 수 있는데 초기값을 -1이 아닌 값으로 설정할 수도 있으므로 그런 구분은 여러분이 적당히 선택해야합니다).


재귀 호출 함수가 하향식임에 비하여 반대로 초기 위치부터 상향으로 올라가는 방식도 가능합니다. 이 경우에는 초기 시작 값을 정해주고 시작해야 합니다. 예를 들어, 피보나치 수열은 구할 대 f(0). f(1) 함수 반환 값을 정해주고 시작하는 것입니다.


그러므로 기본 값을 정하고 위로 올라가면서 값을 구하는 방식이 상향식이고 재귀호출처럼 뒤로 돌아가면서 하향하는 방식도 가능한데, 어느 것이 좋다라고 단순하게 판단할 문제는 아닙니다. 어느 쪽이던든 문제에 따라서 적절하게 사용하면 알고리즘을 간결하게 표현할 수 있습니다. 앞에서도 말했지만, 재귀호출을 사용해야 하고 중복 계산이 많이 발생하는 경우에는 메모이제이션 기법을 사용하라

는 것입니다. 다음 예제는 메모이제이션과 재귀호출을 이용하여 피보나치 수열을 구하는 파이썬 코드입니다. 

# 빠른 피보나치 수열 구하는 예제입니다.   
# 재귀호출만 사용하는 방식과 비교하면 속도가 엄청나게 빨라집니다. 
# [참고] 그냥 반복문 + 메모이제이션 구조로 처리하면 더 빠릅니다. ^^ 


def fastFib(n, memo):
    if not n in memo:
        memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo)
    return memo[n]


def fibonacci(n):
    memo = {0:1, 1:1}
    return fastFib(n, memo)

print( fibonacci(100) ) 

<이상>