[Algorithm] 메모이제이션(Memoization)

메모이제이션

메모이제이션은 메모리에 넣기라는 의미로 기억되어야 할 것이라는 뜻의 라틴어 memorandu에서 파생되었다. 

프로그램이 같은 계산을 반복해야할 때, 이전에 계산한 값을 메모리에 저장함으로써 같은 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 방법이다. 동적 계획법의 핵심이 되는 기술로 메모리라는 공간 비용을 사용하여 계산에 필요한 시간 비용을 줄이는 방법이다. 캐싱이라고 표현하기도 한다.

 

 

예시 - 피보나치 수열

아래와 같이 재귀함수를 이용한 피보나치 수열 함수가 있다고 하자.

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

fib 함수의 재귀호출을 트리 형태로 나타내면 아래와 같다. 5번째 피보나치 수를 계산하는데 총 15번의 함수 호출이 필요하다. 

fib(0)을 3번, fib(0)을 5번 계산하는 등 중복 계산도 많다. 

이것을 저장공간을 활용하여 이전에 계산했던 값은 계산 없이 가져오도록 수정하면 중복 계산을 줄일 수 있다.

memo = [0, 1]

def fib(n):
    l = len(memo)
    if l < n:
        for i in range(l, n):
            memo.append(memo[i - 1] + memo[i - 2])
    return memo[n - 1]

트리로 표현하면 아래와 같다.

 

 

참고 문서

https://ssminji.github.io/2020/02/05/the-cake-thief/

메모이제이션