[Algorithm][Dynamic Programming]동적계획법(다이나믹 프로그래밍)과 메모이제이션(memoization), 타뷸레이션(tabulation)

여러분이 프로그램에게 일을 시키는 이유는 무엇일까?

정말 간단한데 "많은 작업을 시키거나 적은 작업을 여러번 반복하기"위해서이다.

결국에는 많이 시킨다는 것이다.

사람입장에서 덧셈을 만번시키면 아주 죽으려고 하겠지만 컴퓨터 입장에서는 만번이야 가볍게 할 것이다.

문제는 그러다 보니 컴퓨터에게 더 많은 일을 시키고 결국 컴퓨터 역시 한계에 부딪히게 된다.

이러한 문제는 여러방면에서 흔히 발생하는데 그 중에서는 아래 같이 문제가 발생한다.

#include <stdio.h>

#define ll long long

ll count;

ll fib(int n) {
    count++;
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 1;
    }

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

int main() {
    for (int n = 1; n <= 50; n++) {
        count = 0;
        printf("%lld: %lld: %lld\n", n, fib(n), count);
    }
    return 0;
}

피보나치 수열을 구하는 문제이다.

뭐 코드는 간단하니 설명할 것은 없다. 1항부터 50항까지 출력한다.

정말 간단해 보이고 컴퓨터는 얼마 안걸려서 재빨리 끝날거 같지만 실제로는 꽤 시간이 걸린다.

한번 실행해보면 고작 50항까지인대도 시간이 많이 걸리는걸 확인할 수 있다.

1: 1: 1
2: 1: 1
3: 2: 3
4: 3: 5
5: 5: 9
6: 8: 15
7: 13: 25
8: 21: 41
9: 34: 67
10: 55: 109
11: 89: 177
12: 144: 287
13: 233: 465
14: 377: 753
15: 610: 1219
16: 987: 1973
17: 1597: 3193
18: 2584: 5167
19: 4181: 8361
20: 6765: 13529
21: 10946: 21891
22: 17711: 35421
23: 28657: 57313
24: 46368: 92735
25: 75025: 150049
26: 121393: 242785
27: 196418: 392835
28: 317811: 635621
29: 514229: 1028457
30: 832040: 1664079
31: 1346269: 2692537
32: 2178309: 4356617
33: 3524578: 7049155
34: 5702887: 11405773
35: 9227465: 18454929
36: 14930352: 29860703
37: 24157817: 48315633
38: 39088169: 78176337
39: 63245986: 126491971
40: 102334155: 204668309
41: 165580141: 331160281
42: 267914296: 535828591
43: 433494437: 866988873
44: 701408733: 1402817465
45: 1134903170: 2269806339
46: 1836311903: 3672623805
47: 2971215073: 5942430145
48: 4807526976: 9615053951
49: 7778742049: 15557484097
50: 12586269025: 25172538049

n번째: 피보나치 값: 연산횟수

보면 알겠지만 연산횟수가 50항에서 250억번 연산을 시행한걸 알 수 있다.

시간복잡도는 매 노드가 2가지 분기를 만들기 때문에 O(2^n)가 됨을 알 수 있다.

컴퓨터니까 중세시대 농노마냥 일을 빡새게 시켰지만 농노도 근성에 한계가 있듯이 컴퓨터도 저 정도일이면 엄청 느리게 처리한다.

이런 문제는 비일비재한데 이를 해결하기위해서 아주 획기적인 방법을 도입했다.

모든 문제에만 적용되는게 아니라 이러한 문제에만 적용될수있다.

코드를 한번 보자.

fib(5)
    ->fib(4)
        ->fib(3)
            ->fib(2)
            ->fib(1)
        ->fib(2)
    ->fib(3)
        ->fib(2)
        ->fib(1)

피보나치 5항을 구하는데 무려 9번의 연산이 필요하다.

하지만 잘보면 여러분이 알 수 있는게 중복되서 연산이 이루어 진다는 것이다.

1을 구하는 연산은 총 2번, 2를 구하는 연산은 3번, 3을 구하는 연산은 2번... 이런식으로 연산이 늘어남을 볼 수 있다.

만약 그럼 연산이 구해졌을 때 그걸 저장하고 그 저장된 값을 비교한다면 어떻게 될까?

fib(5)
    ->fib(4) => "연산후 저장"
        ->fib(3) => "연산 후 저장"
            ->fib(2) => "연산 후 저장"
            ->fib(1) => "연산 후 저장"
        ->fib(2) => /* 저장된 값 사용 */
    ->fib(3) /* 저장된 값 사용*/

만약 그런 논리로 사용하게 된다면 실제로 연산횟수는 드라마틱 하게 줄어든다.

fib2와 fib3은 값을 이미 구한 상태이므로 재 호출을 할 경우 추후의 연산을 사용하지 않는다.

위를 보면 재귀가 9번에서 7번으로 준걸 확인할 수 있다.

이렇게 보면 적게 준거 같은데 아래 코드들을 확인해보자.

int main() {
    memset(memo, -1, sizeof(ll) * MAXSIZE);
    for (int n = 1; n <= 50; n++) {
        count = 0;
        printf("%lld: %lld: %lld\n", n, fib(n), count);
    }
    return 0;
}

코드를 보면 크게 추가된 로직이 없다.

작게 작게 뭔가 추가 됬는데 이를 잘 보면 뭔가 처리를 했음을 알 수 있다.

memset(memo, -1, sizeof(int) * MAXSIZE);

이 로직은 배열의 초기화이다. 보통 전역으로 선언하면 0으로 자동초기화되는데 이를 1로 초기화 하는 것이다.

보통의 경우 -1로 초기화하는 경우가 많다. 그런 습관을 드는 것이 좋은데 그 이유는 0으로 두면 추가적인 연산을 하는 경우가 있기 때문이다.

양수와 0만 사용한다면 초기화를 -1로 해주는게 좋고 음수까지 사용하는 코드라면 엄청 큰 값을 선언해주는게 좋다.

보통 배열 인덱스니까 음수까지 안갈거라고 생각하는 사람도 있지만 음수 인덱스가 필요한 경우도 분명 존재한다.

ll memo[MAXSIZE];

ll fib(int n) {
    count++;
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 1;
    }

    if (memo[n] == -1) {
        memo[n] = fib(n - 2) + fib(n - 1);
    }

    return memo[n];
}

배열을 선언하고 그 배열을 확인하는 로직이 추가됬다.

보면 현재 인덱스의 배열을 확인하고 그 배열의 값이 -1이면 아직 초기화 안된것이므로 값을 계산한다는 로직이다.

로직 자체는 아주 작은 몇줄 추가됬을 뿐이지만 성능은 아주 드라마틱하게 상승한다.

1: 1: 1
2: 1: 1
3: 2: 3
4: 3: 3
5: 5: 3
6: 8: 3
7: 13: 3
8: 21: 3
9: 34: 3
10: 55: 3
11: 89: 3
12: 144: 3
13: 233: 3
14: 377: 3
15: 610: 3
16: 987: 3
17: 1597: 3
18: 2584: 3
19: 4181: 3
20: 6765: 3
21: 10946: 3
22: 17711: 3
23: 28657: 3
24: 46368: 3
25: 75025: 3
26: 121393: 3
27: 196418: 3
28: 317811: 3
29: 514229: 3
30: 832040: 3
31: 1346269: 3
32: 2178309: 3
33: 3524578: 3
34: 5702887: 3
35: 9227465: 3
36: 14930352: 3
37: 24157817: 3
38: 39088169: 3
39: 63245986: 3
40: 102334155: 3
41: 165580141: 3
42: 267914296: 3
43: 433494437: 3
44: 701408733: 3
45: 1134903170: 3
46: 1836311903: 3
47: 2971215073: 3
48: 4807526976: 3
49: 7778742049: 3
50: 12586269025: 3

마술이 정말 따로없다고 할 수 있다.

250억번에 걸려서 했던 연산이 고작 3회?

사실 이는 앞에서 연산해서 그렇고 50만 따로 구해보자.

int main() {
    memset(memo, -1, sizeof(ll) * MAXSIZE);
    for (int n = 50; n <= 50; n++) {
        count = 0;
        printf("%lld: %lld: %lld\n", n, fib(n), count);
    }
    return 0;
}

이렇게 코드를 수정하고 돌려보자.

50: 12586269025: 97

250억 => 97번으로 드라마틱이라는 말로는 모자랄 정도로 줄었다.

중복연산을 제거했기 때문에 일어난 일이다.

원리는 위에서 설명했듯이 한번 연산이 되면 나중에는 재연산을 하지 않고 저장된 값을 쓰기 때문이다.

여기서 시간복잡도는 당연히 한번 연산했던 애는 연산으로 구하지 않으므로 O(n)이 된다.

#include <stdio.h>
#include <memory.h>

#define MAXSIZE 101
#define ll long long

ll count;
ll memo[MAXSIZE];

ll fib(int n) {
    count++;
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 1;
    }

    if (memo[n - 2] == -1) {
        memo[n - 2] = fib(n - 2);
    }

    if (memo[n - 1] == -1) {
        memo[n - 1] = fib(n - 1);
    }

    return memo[n - 2] + memo[n - 1];
}

int main() {
    memset(memo, -1, sizeof(ll) * MAXSIZE);
    for (int n = 1; n <= 50; n++) {
        count = 0;
        if (memo[n] == -1) {
            memo[n] = fib(n);
        }
        printf("%lld: %lld: %lld\n", n, memo[n], count);
    }
    return 0;
}

연산량을 조금이라도 더 줄이고 싶다면 위의 방법도 있다.

첫번째 방식이 재귀가 도는 자신을 기준으로 판단한다면 두번째 방식은 재귀가 돌기전 상위에서 판단하는 방식이다.

보통의 경우 연산량이 1/2정도 주는 효과가 있으나 크리티컬하진 않다.

두가지다 취향차이이고 전자가 코드가 더 깔끔해서 선호하는 방식이긴 하다.

여태까지 했던 알고리즘 중에서 가장 마법같은 알고리즘이다.

이렇게 "저장했던 값을 재활용해서 사용하는"알고리즘을 동적계획법, 혹은 다이나믹프로그래밍이라한다.

그리고 우리가 사용했던 "계산이 필요한 순간 계산해서 저장"하는 방식을 메모이제이션이라고 한다.

반대로 미리 다 구해놓는 방식을 타뷸레이션이라고 한다.

가량 여러분이 50번째 항의 값을 알고싶다고 가정하자.

그러면 아래 같이 코드를 짤것이다.

#include <stdio.h>
#include <memory.h>

#define MAXSIZE 101
#define ll long long

ll count;
ll memo[MAXSIZE];

ll fib(int n) {
    count++;
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 1;
    }

    if (memo[n] == -1) {
        memo[n] = fib(n - 2) + fib(n - 1);
    }

    return memo[n];
}

int main() {
    memset(memo, -1, sizeof(ll) * MAXSIZE);
    count = 0;
    int n = 50;
    printf("%lld: %lld: %lld\n", n, fib(n), count);
    return 0;
}

이렇게 코드를 짤수도 물론 있지만 미리 다 구해 놓는 방식역시 사용할 수 있다.

#include <stdio.h>
#include <memory.h>

#define MAXSIZE 101
#define ll long long

ll tab[MAXSIZE];


int main() {
    tab[1] = 1;
    tab[2] = 1;
    for (int n = 3; n < MAXSIZE; n++) {
        tab[n] = tab[n - 1] + tab[n - 2];
    }
    int n = 50;
    printf("%lld: %lld\n", n, tab[n]);
    return 0;
}

재귀를 사용하지 않고 for문을 사용해서 미리 값을 다 구한후 해당 값을 찾았다.

이렇게 "미리 다 구해놓는 방식"을 타뷸레이션이라고한다.

for문을 사용하기에 재귀보다 연산에서 유리하다. 만약 어쩔수 없이 전사대입을 해야한다면 무조건적으로 타뷸레이션이 이득을 본다.

단 위의 예제에서 보면 알겠지만 우리는 50항까지 구하지만 실제로는 100항까지 전부 구하였다.

이런식으로 필요 없는 값까지 미리 계산하게 된다. 만약 그값을 쓰지 않는다면 고스란히 오버헤드로 남게 된다.

또한 사용자는 한번에 몰빵해서 연산을 하는것보다 간헐적으로 연산이 좀더 걸리는데 성능저하를 느끼지 못한다(단 간헐적이 시간이 느릴경우만해당)

따라서 타뷸레이션보다 메모이제이션이 사용자가 느끼기에는 덜 부담이 될 수 있다.

이 역시 취향차이 이며 실제로 백준문제에서는 메모이제이션으로 풀리는 문제는 타뷸레이션으로 풀리고 역도 성립한다.

그러나 대부분의 상황에서는 타뷸레이션이 훨씬 빠르긴하다.