메모이제이션

메모이제이션은 함수의 입력에 대응하는 결과를 저장해 같은 계산의 반복을 줄이는 기법이다. 재귀형 동적 계획법에서 자주 사용한다.

원리

호출 때 먼저 저장된 결과를 확인하고, 없다면 계산해 보관한다. Python의 functools.cache는 이런 방식의 캐시를 제공한다.

예시

피보나치 수를 단순 재귀로 구하면 같은 n을 여러 번 계산한다. 각 n의 결과를 저장하면 서로 다른 상태만 계산하게 된다.

주의할 점

결과가 시간이나 외부 상태에 의존하면 입력만으로 만든 캐시가 오래된 값을 반환할 수 있다. 메모리 사용량, 캐시 무효화와 동시 실행 정책도 고려한다.

참고 자료