동적 계획법 ① — 피보나치로 배우는 재귀·메모이제이션·DP

같은 문제를 세 번 푼다. 정의 그대로의 재귀, 계산값을 적어 두는 메모이제이션, 채우는 순서까지 정해 상향식으로 올리는 동적 계획법. 피보나치 하나로 이 세 가지의 차이와, 어떤 문제가 애초에 이렇게 풀리는지를 본다.

이 포스트에서 다루는 내용

재귀는 알고리즘이 아니라 방법이다 — 분할 정복과 DP가 언제 재귀를 쓰는가
어떤 문제가 이렇게 풀리는가: 부분 문제의 독립성
정의 그대로의 재귀가 왜 느린가 — 지수 범위 $2^{n/2} \le F(n) < 2^n$ 증명
메모이제이션: 계산값을 적어 두어 $O(N)$ 으로
동적 계획법: 채우는 순서를 알면 재귀 없이 상향식으로

피보나치와 재귀

피보나치 수열은 정의부터 재귀식이다.

F(0) = 0,\quad F(1) = 1,\quad F(n) = F(n-1) + F(n-2)\ (n \ge 2)

정의가 곧 재귀식이므로 그대로 코드로 옮기면 답이 나온다.

long long fib(int n) {
    if (n < 2) return n;              // F(0)=0, F(1)=1
    return fib(n - 1) + fib(n - 2);
}

여기서 짚을 점이 하나 있다. 재귀는 그 자체로 알고리즘이 아니라 하나의 방법이다. 재귀를 대표적으로 쓰는 두 곳이 분할 정복과 동적 계획법(dynamic programming, DP)이다. 둘 다 큰 문제를 작은 문제로 미루지만, 재귀가 성립하는 조건이 있다.

부분 문제를 무엇으로 잡느냐

재귀로 풀린다는 말은 부분 문제를 잘 잡았다는 뜻이다. 잘 잡았다는 것은 두 가지다.

상태가 충분하다. 부분 문제의 답이 그 부분 문제만 보고 정해져야 한다. 답을 정하는 데 필요한 정보가 상태에 다 들어 있어야 한다는 뜻이다.
최적 부분 구조. 전체의 최적해가 부분 문제의 최적해로 조립된다.

merge sort가 그렇다. 「이 구간을 정렬하라」는 구간만 보면 답이 정해지고, 두 절반의 정렬 결과를 합치면 전체가 정렬된다.

반대 예로 그래프의 최단 거리를 정점 집합을 반으로 갈라 푼다고 하자. 「왼쪽 그래프의 최단 거리」는 답이 정해지지 않는다. 오른쪽을 거쳐 돌아오는 경로가 더 짧을 수 있기 때문이다. 상태가 모자란다. 다만 이것은 이 쪼개는 방식이 나쁘다는 말이지 최단 거리를 DP로 풀 수 없다는 말이 아니다. 상태를 「몇 개 이하의 간선을 쓰는 최단 거리」나 「중간 정점을 어디까지 허용한 최단 거리」로 잡으면 그대로 DP가 되고, 벨만·포드와 플로이드·워셜이 각각 그 예다.

DP가 성립하는 조건

DP는 여기에 하나를 더한다. 부분 문제가 겹쳐야 한다.

분할 정복은 쪼갠 부분 문제가 서로 다른 것을 다루므로 한 번씩만 풀면 된다. DP가 겨냥하는 것은 반대 상황이다. 같은 부분 문제가 여기저기서 되풀이해 나오는 경우인데, 이때 답을 적어 두면 다시 풀지 않아도 된다. 겹침은 DP의 걸림돌이 아니라 DP를 쓰는 이유다.

그래서 필요한 성질은 「독립」이 아니라 「값으로 존재」다. 어떤 부분 문제의 답이 그 자체로 하나의 값으로 존재해야 하고, “이 값이 나중에 어디에 쓰일지”를 몰라도 계산할 수 있어야 한다. 피보나치의 $F(5)$ 는 $F(5)$ 라는 값으로 존재하는 동시에 $F(6)$ , $F(7)$ 을 만드는 재료로도 쓰인다. $F(5)$ 를 구할 때 그 쓰임새를 알 필요는 없다. 값은 그냥 값이다.

재귀는 왜 느린가

위 코드는 답을 내지만 느리다. 같은 부분 문제를 몇 번이고 다시 풀기 때문이다. $F(5)$ 를 펼쳐 보자.

F(5) = F(4) + F(3) = \big(F(3) + F(2)\big) + F(3) = \cdots

F(5)의 재귀 트리. F(3)은 두 번, F(2)는 세 번 계산된다. n이 커지면 이 중복이 지수로 불어난다.

트리에서 $F(3)$ 은 두 번, $F(2)$ 는 세 번 나타난다. 잎에 도달하면 $F(1)=1$ 이나 $F(0)=0$ 을 돌려주고, 전체 값 $F(n)$ 은 $1$ 을 돌려주는 잎의 개수와 같다. 그 잎의 개수가 곧 $F(n)$ 이므로, 호출 수는 $\Theta(F(n))$ 이다. 그렇다면 $F(n)$ 자체가 얼마나 빨리 커지는지 재면 된다.

정리 1피보나치는 지수로 커진다

$n \ge 2$ 에서 다음이 성립한다.

2^{\,n/2 - 1} \;\le\; F(n) \;<\; 2^{\,n}

따라서 정의 그대로의 재귀는 호출 수가 $\Theta(F(n))$ , 즉 지수 시간이다.

증명. 피보나치는 $n \ge 1$ 에서 커지기만 한다( $F(n) \ge F(n-1)$ ).

상한: 작은 항을 큰 항으로 바꿔 키우면

F(n) = F(n-1) + F(n-2) \le F(n-1) + F(n-1) = 2\,F(n-1).

이를 반복하면 $F(n) \le 2^{n-1} F(1) = 2^{n-1} < 2^n$ 이다.

하한: 큰 항을 작은 항으로 바꿔 줄이면

F(n) = F(n-1) + F(n-2) \ge F(n-2) + F(n-2) = 2\,F(n-2).

두 칸씩 내려가며 반복하면 $F(1)=F(2)=1$ 에 닿아 $F(n) \ge 2^{\,n/2 - 1}$ 이다. 두 부등식을 합치면 $2^{\,n/2-1} \le F(n) < 2^n$ . 밑이 $\sqrt{2}$ 와 $2$ 사이인 지수 증가다. ∎

지수 시간의 뿌리는 분명하다. 이미 푼 부분 문제를 기억하지 못해 매번 다시 푸는 것이다.

메모이제이션

한 번 계산한 값을 어딘가에 적어 두면, 다음에는 다시 풀지 않고 꺼내 쓰면 된다. 같은 호출을 한 번만 하겠다는 발상이다.

long long memo[MAX];                 // 모두 -1로 초기화: 아직 계산 안 함

long long fib(int n) {
    if (n < 2) return n;
    if (memo[n] != -1) return memo[n];   // 적어 둔 값이 있으면 꺼내 쓴다
    return memo[n] = fib(n - 1) + fib(n - 2);
}

값을 배열에 기록하는 일은 값마다 한 번이다. 그 값을 꺼내 쓰는 일은 여러 번 일어난다. 의존 관계를 보면 왜 전체가 선형인지 드러난다. $F(3)$ 은 $F(4)$ 와 $F(5)$ 를 계산할 때 읽힌다. $F(5)$ 가 이후에 몇 번 더 쓰이든, $F(3)$ 은 $F(5)$ 를 처음 계산하는 순간에만 관여한다. 각 값은 한 번 계산되고 이후에는 상수 번 읽힐 뿐이다.

메모이제이션의 의존 그래프. F(i)는 F(i-1), F(i-2)에만 기댄다. 각 값이 한 번만 계산되어 재귀 트리가 사슬로 접힌다.

그림은 의존 관계를 보여 준다. 화살표가 가리키는 값이 먼저 있어야 그 값을 계산할 수 있다는 뜻이다. 메모이제이션은 이 그래프를 필요할 때 거슬러 올라가며 채운다. $F(5)$ 를 물으면 $F(4)$ 와 $F(3)$ 을 묻고, 그렇게 바닥까지 내려갔다가 돌아오면서 적는다. 다음 절의 상향식은 같은 그래프를 왼쪽부터 차례로 채운다. 채우는 순서만 다르고 의존 관계는 같다.

계산이 값마다 한 번이므로 전체는 $O(N)$ 이다. 지수에서 선형으로 내려왔다.

동적 계획법

메모이제이션은 여전히 재귀다. 배열이 어떤 순서로 채워질지 몰라도 동작한다는 장점이 있다. 필요한 값을 만나면, 계산돼 있으면 꺼내 쓰고 아니면 그 자리에서 재귀로 채운다.

채워지는 순서까지 미리 알 수 있다면 재귀를 걷어낼 수 있다. $F(i)$ 는 $F(i-1)$ 과 $F(i-2)$ 에만 기댄다. 작은 인덱스부터 채우면 $F(i)$ 차례에는 두 값이 이미 준비돼 있다. 이렇게 작은 문제부터 상향식으로 표를 채우는 방법이 동적 계획법이다.

long long fib(int n) {
    long long dp[MAX];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];   // 왼쪽 두 칸은 이미 채워져 있다
    return dp[n];
}

재귀 호출이 사라지고, 배열에 있는 값을 가져다 쓴다. $dp[i]$ 의 입장에서 $dp[i-1]$ , $dp[i-2]$ 는 이미 계산돼 있다고 믿어도 된다. 채우는 순서가 그것을 보장하기 때문이다.

메모이제이션 vs 동적 계획법

둘 다 부분 문제를 한 번씩만 풀어 $O(N)$ 이다. 큰 복잡도의 차이는 없다. 메모이제이션은 하향식(top-down) 재귀라 순서를 몰라도 되는 대신 재귀 호출 비용이 붙는다. 동적 계획법은 상향식(bottom-up)이라 순서를 스스로 정해야 하지만 재귀가 없어 조금 더 빠르고 가볍다. 채우는 순서를 명확히 아는 문제라면 DP가 자연스럽다.

마치며

피보나치 하나로 세 방법을 지나왔다. 정의 그대로의 재귀는 같은 부분 문제를 지수 번 다시 푼다. 메모이제이션은 계산값을 적어 두어 이 중복을 없애 $O(N)$ 으로 내린다. 동적 계획법은 채우는 순서까지 정해 재귀마저 걷어낸다. 셋을 가르는 것은 부분 문제의 답이 값으로 존재하는가였다. 부분의 답이 그 자체로 존재하기에, 한 번 풀어 적어 두고 되쓸 수 있다.

다음 편에서는 이 틀을 피보나치보다 복잡한 문제에 적용해, 상태와 점화식을 어떻게 세우는지 본다.