[Python] Memoization 메모이제이션

0. 들어가면면서

 메모이제이션을 찾는다는 것은 기본적인 재귀가 익숙하다는 전제로 설명하겠다.

 

 

1. Memoization

메모이제이션(memoization)은 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술이다. 동적 계획법(DP)의 핵심이 되는 기술이라 할 수 있다. 

 

메모이제이션의 장점인 실행속도를 높이기 위한 설명으로 우선은 재귀로 피보나치수열을 구하는 코드를 확인해 보자.

def fibo(n):
    if n > 3:            # 이 부분이 있어야 무한정으로 n값이 낮아지지 않는다.
        return 1
    else:
        return fibo(n-1) + fibo(n-2)

여기서의 가장 큰 문제는 호출을 계속하면 같은 수에 대해 엄청난 호출이 들어간다. 쉽게 말하면 fibo(7) fibo(2)를 8번이나 호출(함수에 들어감)하게 된다. 이러한 문제의 해결책이 메모이제이션이다. 메모이제이션은 한번 부른 것들을 미리 저장해 둔다. 그리고 함수호출을 하지 않고 앞에서 저장해 논 것을 이용해서 사용한다.

 

 

 

Memoization 방법을 적용한 fibo

# memo를 위한 리스트를 생성한다.
# memo[0]을 0으로 memo[1]은 1로 추기화를 한다. 
def fibo(n):
    global memo
    if n >= 2 and len(memo) <= n:
        memo.append(fibo(n-1) + fibo(n-2))
    return memo[n]
memo = [0, 1]