동적프로그래밍, 동적계획법, Dynamic Programming

다음 글은 '코딩인터뷰 완전분석'이라는 책을 정리한 글입니다. 문제가 있거나, 잘못된 부분이 있다면 댓글로 남겨주세요!

동적프로그래밍이란?

---

동적 프로그래밍은 반복적으로 호출되는 부분을 찾아 나중을 위해 결과를 캐시에 저장해 놓는 알고리즘 방식이다. 

재귀법으로 구현해보기

---

피보나치 수열을 예제로 들어보자. 만약 재귀법으로 구현을 한다면 다음과 같을 것이다.

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

하지만, 재귀법으로 구현을 할시 N번째 피보나치 수를 생성하는 데 걸리는 시간이 N이 커짐에 따라 기하급수적으로 증가하므로, 최적화할 방법이 필요하다.

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

---

피보나치 수열을 재귀법으로 작성하면 많은 노드들이 중복되어 호출된다. 예를 들어  fib(5)를 구한다고 했을 때, fib(3)은 두 번, fib(2)는 세 번이 호출된다. 이들이 호출될 때마다 다시 계산할 필요는 없다. 따라서 fib(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];
}

memo 배열에 이미 계산된 부분은 캐시값으로 넣어놓고, 다시 해당 값을 계산해야 할 경우, 배열에 있는 값을 가져와서 사용하는 방식으로, 수행시간은 O(n)이 된다. 

상향식 동적 프로그래밍

---

동적 프로그래밍 문제를 풀 때 상향식으로 구현할 수도 있다. 먼저 초기사례인 fib(1)과  fib(1)을 계산하고, 그 뒤 이 둘을 이용해  fib(2)를 계산하고 순서대로 3, 4.. 도 같은 방식으로 이용하면 된다. 

int fibonacci(int i) {
    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;
}

간단하게 동적 프로그래밍에 대해서 알아보았고, 다음에는 동적 프로그래밍 문제를 풀어보도록 하자. 풀 수 있으려나 모르겠지만.. 일단 풀어보도록 하자.