[알고리즘 문제해결전략] 메모이제이션

 

메모이제이션 구현 패턴

 

알고리즘 문제해결전략에서 제시하는 메모이제이션 구현 패턴이다.

 

1. 항상 기저 사례를 제일 먼저 처리한다.

  - 인덱스 오류를 줄일 수 있음. 잘못된 입력이 들어온 경우 처리가 가능함.

 

2. 메모이제이션할 공간을 모두 나올 수 없는 값으로 초기화를 한다.

 - 미리 계산된 반환값이 아님을 알 수 있음.

예를 들어, 모든 반환값이 0 이상으로 보장되는 상황이라면, 메모이제이션할 공간을 모두 -1로 초기화해둔다.

 

3. ret 변수를 두어, cache[a][b]에 대한 참조형(reference)으로 사용하자.

- 매번 귀찮게 cache[a][b]를 쓰지말자. 이 방법은 특히 다차원 배열에 메모이제이션할 때 유용하다.

 인덱스 오류 등 실수를 할 가능성을 없애준다.

 

4. 메모이제이션할 공간을 초기화는 항상 조심하자.

memset함수, fill 함수 등 방법을 잘 활용하자.

 

 

int cache[2500][2500]
// 전부 -1로 초기화해 둔다.
// a와 b는 각각 [0, 2500) 구간안의 정수이다.
// 반환 값은 항상 int형 안에 들어가는 음아닌 정수이다.
 
int someObscureFunction(int a, int b)
{
    // 기저 사례를 처음에 처리한다.
 
    if(...) return ...;
 
    int& ret = cache[a][b];
    if(ret != -1) return ret;
    
    // 이제부터 답을 계산하면 된다.
    ...
 
    return ret;
}
 
int main()
{
    memset(cache, -1, sizeof(cache));
    return 0;
}