동적 계획법

1. 도입

동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나이다. 동적 계획법이라는 말은 최적화 문제를 연구하는 수학 이론에서 왔다.

중복되는 부분 문제

동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 동적 계획법을 사용하는 알고리즘들 또한 처음 주어진 문제를 더 작은 문제들로 나눈뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내기 때문이다.
동적 계획법과 분할 정복의 차이가 발생하는 부분은 문제를 나누는 방식이다. 동적 계획법에서 어떤 부분 문제는 두 개 이상의 문제를 푸는데 사용될 수 있기 때문에, 이 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용함으로써 속도의 향상을 꾀할 수 있다.
그러기 위해서는 각 문제의 답을 메모리에 저장해 둘 필요가 있다. 이때 이미 계산한 값을 저장해 두는 메모리의 장소를 캐시(cache)라고 부르며, 두 번 이상 계산되는 부분 문제를 중복되는 부분 문제라고 부른다.

동적 계획법 알고리즘의 가장 유명한 예 중 하나는 이항 계수의 계산으로, 이것은 n개의 원소 중 r개를 순서 상관없이 고르는 조합의 개념과 같은것으로 점화식 역시 만들어 질 것이다. 하지만 이 점화식은 중복 연산을 피할 수 없다. 함수의 중복 호출 수는 n과 r이 커지면서 기하급수적으로 늘어난다.
이런 시간적, 공간적 낭비를 피하기위해서는 어떻게 해야할까? 함수의 입력값이 정해져있을 때 항상 출력값이 같다는 전제조건만 있다면 캐시 배열을 만들어서 이 문제를 해결할 수 있다. 각 입력에 대한 반환 값을 저장하게 하여, 함수는 매번 호출될 때마다 이 배열에 접근해 값이 저장되어 있느지를 확인한 뒤, 저장되어 있다면 이것을 즉시 반환하고 만약 계산되어 있지 않을 경우엔 직접 계산해서 배열에 저장하게 만들면 되는 것이다.

int bino(int n, int r)
{
    if(r == 0 || n == r) return 1;
    return bino(n-1, r-1) + bino(n-1,r);
}

int cache[30][30];
int bino2(int n, int r)
{
    if(r == 0 || n == r) return 1;
    if(cache[n][r] != -1)
        return cache[n][r];
    return cache[n][r] = bino2(n-1, r-1) + bino2(n-1, r);
}

다시말해 이 메모이제이션을 수행하는 알고리즘 설계 기법을 동적계획법(DP)라고 부른다.

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

프로그래밍에서의 함수가 수학의 함수와 다른 점은 바로 함수의 입력 외에도 전역 변수, 입력 파일, 클래스의 멤버 변수 등 수 많은 입력에 의해 작동한다는 점이다. 예를 들어보자.

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

이 함수는 입력이 전혀 없는데도 다른 출력 값을 보여준다. 반대로 입력이 같으면 ㅊ출력도 항상 같은 함수도 작성할 수 있다.
함수의 반환 값이 그 입력 값만으로 결정되는지의 여부를 다른 말로 참조적 투명성이라고 부른다. 입력이 고정되어 있을 때 그 결과가 항상 같은 함수들을 참조적 투명 함수라고 부른다. 당연히 메모이제이션은 참조적 투명성이 보장되어야한 사용가능한 개념이다.

메모이제이션 구현 패턴

항상 같은 구조로 프로그래밍해야 이후 디버깅이 쉬워지므로 한가지만 익히자.
다음과 같은 재귀 함수가 있다고 하자.

int someObscureFunction(int a, intb);

이 함수를 한번 계산하는 데 굉장히 시간이 오래 걸리는 참조적 투명 함수라고 가정한다. 이 함수에 메모이제이션을 적용한다. 이때 다음과 같은 점을 유의한다.

• 항상 기저 사례를 제일 먼저 처리한다. 입력이 범위를 벗어난 경우 등을 기저 사례로 처리하면 매우 유용한데, 기저 사례를 먼저 확인하지 않고 cache[]에 접근하면 범위를 벗어나는 등의 오류가 있을 수 있다.
• 함수의 반환 값이 항상 0이상이라는 점을 이용해서 cache[]를 모두 -1로 초기화한다. cache[]의 해당 위치에 적혀 있는 값이 -1이라면 이 값은 계산된 반환값일리가 없다.
• ret가 cache[a][b]에 대한 참조형이라는 데 유의하라. 참조형 ret의 값을 바꾸면 cache[a][b]의 값도 변하기 때문에 답을 저장할 때도 매번 귀찮게 cache[a][b]라고 쓸 필요가 없다. 이 방식은 캐시가 다차원 배열일 때 유용하다.
• memset()을 이용해 cache를 초기화할 수 있다. 하지만 for문으로 하는 것이 동작속도가 더 빠르다.

int cache[2500][2500];//-1로 초기화해야한다.

int someObscureFunction(int a, int b)
{
    // 기저 사례 검사
    if(...)return ;

    //(a,b)에 대한 답을 구한 적이 있다면 곧장 반환
    int& ret = cache[a][b];
    if(ret != -1) return ret;

    //이후 답을 계산
    ...
    return ret;
}

int main()
{
    for(int i = 0; i<2500; i++)
        for(int j = 0; j<2500; j++)
            cache[i][j] = -1;
}

메모이제이션의 시간 복잡도 분석

메모이제이션의 시간 복잡도를 추정하는 간단한 계산식이 있다.

(존재하는 부분 문제의 수)x(한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)

외발뛰기 문제 풀이

결국에는 메모이제이션을 통한 재귀호출인 동적 계획법으로 푸는 문제였다. 여기서 중요한 점은 큰 문제를 작은 부분으로 나누면서 어느 한 루트라도 true가 발생하면 전체의 문제가 true가 되도록 구성해야한다는 점이다. 메모이제이션을 디버깅해보면 처음부터 캐시를 채우는 것이 아니라는 것을 알 수 있다. 로직에서 구현한 가장 작은 단위의 리턴값부터 캐싱이 되므로 처음에는 시간을 많이 사용하지만 이후 중복 루틴에서 많은 시간을 아끼는 것을 알 수 있다.

동적 계획법 레시피

대개 동적 계획법 알고리즘의 구현은 다음과 같은 두 단계로 이루어진다.

• 주어진 문제를 완전 탐색을 이용해 해결한다.
• 중복된 부분 문제를 한 번만 계산하도록 메모이제이션을 적용한다.
  
  

전통적 최적화 문제들

동적 계획법의 가장 일반적인 사용처는 최적화 문제의 해결이다. 최적화 문제란 여러 개의 가능한 답 중 가장 좋은 답(최적해)을 찾아내는 문제를 말한다. 사실 동적 계획법은 처음에 최적화 문제의 해답을 빨리 찾기 위해 노력하는 과정에서 고안되었다.
최적화 문제를 동적 계획법으로 푸는 것 또한 완전 탐색에서 시작하지만, 최적화 문제에 특정 성질이 성립할 경우에는 단순히 메모이제이션을 적용하기보다 좀 더 효율적으로 동적 계획법을 구현할 수 있다.
전통적인 방법론에서는 메모이제이션의 범위가 너무 넓어질 수 도 있다. 이것은 문제자체를 부분 문제로 바꿀 경우 해결될 수 도 있다. 예를 들어, 경로 최대화의 문제의 경우, 각 단계에서의 최댓값을 구하는 식으로 메모이제이션을 해서 자연스럽게 해결되는 것이다.
이것이 가능하려면 문제를 분할해서 부분문제들을 만들었을 때 각각의 최적해만 있으면 전체의 최적해로 이어진다는 판단이 있어야한다. 즉, 지금까지 어떤 경로로 어느 한 부분 문제에 도달했건, 남은 부분 문제는 항상 최적으로 풀어도 상관없다는 것이다. 이를 최적 부분 구조(Optimal substructure)라고 부른다.

최적화 문제 동적 계획법 레시피

• 모든 답을 만들어 보고 그 중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계한다.
• 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제 정의를 바꾼다.
• 재귀 호출의 입력에 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄인다. 문제에 최적 부분 구조가 성립할 경우에는 이전 선택에 관련된 정보를 완전히 없앨 수 있다.
• 입력이 배열이거나 문자열인 경우 가능하다면 적절한 변환을 통해 메모이제이션할 수 있도록 한다.
• 메모이제이션을 적용한다.