동적 계획법과 메모화 재귀

1. 도입

1)  중복되는 부분 문제동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다.

동적 계획법을 사용하는 알고리즘들 또한 처음 주어진 문제를 더 작은 문제들로 나눈뒤 각 조각의 답을 계산하고, 이답들로부터 원래 문제에 대한 답을 계산해 내기 때문이다.

동적 계획법과 분할 정복의 차이가 발생하는 부분은 문제를 나누는 방식이다. 동적 계획법에서 어떤 부분 문제는 두 개 이상의 문제를 푸는데 사용될 수 있기 때문에, 이 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용함으로써 속도의 향상을 꾀할 수 있다. 그러기 위해서는 각 문제의 답을 메모리에 저장해 둘 필요가 있다.

이때 이미 계싼한 값을 저장해 두는 메모리의 장소를 캐시(cache)라고 부르며, 두 번 이상 계산되는 부분 문제를 중복되는 부분문제(overlapping subproblems)라고 부른다.

2) 메모이제이션을 적용할 수 있는 경우

int counter = 0;
int count(){
   return counter++;
}

이 함수는 입력을 전혀 받지 않으면서도 매번 다른 결과를 반환한다. 반면 입력이 같으면 출력도 항상 같은 함수도 작성할 수 있다. 함수의 반환 값이 그 입력 값만으로 결정되는지의 여부를 유식한 말로 참조적 투명성(referential transparency)이라고 부란다. 입력이 고정되어 있을 때 그 결과가 항상 같은 함수들을 참조적 투명함수라고 부른다. 메모이제이션은 참조적 투명 함수의 경우에만 적용할 수 있다. 입력이 같은데도 외부 요소에 따라 다른 값이 반환된다면 캐싱을 할 수가 없다.

3) 메모이제이션 구현 패턴

int cache[2500][2500];

int someObscureFuntion(int a, int b){
    if(...) return ...;
    int& ret = cache[a][b];
    if(ret != -1) return ret;
    ...
    return ret;
}

최적 부분 구조(optimal substructure) : 각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 쉽게 얻어낼 수 있을 경우 이 조건이 성립함. 지금까지의 선택과 상관없이 각 부분 문제를 최적으로 풀기만 하면 전체 문제의 최적해도 알 수 있다. 지금까지 어떤 경로로 이 부분 문제에 도달했건 남은 부분 문제는 항상 최적으로 풀어도 상관없다는 뜻.

 

메모화 재귀는 동적 계획법을 재귀적으로 사용하는 것으로 동적 계획법의 일종이라고 생각해도 상관없다.

같은 계산을 한 번만 수행하는 것이 동적 계획법의 본질적인 부분이다.

한 번 계산한 것은 두 번 계산하지 않는다는 원칙을 확실하게 기억하는 것이 좋다.

위에서 아래로 내려가는 하향식 방법이 아니라 아래에서 위로 올라가는 상향식 방법을 사용하면 재귀 함수를 사용하지 않아도 문제를 풀 수도 있다.