파이썬 메모이제이션 (Python memoization)

메모이제이션(memoization) 이란?

• 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 저장함으로써 동일한 계산의 반복 수행을 제거
• 프로그램 실행 속도를 빠르게 하는 기술로 동적 계획법의 핵심이 되는 기술

 

https://ko.wikipedia.org/wiki/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98

 

 

팩토리얼 구하기

 

<메모이제이션을 사용하지 않은 경우>
아래와 같은  팩토리얼을 계산하는 재귀 함수의 경우,
함수가 호출될 때마다 n!을 계산하기 위해 n * (n-1) * (n-2) * ... * 1의 계산을 수행한다.
이런 경우, 재귀적으로 구현되어 있기 때문에, 큰 입력값에 대해서는 계산 속도가 매우 느려진다.

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(5)) # Output: 120
print(factorial(10)) # Output: 3628800

 

<메모이제이션을 사용한 경우>

따라서, 메모이제이션(memoization)을 이용하여 팩토리얼(factorial)를 구한다.
아래와 같이  factorial_dict라는 딕셔너리를 생성하여, 이전에 계산한 팩토리얼 값을 저장하고,
함수가 호출될 때마다 먼저 딕셔너리에 입력값이 있는지 확인하고, 있다면 이전에 계산한 값을 이용한다.
입력값이 딕셔너리에 없다면 새롭게 계산하고 딕셔너리에 저장하면 된다.

예를 들어, memoized_factorial(5)를 처음 호출하면 함수 내부에서 5!을 계산하고, 이를 factorial_dict[5]에 저장한다.
이후에 memoized_factorial(5)를 다시 호출하면 함수 내부에서 factorial_dict[5]의 값을 반환하므로 계산을 다시 수행하지 않아도 된다.

 

# create a dictionary to store previously computed factorials
factorial_dict = {}

def memoized_factorial(n):
    # base case: 0! = 1
    if n == 0:
        return 1
    
    # check if the factorial of n has already been computed
    if n in factorial_dict:
        return factorial_dict[n]
    
    # if the factorial of n has not been computed, compute it recursively
    factorial = n * memoized_factorial(n-1)
    
    # store the computed factorial in the dictionary for future use
    factorial_dict[n] = factorial
    
    return factorial
    
print(memoized_factorial(5)) # Output: 120
print(memoized_factorial(10)) # Output: 3628800

 

피보나치 수열 구하기

 

<메모이제이션을 사용하지 않은 경우>

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(10)) # Output: 55
print(fibonacci(20)) # Output: 6765

 

<메모이제이션을 사용한 경우>

fibonacci_cache = {}  # 메모이제이션에 사용할 딕셔너리 생성

def fibonacci(n):
    if n in fibonacci_cache:  # 딕셔너리에 저장된 값이 있다면, 해당 값을 반환
        return fibonacci_cache[n]
    
    # 딕셔너리에 저장된 값이 없다면, 계산하여 딕셔너리에 저장하고 반환
    if n <= 1:
        value = n
    else:
        value = fibonacci(n-1) + fibonacci(n-2)
    fibonacci_cache[n] = value
    return value

print(fibonacci(10)) # Output: 55
print(fibonacci(20)) # Output: 6765