Q. 메모이제이션이란?
글자 그대로 해석하면 ‘메모리에 넣기’라는 의미. 출처. 위키백과
피보나치 구현 예
def fib(n):
if n == 1 or n == 2:
return 1
return fib(n-1) + fib(n-2)
fib(10)실행결과는 55이다.
메모이제이션을 활용해서 피보나치 구현 예
memo = {}
memo[1] = 1
memo[2] = 1
def fib(n):
if n not in memo:
memo[n] = fib(n-1) + fib(n-2)
return memo[n]
fib(10)똑같이 실행결과는 55이다.
속도차이를 비교해보자.
그냥 구현한 경우 50을 구하는데 얼마나 걸릴까. 끝나지를 않는다. 계속 돌고 있다.
메모이제이션을 활용한 경우 금방 끝난다. 이미 구한 경우는 재활용하니까.
