동적 계획법 메모이제이션 패턴 (C++)

동적 계획법..

다이나믹 프로그래밍과 같은 말이다.

 

동적 계획법은 개념 자체는 쉬워서 알고리즘의 기본 난이도는 낮은 편이다.

하지만 메모이제이션을 몸에 익히고 문제를 보고 동적계획법을 떠올리며 어떤 정보를 메모이제이션할지 바로 찾아내는 내공을 가지려면 엄청난 노력이 필요하다고 생각한다. 다른 알고리즘과는 비교가 안될정도로 많이.

 

이 책에는 약 25개 정도의 큼직한 알고리즘 파트가 1000페이지 조금 넘게 기술되어있다.

그 중에서 동적계획법은 160페이지 가량 되는데 비중이 정말 크다고 볼 수 있다.

 

쉬우면 너무 쉽지만 어려우면 말이 안나올정도로 어려운 동적계획법의 가장 기본이 되는 탑다운 메모이제이션 패턴을 알아보자.

 

패턴 코드

// 전부 -1로 초기화
int cache[2500][2500];

int Function(int a, int b){
    if(...) return ...;
    
    int &ret = cache[a][b];
    if(ret != -1) return ret;
    
    // 구현 파트
    
    return ret;
}

int main(){
    // #include <cstring>
    memset(cache, -1, sizeof(cache));
}

 

• 항상 기저 조건을 먼저 처리하자. 입력이 범위를 벗어난 경우를 기저 조건으로 처리하면 유용하다.
• 함수의 반환 값이 항상 0 이상 이라는 점을 이용해 cache[]를 모두 -1로 초기화 하자.
• cache[]에 있는 값이 -1이라면 이 값은 계산된 값이 아니니 새로 계산할 필요가 있다는 말이다.
• 만약 반환값이 음수라면... 배열의 크기를 늘리고 양수의 최댓값+음수절댓값의 위치에 기록을 하면 어떨까?

ret이 cache[a][b]에 대한 참조형 이라는데 유의하자. cache[]가 다차원 배열일 때 매우 유용하다. 귀찮음도 덜어주고 인덱스 순서를 바꿔쓴다거나 하는 실수를 줄여주는 방법이다.

memset()을 이용해 cache[]를 초기화 한다. 다중 for문보다 간단히 초기화를 할 수 있는 방법이다. 하지만 memset()을 이용하는 방법은 매우 제한적인 경우에만 쓸 수 있으니 조심하자.

 

memset() : 두 번째 인자로 주어진 값(-1)을 주어진 메모리의 모든 바이트에 채운다.
만약 배열이 32비트나 64비트 정수형이라면 각 바이트마다 값이 들어가기 때문에 의도치 않은 수로 초기화 될 수 있다.
memset()으로 0 또는 -1로 채울 수 있는데 두 숫자가 가능한 이유는 각 바이트에 해당 숫자를 집어넣고 부호 있는 정수형으로 해석하면 운이 좋게도 해당 숫자와 같아지기 때문이다.