메모이제이션이란?
중복적으로 계산하는 값들을 저장해 둠으로써 불필요한 중복 계산을 막는 방법입니다.
피보나치 수열 구현에서 이 방법을 사용하는 예시를 잘 확인할 수 있습니다.
문제
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…으로 이어나가는 피보나치 수열에서 입력값에 들어온 숫자번째의 피보나치 수의 값을 구하면 되는 문제입니다.
접근
위 그림처럼 20번째 피보나치 수열을 구한다 하면, 이는 19번째 피보나치 수열과 18번째 피보나치 수열의 합이기 때문에 이 수를 구해야 합니다.
그리고 이를 위해 또 19번째 피보나치 수는 18번째 피보나치 수와 17번째 피보나치 수을 구해야 합니다.
이렇게 연산을 이어나가면 위 사진의 경우만 해도 17번째 피보나치 수를 구하는 과정이 3번이 필요하고 16번째도 3번이 필요하는 등 같은 수를 구하기 위해 여러번 연산을 해야 합니다.
그럼 이런 피보나치 수들을 한번 구할 때 마다 배열에 저장해놨다가 값을 구해놓은 수면 꺼내서 가져오고, 안구해놨으면 연산하는 식으로 변경하면 연산 과정이 훨씬 간결해질 것입니다.
재귀함수만 사용(메모이제이션 X)
def fibo(x):
if x == 0:
return 0
if x == 1:
return 1
return fibo(x - 1) + fibo(x - 2)
n = int(input())
print(fibo(n))fibo()의 인자값이 0과 1이 올 때 까지 계속 재귀함수로 연산하게 될 시 중복으로 연산하는 과정이 많이 생깁니다. 결론적으로 20번째 피보나치 수를 가져오는데에 아래와 같은 횟수의 연산이 일어납니다.
(시간 복잡도: 상한 )
재귀함수와 메모이제이션을 함께 사용
n = int(input())
arr = [-1] * (n + 2)
arr[0] = 0
arr[1] = 1
def fibo(x):
global arr
if arr[x] != -1:
return arr[x]
arr[x] = fibo(x-1) + fibo(x-2)
return arr[x]
print(fibo(n))arr이란 배열에 할당이 안된 값은 전부 -1로 선언합니다.
그리고 할당이 된 피보나치 수는 연산 없이 바로 arr을 통해 값을 가져오고, 할당이 안된 피보나치 수만 연산을 진행하게 하여 메모이제이션을 적용했습니다.
이와 같이 메모이제이션을 적용하면 아래와 같이 연산 수가 확 줄어듭니다.
(시간 복잡도: )