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

동적 계획법

정의 : 어떤 문제가 반복적이고 최적 하위구조로 이루어질때, 하위구조에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법

최적 하위구조(Optimal Substructure)란 전체 문제의 답이 부분 문제의 답으로부터 만들어지는 구조를 말한다. 예를 들어 어떤 문제를 7개의 하위문제로 나눌 수 있을때, 7개의 하위문제의 답을 모두 얻어야 이 문제의 답을 구할 수 있다면 이 문제는 최적 하위구조를 갖추었다고 할 수 있다.

분할정복과 비슷해 보이지만, 분할정복은 문제를 큰부분에서 작은부분으로 나누는데반해(Top-Down), 동적 계획법은 제일 작은 부분부터 큰 문제로 풀어 올라간다(Bottom-Up). 또한 분할정복은 나눈 문제들을 완전히 새로운 하나의 독립된 새로운 문제로 보지만, 동적 계획법은 이전 단계의 답에 의존적이다. 그래서 한번 푼 적 있는 문제는 다시 푸는 일이 없도록 테이블 등에 저장해둔다.

 

알고리즘

1. 문제를 부분 문제로 나눈다.

2. 가장 작은 부분의 문제부터 답을 구한 뒤 테이블에 저장한다.

3. 테이블에 저장되어 있는 부분 문제의 답을 이용하여 점차적으로 상위 부분의 문제의 답을 구한다.

 

동적 계획법의 활용

1. 피보나치 수열 (Fibonacci Sequence)

피보나치 수열은 다음과 같이 정의할 수 있다.

 

 

이것을 그냥 코드로 옮기면 다음과 같이 작성된다.

int Fibonacci(int n) {
    if (n > 1)
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    else if (n == 1)
        return 1;
    else
        return 0;
}

이 알고리즘의 수행시간은 으로 상당히 비효율적이다.

동적 계획법을 이용하여 이 알고리즘을 재구성해보자.

 

먼저 문제를 부분 문제로 나눈다.

 

은 과 의 합이다.

은 와 의 합이다.

그리고 은 과 의 합이다.

 

이로부터

이라는 문제를

, , …, , , 의 하위구조로 나눌 수 있는 것을 알 수 있다.

 

두번째로 작은 부분의 답을 구한뒤 테이블에 저장한다.

인덱스	저장된 값
0	0
1	1
2	1
3	2
4	3
5	5
6	8
...	...
n-2
n-1
n

 

과 는 이미 정의되어 있는 값을 저장하면 되고,

부터는 테이블에 저장된 값을 이용하여 답을 구해 나간다.

계속 구해나가면 의 값을 구할 수 있다.

 

이렇게 구한 피보나치 수의 시간 복잡도는

이다.

 

분할정복으로 구한 시간 복잡도는

이였지만

 

동적 계획법으로 구한 시간 복잡도는

로써 분할정복보단 떨어진다.

 

더 나은 기법을 알기 위해서가 아니라 알고리즘 설계 기법의 이해를 위한 것이므로 뭐가 더 우수한지는 논외로 하기로 한다.