TIL #15 Python 예제 review(3) -피보나치(메모화)

피보나치 수열을 재귀함수로 구현할 때 n이 증가 할 수록 계산시간이 기하급수적으로 증가하게 된다. 이런한 문제점을 해결하기 위해 메모화를 한다고 한다. 메모화란 이미 계산된 결과값에 대해서는 저장해 놓으므로 인해 계산하는 과정을 줄이는 작업이다.

코드

메모 = { 1:1, 2:1 }
def fib(n):
    if n in 메모:
        return 메모[n]
    else:
        output = fib(n-1) + fib(n-2) 
        메모[n] = output          
        return output
print(fib(100))

해석

1) '메모'라는 dict에 계산 했던 값들을 저장한다. (2개의 값이 이미 저장되어 있는 것은 초기 피보나치 수열의 값을 초기화 해준것 n=1일 때, n=2일 때)
2) '메모'의 key는 n을 가리키고, value는 n일 때의 피보나치 값을 나타낸다.
3) n이 '메모'에 있으면, 이미 계산해서 저장한 값이므로 다시 계산하지 않고 저장된 값을 return
4) n이 '메모'에 없으면, 계산 후 '메모'에 저장 후 계산 값 return