[알고리즘] 메모이제이션(memoization)

메모이제이션(memoization)이란?

1. 동적 프로그래밍(DP: Dynamic Programing)의 핵심이 되는 기술이다.

2. 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 재사용하여 중복 계산을 방지할 수 있게 하는 기법이다.

3. 중복 계산을 방지하여 전체 실행 속도를 빠르게 한다.

4. 이론적인 용어라 코딩 테스트, 알고리즘에서만 사용하는 용어이고 실제 현장에서는 캐싱(caching)이라는 단어를 더 많이 사용한다.

 

예)

 - 피보나치 수열: f(n-1), f(n-2)의 값을 메모이제이션하여 f(n)을 계산한다.

 - 팩토리얼을: f(n-1), f(n-2) .... 1의 값을 메모이제이션하여 f(n)을 계산한다.