메모이제이션(Memoization)기법 Python으로 알아보기

안녕하세요!

오늘은 메모이제이션(Memoization)에 대해 알아보려 합니다.

메모이제이션이 뭐냐?? 

메모이제이션은 동일한 연산을 반복해야 할 때 이전에 연산한 값을 메모리에 미리 저장해 둠으로써 계산의 반복수행을 제거하여 프로그램 실행 속도를 향상시키는 기술입니다. 메모리에 저장해뒀다가 사용한다는 점에 있어서 캐싱의 범주에 속한다고 보면 될 것 같은데요.

메모이제이션은 어떤 함수의 인풋에 대한 아웃풋을 저장한다고 보시면 되고 (함수를 위한 캐싱), 우리가 보통 말하는 캐싱은 외부에서 들어오는 파일, 데이터를 저장해서 사용하는 용어로 생각하시면 될 것 같습니다. (혹시라도 틀린 부분이 있다면 꼭 댓글 남겨주세요!)

메모이제이션의 특징으로는, 보통 실행 속도가 빠른 알고리즘이 더 많은 메모리를 사용하듯이, 이 메모제이션 기법도 메모리 공간을 희생하고  수행 속도를 향상시킵니다.

그렇기 때문에 다음과 같은 조건이 필요합니다.

 

1. 연산에 있어 많은 메모리를 사용하지 않는 함수

2. 같은 입력에 대해 같은 출력을 내는 함수 (동일한 인풋 -> 동일한 아웃풋)

3. 반복되는 함수 결과 값 사용 (조건이라기보다는 사용하는 목적이 맞겠네요!)

 

메모이제이션 기법을 사용하면 좋은 대표적인 예로 피보나치 수열이 있습니다.

피보나치 수는 1, 1, 2, 3, 5, 8... 로 다음과 같은 점화식으로 나타낼 수 있는데요.

즉 n>2 항부터 f(n) = f(n-1) + f(n-2)를 만족하는 수열입니다. 

점화식을 보시면 아시겠지만, f3 = f2 + f1,  f4 = f3 + f2로   f2의 경우 이미 이전에 계산했음에도 또다시 계산하게 됩니다. 만약 f2에 대한 결과값을 메모리에 갖고 있다면? 불필요한 연산을 하지 않아도 되겠죠? 

연산이 중복되는게 보이시죠??

그럼 파이썬으로 메모이제이션기법을 사용하지 않은 피보나치수와 메모이제이션기법을 사용한 피보나치수의 실행시간을 비교해보겠습니다. 

# 메모이제이션 기법 사용x

def fib(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return fib(n-1) + fib(n-2)

 

# 메모이제이션 기법 사용O

dic = {1:1, 2:1}

def fib_memoization(n):
    if n in dic:
        return dic[n]
    
    dic[n] = fib_memoization(n-1) + fib_memoization(n-2)
    return dic[n]

 

각각 40번째 피보나치 수를 구한다고 했을 때 시간 측정을 해본 결과 메모이제이션 기법을 사용하지 않았을 경우 약 32초가 나왔고  메모이제이션 기법을 사용한 경우는 0.00026초가 나왔습니다. ㅎ;; 뭐 굳이 몇 배 차이인지 계산 안 해도 엄청나게 차이가 많이 나죠?? (약 123076배네요)

이 메모이제이션기법은 DP(동적 계획법)에서 사용되는 방법이고 어려운 개념이 아니기 때문에 잘 숙지하고 있으면 좋을 것 같습니다.

읽어주셔서 감사합니다.