[Python] - 16) 메모화

저번 포스팅에서 재귀 함수는 계산을 반복하기 때문에 문제점이 많다고 했습니다. 

이번 포스팅에서는 이로 인해 생기는 문제점인 메모화 기술을 알아보겠습니다.

먼저, 재귀 함수도 복습할 겸, 생기는 문제점을 실감하기 위해 재귀 함수를 이용해 피보나치 수열을 작성하는 코드를 살펴볼게요!

코드 입력 화면

코드 실행 화면

위의 코드 처럼 입력하면 굉장히 잘 짜여진 코드라고 생각할 수 있지만 저 코드로 피보나치 수열의 40 번째 항을 계산해보세요.

코드가 바로 40번째 항을 출력해주나요??

아닙니다!! (컴퓨터에 따라 다르겠지만 저는 한 3~4초정도 걸렸어요.)

더 높은 항을 구하려고 할 수록 걸리는 시간은 기하급수적으로 늘어나게 됩니다.(아까 언급하기도 했지만 계산을 많이 반복하기 때문)

그렇다면 코드를 작성해서, 얼마나 반복하는지도 알아보겠습니다.

(배운 적이 없는 코드인 것 같으니 그냥 일단 한번 따라 쳐볼게요! counter, global 등등 나중에 나와요!!)

코드 입력 화면

.

.

.

코드 실행 화면

위의 코드를 통해 피보나치 10번째 항을 구할 때 계산하는 횟수는 총 109 번인 것을 알 수 있습니다. 

그렇기 때문에 시간이  점점 오래걸리는 것입니다.

 

 

그렇다면, 같은 값을 여러번 계산하는 과정을 줄여준다면, 코드가 굉장히 빠르게 실행되지 않을까요? 

딕셔너리를 사용해서 한 번 계산한 값을 저장해주면 되는데, 이를 메모한다 라고 표현합니다!

코드 입력 화면

코드 실행 화면

솔직히, 이렇게 딕셔너리에 계산한 값 넣어주는 방법으로 재귀 함수의 반복 줄여주는거 보고 진짜 너무 신기했습니다.

(방탈출 하는 것 같고,,, 약간 내 스타일?? 이게 바로 코딩의 재미인가...)

이 신기함이 언제까지 갈진 모르겠지만 오래 갔으면 좋겠네요ㅠㅠ

이번 포스팅은 여기서 마칠게요. 

다음 포스팅은 튜플로 이어갑니다!!

 

 

'Hello Coding 파이썬' 을 참고하여 작성하였음.