빠른 프로그램, 동적 프로그래밍

프로그래밍 언어 관련 수업을 듣다 보면 재귀 호출에 대해서 배우게 된다.

어떤 알고리즘을 해결하면서 재귀 함수는 꽤 중요한 역할을 가지고 있는데, 피보나치 수열의 항이나 수의 분할 정도를 하는 경우가 많다.

unsigned long long stupid(unsigned long long n) {
    return (n == 1 || n == 2) ? n - 1 : stupid(n - 1) + stupid(n - 2);
}

1이나 2일때는 0, 1을 반환하고 그렇지 않을때는 이전 항과 그 전 항의 합을 반환한다. 이때 이전 항을 다시 구하게 되는 것이다.

아주 간단한 모습을 하고 있으면서 원하는 결과를 뱉기는 한다. 10정도를 넣으면 34라는 올바른 결과를 반환한다. 하지만 n에 100을 넣으면?

위의 코드는 n이 하나 늘어날 때 마다 연산이 두배가 되는, O(2^n)이라는 끔찍한 코드이다. 아무리 CPU의 연산이 빨라졌다 하지만 시간이 걸리는 것은 매한가지. 열번째 항을 구하는데 109회의 호출, 스무번째 항을 구하는데 13529회의 호출이 필요하다.

덧셈을 두 개의 Thread로 나눠서 병렬화하는 해법을 내놓는 사람이 있을 수도 있는데, 하지마라. 근본적으로 잘못된 알고리즘을 병렬화로 해결하는 것은 문제 덮기에 불과하다. 오히려 두배씩 늘어나는 Thread를 감당할 수가 없을 것이다. 실제로 해봤다가 (n = 50) 맹렬한 열을 뿜으며 20분간 멎어있는 i7을 보았다.

이러한 알고리즘의 가장 큰 문제는 했던 연산을 다시 한다는 것. 이 때문에 동적 프로그래밍이라는 이야기가 탄생했다.

사람을 생각해도 피보나치 수열을 구하면서 하나씩 쓰고 앞에서부터 구하며 마지막 항을 구할때는 마지막의 전 항과 그 전 항의 합만 구하지 일일히 처음부터 구하지 않는다. 작성하는 프로그래머 조차 손으로 시키면 그러지 않을 짓을 컴퓨터한테 시키는 것이다. 심지어 병렬화를 하는 것은 고작 수 두개를 더하는데 그 만큼의 사람을 데려다가 나눠서 시키겠단 뜻이다. 심각하게 비효율적인 방법일 것이다.

그렇다면 프로그램도 이전 결과를 기억하게 해보자. 우리가 흔히 사용했던 배열 또는 포인터를 이용하면 아주 간단할 것이다.

#pragma once
#include <cstring>

class Fibonacci {
private:
    unsigned long long *map;
    const unsigned long long n;

public:
    Fibonacci(unsigned long long n) : n(n) {
        map = new unsigned long long[n];
        std::memset(map, 0, sizeof(unsigned long long) * n);
    }

    ~Fibonacci() {
        if (map != nullptr) {
            delete[] map;
            map = nullptr;
    }

    inline unsigned long long great() {
        return great(n);
    }

private:
    static unsigned long long great(unsigned long long n) {
        if (n == 1 || n == 2) return n - 1;

        if (*(map + n - 1) == 0) *(map + n - 1) = great(n - 1) + great(n - 2);

        return *(map + n - 1);
    }
};

따로 소스파일을 작성하기 귀찮아서 헤더에 몽땅 넣은 필자를 욕해라..

결과가 저장될 공간을 하나 마련해둔 뒤 이전 계산 결과가 없으면 계산 결과를 채우고 계산 결과만 반환하도록 했다. 이렇게 한다면 매번 이전 계산 결과의 이전 계산 결과의 이전 계산 결과의 이전 계산 결과 ...를 구할 필요가 없어진 것이다.

이렇게 시간복잡도는 O(n)이라는 획기적인 시간 단축을 이룰 수 있다. 물론 이제는 기억하는 공간이 필요하므로 O(n)이라는 공간복잡도가 필요해진다. 물론, 동적 프로그래밍 기법을 사용하지 않았을 때 말도 안되는 깊이의 재귀로 인한 메소드 오버헤드 공간이 더 잡아먹기도 할 것이다.

이렇게도 해결되지 않는 문제가 있다. 어쩔 수 없이 n이 엄청나게 커질때 발생하는 Stack overflow인데, 이건 실행 옵션과 타협보도록 하자. 각 언어별로 함수 또는 메소드를 호출하는데 자체에 비용이 발생하기 때문에 답이 없..

지않다. 반복을 써서 구현해보도록 하자.

반복을 이용해서 구현하면 맨 처음 멍청한 방법으로 구현이 훨씬 어렵다.

unsigned long long loop(unsigned long long n) {
    if (n == 1 || n == 2) return n - 1;

    unsigned long long result = 0;
    unsigned long long before = 0;
    unsigned long long temp = 0;

    for (unsigned long long i = 0; i < n; i++) {
        temp = result;
        result += before;
        before = temp;
    }
}

이 얼마나 간단한 방법인가. 설명할 필요도 없는 쉬운 방법이 되겠다. 임시 변수에 현재까지 결과를 넣어두고 현재까지 결과에 이전 항을 더하고 이전 항을 방금의 결과로 바꾼다. 시간복잡도는 여전히 O(n)이고 공간복잡도는 O(1)이 된다! 기적같은 결과일 뿐이다. 게다가 함수를 불러내는 방식도 아니므로 Stack의 한계로부터도 자유롭다.

이런 방법도 편하지만 반복만으로 모두 해결될 턱도 없다. 이번엔 수의 분할을 해보자.

분할 알고리즘은 어떤 자연수의 분할 경우의 수를 구하는 것인데, 예를 들어 5는

5

4 + 1

3 + 2

3 + 1 + 1

2 + 2 + 1

2 + 1 + 1 + 1

1 + 1 + 1 + 1 + 1

이렇게 자기 자신과 1로만 이루어진 합까지 모두 나타내어 경우의 수가 총 일곱가지가 된다.

typedef unsigned long long ull;

ull stupid(ull n) {
    ull result = 0;

    for (ull k = 1; k <= n; k++)
        result += stupid(n, k);

    return result;
}

ull stupid(ull n, ull k) {
    return (n == k || k == 1) ? 1 : (k > n || k < 1) ? 0 : stupid(n - 1, k - 1) + stupid(n - k, k);
}

unsigned long long을 일일히 치기 너무 귀찮았던 탓에 ull이라는 성의없는 이름으로 붙였다. 

해결에 필요한 알고리즘은 상당히 간단하다.

분할하고자하는 n과 1씩 커지는 n이하의 자연수 k의 분할의 합이 바로 P(n, k)다.

말로는 이해가 가지 않는 프로그래머들을 위한 식으로는

P(n, k) = P(n - 1, k - 1) + P(n - k, k) 이고

P(n, k) = P(n - k, 1) + P(n - k, 2) + P(n - k, 3) + ... + P(n - k, k) 이다.

위의 멍청한 방법은 10의 분할 수를 구할 때 중복되는 연산이 꽤 많다는 것을 알 수 있다.

방금과 같은 방법으로 중복된 연산 결과를 어딘가에 저장해보자.

#include <iostream>
#include <cstring>

typedef unsigned long long ull;
class Partition {
public:
    Partition(ull n) {
        this->n = n;

        data = new ull*[n];
        for (ull i = 0; i < n; i++) {
            *(data + i) = new ull[n];
            std::memset(*(data + i), 0, sizeof(ull) * i);
        }
    }

    ~Partition() {
        if (data != nullptr) {
            for (int i = 0; i < n; i++) {
                delete[] *(data + i);
                *(data + i) = nullptr;
            }

            delete[] data;
            data = nullptr;
        }
    }

    ull great(ull n) {
        ull result = 0;

        for (int k = 1; k <= n; k++) {
            result += great(n, k);
        }

        return result;
    }

private:
    ull **data;
    ull n;

    ull great(ull n, ull, k) {
        if (n == k || k == 1) return 1;
        if (k > n || k < 1) return 0;
        if (*(*(data + n - 1) + k - 1) == 0) {
            *(*(data + n - 1) + k - 1) = great(n - 1, k - 1) + great(n - k, k);
        }

        return *(*(data + n - 1) + k - 1);
    }
};

역시 헤더에 몽땅 넣었지만 참고하는 사람들은 눈치껏 cpp에 작성하길 바란다.

앞선 피보나치 수열과 마찬가지로 지수적으로 커지던 연산은 이제 메모리가 허락하는 한 돌려볼만 한 선형의 시간을 갖게 된다.

물론 그에 따른 공간복잡도는 O(n^2)이 되는데, 배열을 삼각형 꼴로 만들어 절반으로 줄이는 방법도 있지만 계수가 점근 표기법에 영향을 주진 않으므로, 다차 형태의 공간복잡도는 유지된다.

실제로 100의 분할수만 구하더라도 단순한 재귀적 방법은 9.7초정도 걸린데 비해 동적 프로그래밍 기법이 사용된 방법은 약 2ms정도에 구한다. 이정도면 지수적인 수준을 벗어난 듯 할 정도이다.

프로그래밍에서 정말 이런 단순한 경우의 동적 프로그래밍을 할 경우가 많지는 않다. 하지만 어쩌면 당연한 같은 연산 피하기, 이전 결과 기억하기라는 방법을 통해 비약적인 성능 향상을 꾀할 수 있다는 것은 항상 명심해야 한다.