메모이제이션 - Memoization

컴퓨터 프로그래밍 용어로, 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써 중복 계산을 방지할 수 있게 하는 기법이다. 동적 계획법의 핵심이 되는 기술로서 결국 메모리라는 공간 비용을 투입해 계산에 소요되는 시간 비용을 줄이는 방식이다.

아래는 피보나치 수열을 예로 들은 사진이다.

위와 같이 4번째 피보나치 수열을 구하는 데 함수 f를 호출하는 횟수는 총 9번이다. 위의 예시에서 중복해서 계산하는 값만 따져 봐도 f(2)가 2번(+1번), f(1)을 3번(+2번), f(0)을 2번(+1번) 계산한다. 9번의 계산 중에 무려 4번을 중복해서 계산하는 셈이다. 비록 위 예시는 비교적 작은 값을 제시했지만, 피보나치 수열을 순진(naive)한 방법으로 구할 경우 시간복잡도는 피보나치 수열의 값에 따라 폭발적으로 증가한다. 즉 O(1.6^N)다.

그러나 중복되는 값(미리 구한 값들)을 새로운 배열에 저장하고 중복연산을 방지한다면 시간복잡도를 O(N)까지 줄일 수 있다.