동적 계획법

흔히 동적 계획법을 동적 프로그래밍이라고도 부르는데, 일반적으로 사용하는 동적(dynamic), 혹은 프로그래밍(programming) 이런 단어와는 전혀 관련이 없다. 따라서 dynamic programming은 동적 계획법이다. 동적계획법은 거의 대부분 재귀적 알고리즘과 반복적으로 호출되는 문제를 찾아가는 것이 관건이다. 하지만 재귀(recursive) 를 사용해서 스택  layer에 계속 추가를해서 깊이가 깊어 질수록 많은 메모리를 사용해서 메모제이션 기법으로 두번 이상 반복 계산되는 부분 문제들의 답을 저장함으로써 속도를 꾀할 수 있다.

 

재귀를 사용해서 푸는 문제중 가장 대표적인 피보나치 수열을 통해 동적 계획법을 적용해보자.

 

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

 

 

이 함수의 수행시간은 어떻게 될 까? 먼저 아래의 재귀 트리 예시를 살펴보자. 각 호출에 소요되는 시간은 O(1)이므로 전체 노드의 개수와 수행시간은 같다. 또한 루트 노드는 두개의 자식 노드를 갖고 있다. 이런식으로 자식의 자식 노드가 두개의 자식을 갖고 있고 계속적인 반복이 n번 반복이 되면 O(2^n)이 된다.

추가로 O(2^n)보다는 살짝 빠르다. 왜냐하면 항상 오른쪽 부분트리가 왼쪽 부분 트리보다 항상 작다는 사실이다 만약 동일했으면 맞겠지만, 하여튼 실제 수행 시간은 O(1.6^n)에 가깝다.

 

이를 컴퓨터로 구현하면 수행시간이 기하급수적으로 증가한다.

 

실제로 일반 재귀식으로 피보나치 수열을 0이상의 정수가 n이 주어졌을때 n번째 피보나치 수를 구할때 n이 100이라면 실행이 끝나지 않는다. 또한 100의 절반인 n값이 50번째 피보나치수를 구하면 컴퓨터 성능에따라 30s~1분이상이 소요될 수 있다. 물론 int 자료형 때문에 overflow가 발생할 수 있다.

 

 

 

하향식 동적 프로그래밍(메모제이션)

이 문제를 메모제이션을 이용하여 캐시에 저장하고 나중에는 저장된 값을 사용해보자. O(N)의 시간복잡도가 나오게 구현됐다.

 

    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];
    }

 

 

메모제이션을 통한 중복호출 방지

좌측 끝 노드에서는 N값이 0이 될때까지 계속 감소하다가 나머지 우측 노드인 fibonacci(i - 2, memo) 를 호출해 스택 레이어를 사용하지 않고 사용된 캐시 값을 그대로 반환하게된다.