[알고리즘] 동적프로그래밍(Dynamic programming)

1. 동적프로그래밍(Dynamic programming) : 큰 문제를 작은 부문제로 나누어서 풀어나가되, 이미 계산했던 연산이라면 다시 하지 않고 기록되어 있는 값을 가져와서 진행하도록 하는 방식이다.  

예를 들어, 피보나치 수열을 재귀를 이용해서 풀면 다음과 같다.

 

#include <iostream>

int fibo(int num)
{

   if(num == 1)
      return 1;
   else if( num ==2 )
      return 1;
   else
      return fibo(num-1)+fibo(num-2);

}

int main() {

   int num;
   std::cin >>num;

   std::cout<< fibo(num)<<std::endl;

   return 0;

}

 

이를 그림으로 표현하면 다음과 같이 fib(5)를 구하기 위해 fib(2), fib(3) 등의 부문제의 계산을 여러번 반복해야 함을 확인할 수 있다. 이러한 문제를 극복하고 효율성을 높이기 위해 동적프로그래밍이 고안되었다.

 

피보나치 수열

---

2. 동적프로그래밍을 적용하면 다음과 같이 피보나치 수열을 구할 수 있다.

 

#include <iostream>
#include <algorithm>

int f[100] = { 0, };

int fibo(int num) {
    f[0] = 0;
    f[1] = 1;
    if (num >= 2) {
        for (int i = 2; i <= num; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
    }

    return f[num];
}

int main() {
    int n;
    std::cin >> n;
   
    std::cout << fibo(n);

	return 0;
}

 

즉, 하나의 문제를 여러 부문제로 나누고, 부문제의 결합을 통해 최종해를 구해나가는 방식이다.

---

3. 문제를 분할하고, 분할된 부문제의 결합을 통해 최종 목적지를 향해 간다는 점에서 동적프로그래밍은 분할통치법과 비슷하다고 볼 수 있다. 이들의 공통점과 차이점을 정리해 보자면, 다음과 같다.

 

공통점	차이점
원점-목표점 구조의 문제공간에서 정의된다. (원점 : 문제의 초기 지점. 목표점 : 최종해가 요구되는 지점)	문제 해결의 진행방향 : 동적프로그래밍은 단방향(원점 -> 목표점) / 분할통치는 양방향(목표점 -> 원점 -> 목표점) 성능 : 동적프로그래밍은 단방향적 특성으로 인해 효율적임 / 분할통치는 분할 회수 및 중복 연산의 수행이 요구됨.

---

4. 예제) 에어텔(Airtel)

 

[문제] n개의 도시가 일직선상에 위치하며 0부터 n-1까지 번호가 매겨져 있다. 도시 0에서 출발하여 n-1로 가고자 한다. 도시와 도시 사이는 오른쪽으로만, 그리고 항공편으로만 이동해야 하며 하루에 한 개의 한공편만 이용 가능하다. 항공편이 도착한 도시에서는 반드시 그 도시의 호텔에서 1박을 해야하며 다음날 아침 새로운 항공편으로 여행을 계속하도록 한다. 여행의 최소 비용을 구하는 알고리즘을 작성하시오.

 

(항공요금은 도시 구간이 멀수록 비싸며 i(1<=i<=n-1) 구간에 대한 항공요금이 배열 A의 A[i] 원소값으로 주어진다. 각 도시의 호텔 숙박요금은 배열 H[]에 주어진다. 이때, 도시 0과 n-1에서는 숙박할 필요가 없다.)

 

[풀이] 도착도시 0에 대한 최소비용 m[0]을 0으로 초기화 해 놓는다. 도착도시 d(1<=d<=n-1)에 대해서 도시 k를 경유한다면, k는 0<=k<=d-1 의 범위를 갖는다. 이러한 k를 경유하는 경우의 도착 도시 d까지 가는 최소 비용을 찾아 m[d]에 저장한다. cost = m[k] + H[k] + A[d-k] 로 계산 가능하고 0<=k<=d-1 의 각 경유도시 k에 대해서 계산되는 가장 작은 cost를 m[d]에 저장하면 된다. 앞서 기록 된 m[k]의 값을 그대로 가져다 계산하는 동적프로그래밍을 통해 중복된 계산을 피하고 효율을 높일 수 있다.

 

[코드]

#include <iostream>

#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
#define INF 10000

int A[] = { 0, 1, 3, 6, 11, 17 }; //거리에 따른 항공 비용. 
int H[] = { 0, 2, 5, 1, 5, 0 }; //그 위치에서의 호텔 비용 
int m[10];

int airtel(int n) {
	m[0] = 0;
	int cost;
	int d, k;
	for (d = 1; d < n; d++) { //도착도시 d 
		m[d] = INF;
		for (k = 0; k < d; k++) { //경유지 k 
			cost = m[k] + H[k] + A[d - k];
			m[d] = min(m[d], cost);
		}
	}

	return m[n - 1];

}

int main() {
	std::cout << airtel(6);
}