[Algorithm] 동적계획법

동적계획법

동적 계획법은 수학 이론에서 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

동적 계획법의 원리는 매우 간단하다. 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 부분 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.

 

분할정복 vs 동적계획법 (부분문제의 중복)

전체 문제를 부분문제로 분할하여 정의하고, 부분문제의 해를 조합하여 전체 문제의 해를 찾는다는 점에서 동적계획법은 분할정복과 매우 비슷하다. 그렇다면 두 설계 전략에는 어떤 차이가 있을까?

가장 중요한 차이는 분할된 부분문제가 서로 중복되는지이다.

일반적인 분할정복 전략으로 해결하는 문제들은 부분 문제들을 서로 독립적이도록 분할한다.

하지만 오른쪽 그림과 같이 부분문제들 사이에 중복이 생기도록 분할이 되는 문제들도 존재한다.

이처럼 분할정복과 동적계획법과 차이는 부분 문제의 중복으로 구분할 수 있다.

하지만 위 경우, 문제 해결을 위한 알고리즘은 작성이 가능하지만, 엄청난 시간과 메모리를 소모하게 된다.

다음은 중복이 있는 형태로 이항계수 문제를 분할하여 수행하는 경우이다.

그림에서 볼 수 있는 것처럼 같은 문제를 몇번이나 반복해서 다시 계산하게 된다.

이러한 중복 문제를 해결하기 위해 아주 간단하면서도 좋은 방법이 있다.

한번이라도 답을 구했던 문제에 대해서는 따로 자료구조를 만들어 답을 저장해두는 것이다.

그리고 이후에 다시 해당 부분문제에 대해 함수호출이 일어나는 경우,

다시 답을 계산하는 것이 아니라 자료구조에서 답을 바로 리턴시키도록 한다.

이러한 전략을 메모이제이션(Memoization)이라 부른다.

 

피보나치를 예제로 코드를 보자

일반적인 피보나치 수 코드이다.

// 일반적인 피보나치 수 재귀함수
// 인풋이 조금만 커져도 시간과 메모리를 엄청나게 잡아먹게 된다.
int Fibo(int n)
{
    if (n == 0)
        return 0;

    if (n == 1)
        return 1;

    return Fibo(n - 1) + Fibo(n - 2);
}

 

다음은 위에서 언급한 방법, 메모이제이션을 활용한 구현이다.

int mem[101] = {};
int Fibo(int n)
{
    if (n == 0)
        return 0;

    if (n == 1)
        return 1;

    if (mem[n] != 0)
        return mem[n];

    cout << n << " ";
    return mem[n] = Fibo(n - 1) + Fibo(n - 2);
}

이처럼 메모이제이션을 이용하면 지수적으로 증가하는 시간복잡도를 선형적 시간복잡도까지 감소시킬 수 있다.

이런 메모이제이션의 시간복잡도를 단순하면서 직관적이게 계산할 수 있는 방법은, 해결하려는 문제가 차지하는 공간과 한 부분문제가 필요로 하는 시간복잡도를 보는 것이다. 위 피보나치 수의 경우, 그 문제를 해결하기 위해 하나의 부분문제를 해결할 때마다 하나의 공간을 채우게 된다. 모든 공간이 다 차게 되면, 그 이후로는 어떤 인풋이 들어오더라도 O(1)시간 안에 문제에 대한 답을 낼 수 있다. 그러므로 결국 모든 부분문제에 대한 공간, 즉 모든 인풋에 대한 답을 생성하면 되기 때문에 O(N)의 시간복잡도를 갖는다는 것을 알 수 있다.

 

메모이제이션을 적용하는 경우 주의해야하는 점이 있다.

이는 수학에서의 함수와, 프로그래밍에서의 함수 사이에 차이를 통해 예를 들 수 있는데,

수학에서의 함수 F(x, y)는 어떤 인풋 x, y가 정해졌다면 그에 대한 아웃풋은 항상 동일하다.

이를 함수의 참조적 투명성 (Referential Transparency)이라 부른다.

하지만 프로그래밍의서의 함수 F(x, y)는 함수를 어떻게 구현했느냐에 따라 같은 인풋이 들어와도 다른 아웃풋이 나올 수 있다. 이는 프로그래밍에서 사용하는 여러 전역변수나, 초기화되지 않고 사용되는 자료구조들로부터 나타나는 특성이다.

물론 이러한 특성은 어떤 부분에서는 굉장히 유리하겠지만, 동적계획법에서 메모이제이션을 하는 상황에서는 그렇지 않다. 메모이제이션은 최초 한번 최적해를 구한 상태로 해당 메모리의 값이 고정되기 때문에, 같은 인풋에 대한 다른 아웃풋이 있어서는 안된다. 그러므로 최대한 참조적 투명성을 지킬 수 있는 방향으로 코드를 작성하도록 하자.

 

동적계획법 설계 방법

최적 부분 구조

동적계획법으로 문제를 해결하기 위해 먼저 최적 부분 구조에 대한 이해가 필요하다.

최적 부분 구조란 어떤 문제를 부분문제로 나누었을 때,

이 부분문제들이 최적으로 해결되었다면, 이들이 구체적으로 어떤 형태로 해결되었는지 모르더라도 전체 문제의 최적해를 구할 수 있는 구조를 의미한다.

A->B로 가는 최단 경로를 생각해보자.

이 최단 경로는 항상 X를 지나간다고 가정해보자.

그렇다면 A->B라는 전체 최단경로는 A->X와 X->C라는 부분 최단경로의 합으로 표현해도 최단경로이다.

그러므로 이 문제는 최적 부분 구조를 갖는다고 할 수 있다.

하지만 전체 문제의 최적해를 구하기 위해 부분문제의 최적해 외에도 어떤 형태로 이 최적해를 구하게 되었는지와 같은 여러 다른 값들을 참조해야하는 경우 그 문제는 최적 부분구조를 갖지 않는다고 볼 수 있다.

동적계획법을 정확하게 적용하기 위해서는 해당 문제가 최적부분구조를 갖는지 판단할 수 있어야 한다.

또한 최적부분구조를 갖지 않더라도, 전처리나 추가 처리등을 통해 최적 부분구조로 변환할 수 있어야 할 것이다.

 

점화식

문제가 최적 부분구조를 갖는다는것을 알았다면 점화식을 새워야한다.

점화식은 분할정복에서의 방법과 매우 흡사한 방법으로 정의할 수 있다.

 

1. 해결해야하는 문제를 더 작은 부분문제로 분할

2. 부분문제들을 통해 얻은 답들을 이용하여 현재 문제에 대한 답을 정의한다.

3. 더 이상 분할할 수 없는 단위 처리

 

피보나치 수를 예로 들면 다음과 같다.

1. Fibo(n)이라는 큰 문제를 Fibo(n - 1)과 Fibo(n - 2)로 분할한다.

2. Fibo(n - 1)과 Fibo(n - 2)를 이용하여 Fibo(n)을 정의, Fibo(n) = Fibo(n - 1) + Fibo(n - 2)

3. Fibo(1) = 1, Fibo(0) = 0

 

메모이제이션

점화식을 구했다면, 이제 메모이제이션과 재귀함수를 이용하여 알고리즘을 구현한다.

점화식은 재귀함수로 아주 쉽게 대응시킬 수 있다. 초기값 => 기저조건, 점화식 => 재귀호출

답을 저장할 배열을 정의하고, 배열의 차원과 크기는 인풋으로 들어올 수 있는 인자와 범위만큼 잡아준다.

그 후, 답을 한번이라도 구했다면, 배열에서 답을 반환하도록 하고, 최초로 구했다면 배열에 저장하도록 한다.

 

메모이제이션의 경우, 초기값은 현재 문제에서 해로 구할 수 없는 값으로 설정하는것이 안전하다.

그리고 피보나치수열이 아닌 다른 문제의 경우 인풋으로 여러 값들을 받을수도 있는데, 이런 경우 배열의 차원을 높여주어 처리하면 편하다.

ex) 이항계수의 경우 2차원으로 처리

int mem[500][100] = {};
int Bino(int n, int k)
{
// ...
}

또한 반드시 배열로만 메모이제이션이 가능한 것은 아니다.

인풋의 형태가 복잡하거나, 복합적인 경우, 배열에 인덱스로 표현하기 어려울 수 있고,

그런 경우, 비트마스크, 해시테이블 등 여러 다른 자료구조로 메모이제이션 자료구조를 설계할 수 있을 것이다.

// 이진트리를 이용한 메모이제이션
// O(NlogN)
int Fibo(map<int, int>& mem, int n)
{
    if (n == 0)
        return 0;

    if (n == 1)
        return 1;

    // 답을 한번이라도 구했다면, 바로 반환
    auto it = mem.find(n);
    if (it != end(mem))
        return it->second;

    // 최초로 답을 구하는 경우 배열에 저장
    int ans = Fibo(mem, n - 1) + Fibo(mem, n - 2);
    mem.insert(make_pair(n, ans));
    return ans;
}

 

반복문

동적계획법으로 문제를 해결하는데에는 메모이제이션과 재귀를 활용한 방법 외에도, 

배열과 반복문을 이용한 방법이 있다.

이 방법은 상대적으로 재귀 & 메모이제이션 전략보다는 비직관적이지만, 

코드가 간결하고 성능이나 메모리 측면에서 메모이제이션보다 우수하다.

기본적으로 점화식을 구하는 부분까지는 동일하다. 

점화식을 구한 후 재귀함수의 경우에는 top-down 방식으로 해를 만들어나가는 반면,

반복문을 활용한 방법은 해를 bottom-up 방식으로 쌓아올려가도록 설계한다.

// 배열과 반복문을 이용한 방법
int FiboIterate(int n)
{
    int mem[101] = { 0 };
    mem[0] = 0;
    mem[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        mem[i] = mem[i - 1] + mem[i - 2];
    }
    return mem[n];
}

이 방법을 이용할 때 가장 주의해야할 점은 밑에서부터 해답을 쌓아올리는 방식이기 때문에 현재의 해답을 구하기 위해서는 반드시 이전의 해답을 알아야 한다는 것이다.

즉 더 작은 부분문제의 해답들은 현재의 해답이 구해지기 전에 반드시 구해져야 한다.

당연한 말처럼 들릴 수 있겠지만, 대부분의 동적계획법 문제들은 점화식이 피보나치 수 처럼 단순하기 이전 상태 몇개만 참조해오지 않는다. 다양한 위치에서의 부분문제 상태들을 참조하기 때문에, 이 부분문제에 대한 답이 순서대로 잘 구현되게 하려면, 반복문의 처리 순서도 복잡해질 수 있다.

또한 배열을 활용한 방법의 경우 기저의 처리도 잘 신경써주어야 한다.