🐹 11. Recursion & Dynamic programming

08. 재귀와 동적 프로그래밍

재귀와 관련된 문제들은 상당수는 패턴이 비슷하다. 주어진 문제가 재귀 문제인지 확인해 보는 방법은, 해당 문제를 작은 크기의 문제로 만들 수 있는지 보는 것이다.

다음과 같은 문장으로 시작하는 문제는 재귀로 풀기 적당한 문제일 가능성이 높다.(항상 그런것은 아니다.)

• “n번째 …를 계산하는 알고리즘을 설계하라”
• “첫 n개를 나열하는 코드를 작성하라”
• “모든 …를 계산하는 메서드를 구현하라”

[ 접근법 ]

재귀적 해법은 부분문제(subproblem)에 대한 해법을 통해 완성된다.

따라서 많은 경우, 단순히 f(n-1)에 대한 해답에 무언가를 더하거나, 제거하거나, 아니면 그 해답을 변경하여 f(n)을 계산해낸다. 아니면, 데이터를 반으로 나눠 각각에 대해서 문제를 푼 뒤 이 둘을 병합(merge)하기도 한다.

주어진 문제를 부분문제로 나누는 방법도 여러 가지 있다. 가장 흔하게 사용되는 세 가지 방법으로는

• 상향식(bottom-up)
• 하향식(top-down)
• 반반(half-and-half)

이 있다.

상향식 접근법

상향식 접근법(bottom-up approach)는 가장 직관적인 경우가 많다. 이 접근법은 우선 간단한 경우들에 대한 풀이법을 발견하는 것으로부터 시작한다.

ex) 리스트

처음에는 원소 하나를 갖는 리스트로부터 시작한다. 다음에는 원소 두 개가 들어 있는 리스트에 대한 풀이법을 찾고, 그 다음에는 세 개 원소를 갖는 리스트에 대한 풀이법을 찾는다. 이런 식으로 계속해 나간다.

이 접근법의 핵심은, 이전에 풀었던 사례를 확장하여 다음 풀이를 찾는다는 점이다.

하향식 접근법

하향식 접근법(top-down approach)는 덜 명확해서 복잡해 보일 수 있다. 하지만 가끔은 이 방법이 문제애 대해 생각해 보기에 가장 좋은 방법이기도 하다.

이러한 문제들은 어떻게 하면 N에 대한 문제를 부분 문제로 나눌 수 있을지 생각해 봐야 한다. 나뉜 부분문제의 경우가 서로 겹치지 않도록 주의한다.

반반 접근법

데이터를 절반으로 나누는 방법도 종종 유용하다.

ex) 이진 탐색

정렬된 배열에서 특정 원소를 찾을 때, 가장 먼저 왼쪽 절반과 오른쪽 절반 중 어디를 봐야 하는지 확인한다. 이와 같은 방식으로 절반씩 재귀적으로 탐색해 나간다.

ex) 병합 정렬

배열 절반을 각각 정렬한 뒤 이들을 하나로 병합한다.

[ 재귀적 해법 vs 순환적 해법 ]

• 재귀적 알고리즘

  → 공간 효율성이 나빠질 수 있다.

  재귀 호출이 한 번 발생할 때마다 스택에 새로운 층(layer)을 추가해야 한다. 이는 재귀의 깊이가 n일 때 O(n) 만큼의 메모리를 사용하게 된다는 것을 의미한다.

이런 이유로, 재귀적(recursive) 알고리즘은 순환적(iterative)으로 구현하는 것이 더 나을 수 있다. 모든 재귀적 알고리즘은 순환적으로 구현될 수 있지만, 순환적으로 구현된 코드는 때로 훨씬 더 복잡하다.

[ 동적계획법 & 메모이제이션 ]

동적 프로그래밍은 거의 대부분 재귀적 알고리즘과 반복적으로 호출되는 부분문제를 찾아내는 것이 관건이다. 이를 찾은 뒤에는 나중을 위해 현재 결과를 캐시에 저장해 놓으면 된다.

혹은 재귀 호출의 패턴을 순환적 형태로 구현할 수도 있다. 물론 여전히 결과를 ‘캐시’에 저장해야 한다.

• 메모이제이션(memoization) : 하향식 동적 프로그래밍
• 동적 프로그래밍 : 상향식 접근법

동적 프로그래밍의 가장 간단한 예시는 n번째 피보나치 수(Fibonacci number)를 찾는 것이다. 이런 문제를 풀 때는 일반적인 재귀로 구현한 뒤 캐시 부분을 나중에 추가하는 것이 좋다.

피보나치 수열

피보나치 수를 찾는 방법

방법 #1: 재귀

int fibonacci(int i) {
    if (i == 0) return 0;
    if (i == 1) return 1;
    return fibonacci(i - 1) + fibonacci(i - 2);
}

이 함수의 수행 시간을 고려할 때 뿐만 아니라 다른 재귀 문제를 풀 때 호출되는 경로를 트리로 그려보면 도움이 된다.

트리의 말단 노드는 모두 기본 경우(base case)인 fib(1) 아니면 fib(0)인 것을 알 수 있다. 각 호출에 소요되는 시간이 O(1) 이므로 트리의 전체 노드의 개수와 수행 시간은 같다. 따라서 총 호출 횟수가 수행 시간이 된다.

기본 경우(말단 노드)에 도달하기 전까지의 각 노드는 두 개의 자식 노드를 갖고 있다. 이 자식 노드 또한 두 개의 자식 노드를 갖고 있고(즉, 네 개의 손자 노드가 있는 셈이다), 이 손자 노드들도 각각 두 개의 자식 노드를 갖고 있다.

이를 n번 반복하면 대략 $O(2^n)$개의 노드를 갖게 된다. 따라서 수행 시간은 대충 $O(2^n)$이 된다.

실제론 $O(2^n)$보다 빠르다. 위 그림을 보면 (말단 노드와 말단 노드 바로 위는 제외하고) 오른쪽 부분트리의 크기가 왼쪽 부분트리의 크기보다 항상 작다는 사실을 알 수 있다. 만약 이 둘의 크기가 같다면 수행 시간은 $O(2^n)$이 될 것이다.

하지만 양쪽의 크기가 같지 않으므로, 실제 수행 시간은 $O(1.6^n)$에 가깝다. big-O 표기법은 수행 시간의 상한을 의미하는 것이므로 $O(2^n)$도 기술적으로 옳은 표현법이긴 하다. 어쨌든 여전히 수행 시간은 지수 시간이다.

(지수 시간은 수행 시간이 기하급수적으로 증가한다.)

최적화 방법을 찾아야 한다.

방법 #2: 하향식 동적 프로그래밍(메모이제이션)

재귀 트리에서 많은 노드들이 중복되어 호출된다. 이들이 호출될 때마다 다시 계산할 필요가 없다.

사실, 우리가 fib(n)을 호출했을 때, fib이 탐색할 경우의 수가 O(n)이므로 fib 함수를 O(n)번 이상 호출하면 안된다. 매번 fib(i)를 계산할 때마다 이 결과를 캐시에 저장하고 나중에는 저장된 값을 사용하는 것이 좋다. 바로 이게 메모이제이션(memoization)이다.

이전의 코드를 약간 고쳐 O(N) 시간에 돌아가게끔 만든다. 재귀 호출 사이에 fibonacci(i)의 결과를 캐시에 저장하는 부분만 추가한다.

int fibonacci(int n) {
    return fibonacci(n, new int[n + 1]);
}

int fibonacci(int i, int[] memo) {
    if (i == 0 || i == 1) return i;
    if (memo[i] == 0) {
        memo[i] = fibonacci(i - 1, memo) + fibonacci(i - 2, memo);
    }
    return memo[i];
}

일반적인 컴퓨터에서 이전의 재귀 함수 코드를 돌려보면 50번째 피보나치 수를 찾는 데 1분 이상 걸린다. 하지만 동적 프로그래밍을 사용하면 10,000번째 피보나치 수열을 찾는 데 밀리초(millisecond)도 걸리지 않는다(물론 위의 코드를 그대로 사용하면 10,000번이 되기도 전에 int 자료형 때문에 오버플로우가 발생할 것이다)

재귀 트리를 그려보면 다음과 같다.(사각형으로 표시된 부분은 캐시값을 그대로 반환한 경우를 나타낸다)

이 트리에서 각 노드의 자식 노드는 한 개이므로, 모든 노드의 개수는 대략 2n개가 된다. 따라서 수행 시간은 O(n)이다.

방법 #3: 상향식 동적 프로그래밍

재귀적인 메모이제이션으로 접근하되 그것을 뒤집는다고 생각해보자.

먼저, 초기 사례(base case)인 fib(1)과 fib(0)을 계산한다. 그 뒤, 이 둘을 이용해 fib(2)를 계산하고, 차례로 fib(3), fib(4) 등을 이전의 결과를 이용해 계산한다.

int fibonacci(int n) {
    if (n == 0) return 0;
    else if (n == 1) return 1;
    int[] memo = new int[n];
    memo[0] = 0;
    memo[1] = 1;
    for (int i = 2; i < n; i++) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    return memo[n - 1] + memo[n - 2];
}

memo[i]는 memo[i+1]과 memo[i+2]를 계산할 때만 사용될 뿐, 그 뒤에는 전혀 사용되지 않는다. 따라서 memo 테이블 말고 변수 몇 개를 사용해서 풀 수도 있다.

int fibonacci(int n) {
    if (n == 0) return 0;
    int a = 0;
    int b = 1;
    for (int i = 2; i < n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return a + b;
}

위 코드는 단순히 피보나치 수열의 마지막 숫자 두 개를 a와 b 변수에 저장하도록 바꾼 결과다. 루프의 각 단계에서는 다음 값 (c = a + b)을 계산한 뒤 (b, c = a + b)의 값을 (a, b)로 옮기는 일을 수행했다.