#term memoization, 메모이제이션

계산한 값을 메모리에 저장해서 여러 번 같은 값 계산을 피하는 최적화 기법을 메모이제이션(memoization)이라고 한다. 실행 속도와 공간을 바꾸는 가장 기초적인 기법이기도 하다. 실수로 메모리제이션이라고 하기도 하는데 메모이제이션이 정확한 용어이다.

이 용어를 몰랐을 때는 데이터나 값을 미리 복사해 놓거나 계산해 놓은 임시 장소를 뜻하는 캐시(cache)에 저장하는 동작, 즉 캐싱(caching)이란 용어를 쓰곤 했다. 데이터를 미리 계산해서 임시 장소인 메모리에 저장해놓는 동작이라 캐싱이란 용어도 틀린 말은 아니다. 하지만, 딱 가리키는 용어인 메모이제이션이 있으니 이걸 쓰는 게 맞겠지.

메모이제이션을 사용하는 피보나치 수열을 계산하는 코드이다. 역시 예를 들때는 피보나치 수가 최고지.. 암~

// 안전 코드를 제외한 간단한 코드 조각

// 메모리 초기화.
const static int NOT_VALID = -1;
const static int MEMO_MAX = 10000;

std::vector<int> memo;
memo.resize( MEMO_MAX );
std::fill( memo.begin(), memo.end(), NOT_VALID );

// 피보나치 초기화
memo[0] = 0;
memo[1] = 1;

int fib( int n )
{
    if( memo[n] != NOT_VALID )      return memo[n];
    memo[n] = fib(n-1) + fib(n-2);  // memoization
    return memo[n];
}