Algorithm - 17. DP(2)

📌 airtel 예제

dp에 대한 부족한 이해를 위해 참고서의 예제를 가져왔다. 에어텔 문제는 전형적인 그래프 문제는 아니지만 dp를 이용해 문제를 해결하고자 한다. 뿐만 아니라 분할정복 해결과의 비교를 통해 dp의 수행 효율을 알아본다.

배경

• n개의 도시가 있는 나라에 살고 있다.
• 도시들은 일직선 상에 위치하며 0부터 n-1까지 번호가 있다.
• 0번 도시에서 출발해 n-1번 도시로 가려고 한다.
• 도시와 도시는 우측으로만 이동해야 하고 하루에 1개 항공편을 탈 수 있다.
• 도착한 도시에서는 반드시 그 도시의 호텔에 1박을 해야하고 다음 날 아침 새로운 항공편을 탈 수 있다.

전제

• 항공 요금은 도시 구간이 멀수록 비싸고 i(1 <= i <= n-1) 구간에 대한 항공 요금은 배열 A의 A[i] 원소값으로 주어진다.
• 숙박 요금은 배열 H[1:n-2]에 주어진다. 출발 도시, 도착 도시의 숙박 요금은 포함하지 않는다.

문제

• 출발 도시 0에서 도착 도시 n-1까지의 최소 비용을 구하라.

개요

문제 해결에 대해 분할정복과 dp 방법으로 각각 해결하며 둘의 성능을 비교한다.

문제 상 공간은 1차원 배열에 나열된 n개의 도시들이다. 분할정복과 dp 방법 각각 정방향 해결과 역방향 해결 방법이 있으며 총 4가지의 접근 방식이 존재한다.

정방향 해결은 출발 도시를 0으로 고정하고 도착 도시를 출발 도시에서 가장 가까운 도시 1부터 하여 n-1(목표 도착 도시)까지 점진적으로 해를 구한다.

역방향 해결은 도착 도시를 n-1로 고정하고 출발 도시를 도착 도시에서 가장 가까운 도시 n-2부터 하여 0(목표 출발 도시)까지 점진적으로 해를 구한다.

분할정복은 재귀 알고리즘으로써 해를 구하는 순서가 재귀 호출로부터의 반환 순서와 일치하며 재귀 호출 순서와는 반대다. 반면 dp는 비재귀 알고리즘으로써 해를 구하는 순서가 계산 순서와 그대로 일치한다.

또한, 숙박 비용 H[0], H[n-1]에 0을 저장하고 문제 해결을 시작한다.

---

분할정복

정방향 해결

airtel(n-1) //출발 0부터 도착 n-1도시까지의 최소 비용을 구하고자 함


Alg airtel(dest)
	input destination city dest
    output minCost of city 0 to dest

if(dest = 0){
	return 0
}

minCost <- big integer number	//최소비용 매우 큰 수로 초기화

for k <- 0 to dest-1 {
	cost <- airtel(k) + H[k] + A[dest-k]
    minCost <- min(minCost, cost)
}
return mincost

airtel()은 도착 도시 dest에 대해 도시 k를 경유할 경우의 cost를 계산해 minCost를 구한다.

그림은 cost를 구하는 airtel(k) + H[k] + A[dest-k] 수행 내용을 나타낸다. airtel(k)는 출발 도시에서 k 도시까지의 비용을 재귀호출로 구하고 k 도시에서의 숙박 요금(H[k]), k 도시에서 목적지 dest까지의 항공 요금(A[dest-k])을 더해 도시 k를 경유하는 경우의 cost를 계산하는 것이다.

알고리즘 수행 시간은 O(2^n)이다.

역방향 해결

airtel(0) //출발 도시가 0일 때의 도착 도시 n-1까지의 minCost

Alg airtel(start)
	input start city start
    output minCost of city start to n-1
    
if(start = n-1) {
	return 0
}

minCost <- big integer number

for k <- start+1 to n-1 {
	cost <- A[k-start] + H[k] + airtel(k)
    minCost <- min(minCost, cost)
}

return minCost

역방향에서의 airtel()은 출발 도시 start에서 도시 k를 경유할 때의 minCost를 계산한다.

그림은 cost를 구하는 A[k-start] + H[k] + airtel(k) 수행 내용을 나타낸다. s에서 k까지의 항공 요금, k에서의 숙박 비용, k에서 n-1까지의 minCost를 더해 cost를 계산한다.

역방향 해결에서의 수행 시간도 O(2^n)이 된다. airtel 문제에 대한 분할정복 해결은 과도한 중복 호출로 인해 시간 성능이 크게 저하된다. 동일한 호출이 수 없이 중복되어 무려 지수 시간이 소요된다.

dp 방식이 분할정복과 다른 점은 배열에 중간 계산한 값들을 기억, 저장해 재사용함으로써 중복 연산을 피한다는 것이다.

---

동적계획법

정방향 해결

Alg airtel(n)
	input integer n
    output minCost of city 0 to n-1

minCost[0] <- 0		//연산 저장할 배열 minCost
for dest<-1 to n-1 {
	minCost[dest] <- big integer number
    
    for k<-0 to dest-1 {
    	cost <- minCost[k] + H[k] + A[dest-k]
        minCost[dest] <- min(minCost[dest], cost)
    }
}

return minCost[n-1]

minCost라는 외부 메모리를 사용해 연산을 기억해 문제를 해결해 간다. minCost[i]는 출발 도시 0부터 도시 i까지의 minCost를 의미한다.

출발 도시부터 0까지의 비용은 0이기에 minCost[0]에 0을 저장한다.

dest는 도시 1부터 목표 도착 도시 n-1까지를 반복하며, 각 반복마다 0부터 dest까지의 minCost를 구한다.

내부 반복문은 dest에 대해 도시 k를 경유하는 비용을 계산한다. 그림은 cost를 구하는 계산 내용을 나타낸다. minCost[k]는 배열에 저장된, 0부터 k까지의 minCost이다.

역방향 해결

Alg airtel(n)
	input integer n
    output minCost of city 0 to n-1

minCost[n-1] <- 0	//n-1 to n-1 is 0

for start<-n-2 down to 0 {
	minCost[start] <- big integer number
    
    for k<-start+1 to n-1 {
    	cost <- A[k-start] + H[k] + minCost[k]
        minCost[start] <- min(minCost[start], cost)
    }
}

return minCost[0]

역방향 해결에서의 minCost[i]는 i부터 목표 도착 도시 n-1까지의 최소 비용을 뜻한다.

start는 도시 n-2부터 목표 출발 도시 0까지 반복하며, 각 반복마다 start부터 n-1까지의 minCost를 구한다.

내부 반복문은 start에 대해 도시 k를 경유하는 비용을 계산한다. 그림은 cost를 구하는 계산 내용이다. minCost[k]는 배열에 저장된, k부터 n-1까지의 minCost다.

dp를 이용한 airtel 예제 해결 수행 시간은 O(n^2)로 성능이 개선된다. dp는 중복되는 문제들에 대해 아예 외부 배열에 연산 결과를 기억하고 있다가 재사용하는 방식으로 중복을 해결하고자 한다는 것이 핵심이다.

---

참고 : 국형준. 알고리즘 원리와 응용. 21세기사, 2018.