병아리 개발자의 실력 양성기

DP의 핵심요소는 메모이제이션(캐싱)이라고 할 수 있다. 이미 계산한 결과를 저장하는 재귀라고도 할 수 있다. 기억 공간을 반복될 계산결과의 저장에 할당함으로써 귀중한 연산시간을 절약하는 것이다. DP를 이용해 해결할 수 있는 대표적이며 가장 간단한 예로 피보나치 수열이 있다. 어떻게 이 문제가 재귀, top-down DP, bottom-up DP, 그리고 그 기억공간을 추가로 절감하는 방식으로 수행되는지를 살펴본다. 재귀 피보나치 수열은 수학적으로 다음 점화식(recurrence relation)으로 정의된다. $$ f_n = f_{n-1} + f_{n-2} $$ $$ f_0 = 0; \ f_1 = 1 $$ n번째 수를 구하기 위해서는 n-1번째, n-2번째 수를 알아야 하고, 그들을 알기 위해서는 다..

Python의 decorator에 대한 설명으로 대표적인 것이 이름을 출력하는 예제일 것이다. 그러나 실제로 그런 일을 할 일이 별로 없기 때문에 마음에 와닿지가 않아 이해도 잘 되지 않았다. 가장 실용적인 사례로서 DP(dynamic programming)을 위한 memoization의 경우에 활용되는 @cache()라는 decorator를 피보나치 수를 구하는 예제에 적용하여 그 내부 동작을 살펴본다. 먼저 팩토리얼을 구하는 코드를 소개한다. 아래 데코레이터는 @cache로서, DP의 top-down시 많이 활용하는 lru_cache(maxsize=None)과 동일한 결과를 돌려주는 것으로 3.9에서 추가된 함수이다. @cache def factorial(n): return n * factorial(..