[알고리즘] Dynamic Programming (동적 계획법)

동적 계획법, Dynamic Programming(DP)는 최적화 이론의 한 종류로, 특정 값을 구하기 위해서 다른 범위의 값을 이용해 효율적으로 값을 구하는 알고리즘으로, 쉽게 말해 답을 재활용하는 알고리즘이다.

답을 구하기 위한 계산을 반복하는 구조, 즉 같은 답을 계속 내서 다른 값을 이용해야 하는 문제(대표적으로 피보나치 수열)에 매우 뛰어난 방법이다.

 

분할 정복 기법 - 큰 문제를 작은 문제로 쪼개어 풀이하는 알고리즘에서 값을 저장하는 로직이 추가되었다고 할 수도 있다. 

가장 중요한 아이디어는 문제를 재계산(예를 들어 재귀적으로 풀이하는 기법)하지 않는 것이고, 이를 막기 위해 값을 기억하거나 테이블을 만들어 해결한다.

그러므로, 최종 목표를 달성하기 위한 단계를 한 번 씩만 풀게 된다는 것을 보장할 수 있다.

 

풀이 방식은 다음과 같다.

1) 최적 풀이의 구조 고안

2) 최적 풀이값 재귀적 정의(실제 재귀는 아님)

3) Bottom-Up or Top-Down 방식으로 최적 풀이값 계산

4) 계산된 정보로 최적 풀이 구성

 

Top-Down / Bottom-Up 방식

DP를 푸는 방법은 2가지가 있다. 바로 Top_Down과 Bottom-Up인데, 하향식과 상향식 방법이라고도 한다.

각자 방식이 약간 다르고 장단점이 있는데,

Top-Down 방식은 큰 문제에서 작은 문제를 호출하며, 그 값을 저장해가며(memoization) 문제를 해결한다.

따라서 필요한 부분만 계산할 수 있지만 오버헤드가 발생한다는 단점이 존재한다.

Bottom-Up 방식은 테이블을 활용해 문제를 해결하는 방법으로 작은 문제들을 차근차근 테이블에 저장해놓고 큰 문제를 해결한다. 주로 2차원 배열과 반복문로 구현한다.

반복문과 배열을 통해 구현 가능하며 최적화가 쉬운 반면, 답을 구하는 과정에서 불필요한 연산이 발생하는 단점이 발생한다.

 

왜 동적계획법으로 문제를 풀까?

이렇게 동적계획법의 개념을 쭉 설명해 보았는데, 지금부터는 동적 프로그래밍이 아니어도 문제를 해결할 수 있음에도 왜 동적계획법을 이용해서 문제를 푸는지 설명해 보겠다.

앞서 서술했듯, 동적 계획법은 반복 연산이 많이 수행되는 문제에서 유리하다.

그러한 예제 중에서 대표적인, 피보나치 수열을 보자.

피보나치 수열은 n번째 항이 (n-1)번째 항과 (n-2)번째 항을 더한 값이다. 이때 n번째 항을 구하려면 (n-1)번째 항까지를 모두 알아야만 구할 수 있다.

그래서 저 간단한 정의를 C언어로 나타내면 저렇게 함수를 계속 호출해 반환받은 값으로 항을 계산하고 있는 것을 확인할 수 있다. 그렇다면 이게 왜 문제가 되는가?

아래 그림을 보자.

 

피보나치 수열의 4번째 항을 구하는 과정을 트리 구조로 만들어 보았다. 

트리를 보면, fib()은 값을 받아 계산하여 반환하는 함수들인데 같은 함수들이 반복적으로 자주 호출되는 문제가 발생한다.

이미 값을 계산해서 반환했음에도, 다음 항으로 넘어가면 또 같은 내용을 계산하게 되는 것이다.

처음에는 별 차이가 없을 수 있지만, n의 값이 크게 증가함에 따라, 시간 복잡도는 기하급수적으로 늘어나는 문제가 발생한다. 그래서 이를 해결하기 위해, 한 번 계산한 내용을 어딘가에 저장해 반복 연산을 줄이는 동적 계획법을 사용하는 것이다.

 

동적 계획법으로 풀게 되면, 하위 문제들을 다시 풀어내는 것이 아니라 저장/테이블을 이용해 값을 가져다 쓸 수 있게 되므로 시간 복잡도(Time Complexity)가 크게 감소하게 된다.

 

Top-Down pseudocode

C언어 형식으로 간단하게 적어본 pseudocode(의사코드)이다.

Top-Down은 메모하는 방식을 사용하기 때문에 하위 문제를 호출하면서 그 값을 저장한다. 

따라서 구하고자 하는 값이 이미 존재하면 (계산한 적이 있다면) 함수 호출이 아니라 저장했던 값을 불러와 계산을 수행한다.

 

Bottom-Up pseudocode

Bottom-Up의 pseudocode이다.

피보나치 수열은 1차원 배열로도 구현이 가능한데, 하위 문제를 계산한 것을 배열로 저장하여 그것을 차례대로 반복문을 돌리며 상위 문제의 계산에 사용한다.