[Dynamic programming/DP]Memoization (메모이제이션)

Memoization

메모이제이션은 입력값에 대한 결과를 저장하고 다음에 같은 입력값이 오면 한 번만 실행하도록 하는 알고리즘

함수를 한 번만 실행할 수 있어 실행시간을 단축시켜 효율적으로 사용할 수 있다는 장점

동적계획법에서 흔하게 사용

 

 

예시: 피보나치 수열

1. 메모이제이션을 사용하지 않은 흔한 재귀의 경우

계속해서 다시 재계산을 하기 때문에 num 커질수록 overhead 커짐

시간복잡도 O(2^n)

 

2. 메모이제이션 사용

이미 한 번 연산한 내용은 저장하여 저장된 data를 불러오기

 

시간복잡도는 O(n)

 

import sys
n = int(sys.stdin.readline())

class Fibo(object):
    def __init__(self):
        self.memo = {0: [1, 0], 1: [0, 1]}

    def fib(self, n):
        if n in self.memo:
            return self.memo[n]
        else:
            res_0 = self.fib(n-1)[0] + self.fib(n-2)[0]
            res_1 = self.fib(n-1)[1] + self.fib(n-2)[1]
            res = [res_0, res_1]
            self.memo[n] = res
            return res
        
fibo1 = Fibo()
for i in range(n):
    tmp = int(sys.stdin.readline())
    nlist = fibo1.fib(tmp)
    print(nlist[0], nlist[1])

메모이제이션을 적용한 파이썬 코드