다이나믹 프로그래밍

프로그래밍은 대개 현실 세계의 문제를 전산적으로 접근하여 풀기 위하여 사용됩니다.

그 중 어떤 문제들은, 컴퓨터를 사용해도 매우 오래 걸리거나 해결하기 어렵기도 합니다.

컴퓨터 역시 현실 세계의 물건인 만큼, 저장 공간이나 연산 속도에 한계가 존재하며, 이러한 한계가 걸림돌이 되는 경우가 분명히 존재합니다.

만약 어떤 알고리즘이 O(2^N)의 시간 복잡도를 가진다면, N의 크기가 커질수록 처리 속도가 비약적으로 증가할 것입니다. 하지만, 메모리를 조금 더 사용하여 같은 문제를 O(N)의 시간 복잡도로 해결할 수 있다면, 이는 매우 효율적인 방법이 될 수 있습니다.

다이나믹 프로그래밍 (dynamic programming) 은 이렇게 연산 속도를 대폭 줄일 수 있는 대표적인 방법입니다. 다이나믹 프로그래밍에는 탑다운 (top-down) 방식과 보텀업 (bottom-up) 방식이 존재하며, 이 외에 다이나믹 프로그래밍에서 자주 사용하는 기법인 메모이제이션 (memoization) 기법도 있습니다.

개인적으로 제가 좋아하는 이름은 아닌데, dynamic 하지도 않으며 programming 이라는 이름과도 큰 연관이 없습니다. 다이나믹 프로그래밍을 고안한 Richard E. Bellman은 단순히 dynamic 이라는 단어가 멋있어서 그렇게 명명했다고 합니다. 마찬가지로 한글로는 동적 계획법이라고도 하는데, 프로그램 실행 중에 필요한 메모리를 할당하는 기법인 동적 할당법 (dynamic allocation)과는 달리, 동적 프로그래밍은 동적인 것과는 연관이 없습니다.

다이나믹 프로그래밍이 어떻게 활용될 수 있는지 예를 들어 설명해 보겠습니다.

피보나치 수열 (Fibonacci sequence) 에 대해 들어보신 적 있나요?

1, 1, 2, 3, 5, 8, 13, 21, ... 과 같이 이어지는 수열입니다. 잘 보면 첫째, 둘째 항은 1이며, 셋째 항 부터는 이전 항 + 이전 항의 이전 항 이 됩니다.

위 수열을 보면, 2 = 1 + 1, 3 = 2 + 1, 21 = 13 + 8, ... 와 같습니다.

이를 수식으로 옮겨 보면 어떨까요?

위와 같은 점화식을 얻을 수 있습니다.

그렇다면 피보나치 수열의 n번째 항을 얻기 위한 코드는 어떻게 작성하면 좋을까요?

n = 5 일 때를 예로 들어 보겠습니다. 위 점화식에 따르면, a5 = a4 + a3 입니다.

a4는 어디서 얻나요? 마찬가지로 피보나치 수열을 이용하면, a4 = a3 + a2 가 됩니다.

그러면 a3 = a2 + a1 을 또 계산하고, a2 = a1 + a0을 계산하고...

재귀함수 형식으로 구현해보면 좋을 것 같은 모양새이지 않나요?

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

C++로 작성한 재귀함수로 구현한 피보나치 수열입니다.

단순하게 n = 0, 1일 경우 1을 리턴하고, 그 외의 경우 앞에서 적은 점화식을 옮겼습니다.

위처럼 구현하면 무엇이 문제일까요?

아까와 같이 n = 5일 때를 예로 들어 보겠습니다.

앞에서 설명한 바와 같이, a5 = a4 + a3 입니다. a4를 구하려면 a3과 a2를 구해야 하고, a3을 구하려면 a2를 구해야 하고, 우여곡절 끝에 a4를 구한 후에는 우측 a3을 또 구해야 합니다.

a5를 구하기 위해 필요한 연산은 위와 같은 구조를 가지게 됩니다.

a4를 1번 구하고, a3을 2번 구하고, a2를 3번 구합니다. a1, a0는 이미 정의되어 있는 값이므로 별도의 연산을 필요로 하지 않습니다.

즉, 총 연산은 n의 크기가 커질수록 기하급수적으로 늘어나게 됩니다.

피보나치 수열의 시간 복잡도는 세타 표기법을 이용해 θ(1.618...^N) 입니다. big-O 표기법을 이용하면 O(2^N)으로 나타낼 수 있습니다.

즉, n = 30 정도라면 약 10억 번의 연산이 필요한 것입니다.

무엇이 문제일까요?

언급한 것처럼 같은 항에 대한 반복적인 연산이 원인입니다.

그렇다면 이 연산을 "단 한 번만" 수행할 수 있도록 하면 훨씬 효율적으로 문제를 풀 수 있지 않을까요?

이럴 때 다이나믹 프로그래밍을 사용하면 문제를 효율적으로 풀 수 있습니다.

다이나믹 프로그래밍은 다음 조건이 전제되어야 합니다:

큰 문제를 작은 문제로 나눌 수 있다 (divide and conquer).
작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

피보나치 수열에게 딱 맞는 조건이 아닐까요?

소개에서 언급했던 메모이제이션 기법을 이용하여 피보나치 문제를 해결해 보겠습니다.

한 번 구한 결과를 메모리 공간 (배열)에 메모 해두고, 필요할 때 다시 호출하는 것입니다. 값을 저장하고 활용하는 방법이므로 캐싱 (caching) 이라고도 합니다.

long long memo[100] = {0, };    //n의 최댓값이 100이라고 가정

long long fibonacci (int n) {

    memo[0] = 1;
    memo[1] = 1;
    
    if (n == 1 || n == 0) return 1;
    if (memo[n] != 0)
        return memo[n];
    memo[n] = fibonacci(n-1) + fibonacci(n-2);
    return memo[n];
    
}

마찬가지로 재귀적 방식을 이용하여 피보나치 수열을 구현했지만, 이번에는 메모이제이션 기법 또한 함께 사용했습니다.

위 코드에 따르면, 특정 항의 값은 단 한 번만 계산하면 됩니다. 따라서 n = 100일 경우 더하기 연산 역시 100번만 실행되고, 따라서 시간 복잡도는 O(N) 이라고 할 수 있습니다.

그렇다면 재귀적 구조 이외에 다른 방법으로 구현할 수느 없을까요?

시간 복잡도를 논할 때 매우 자주 맞닥뜨리게 되는 반복문으로도 구현할 수 있습니다.

마찬가지로 메모이제이션 기법을 이용하여, 반복문을 통해 피보나치 수열을 구현해 보겠습니다.

long long memo[100] = {0, };    //n의 최댓값이 100이라고 가정

long long fibonacci (int n) {

    memo[0] = 1;
    memo[1] = 1;
    
    for (int i = 2; i <= n; i++)
        memo[i] = memo[i-1] + memo[i-2];
    
    return memo[n];
}

재귀 함수를 이용한 방식은, 큰 문제를 먼저 마주하고, 이를 해결하기 위해 점차 작은 문제로 접근하는 방식을 위에서 아래로 내려간다고 하여 탑-다운 (top-down) 방식이라고 합니다. 하향식이라고도 합니다.

마찬가지로, 반복문을 이용한 방식은, 작은 문제부터 해결하여, 점차 큰 문제의 답을 도출하는 방식인데, 밑에서부터 위로 올라간다고 하여 보텀-업 (bottom-up) 방식이라고 합니다. 상향식이라고도 합니다.

메모이제이션이라는 표현은 탑-다운 방식에 국한되어 사용하는 표현입니다. 비슷한 개념으로 반복문에서도 값을 저장하기 위한 배열을 이용했지만, 이 경우 DP 테이블이라는 별도의 용어가 존재합니다. 또, 메모이제이션 == 다이나믹 프로그래밍 이 아님을 염두에 두어야 합니다.

또, 메모이제이션은 배열이 아닌, python의 dict 자료형을 이용하는 등, 상황에 맞는 여러 자료형을 이용할 수도 있습니다.

*본 글은 "나동빈, 이것이 취업을 위한 코딩 테스트다 with 파이썬 (한빛미디어, 2020)" 를 참고하여 작성하였습니다.