[동적계획법] 최소비용 계단 오르기 ( Min Cost Climbing Stairs )

 

동적계획법(Dynamic Programing)이란?

 

복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법

동적계획법은 분할된 모든 경우의 수를 검토한다. 

중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. 

 

 

Min Cost Climbing Stairs 

 

사람은 한번에 한 칸 혹은 두 칸의 계단을 오를 수 있다. 계단을 오르는데 필요한 비용(cost)이 있다고 가정할 때, 꼭대기까지 오를 수 있는 최소비용을 얼마인가?

 

 

 

Top-Down

 

계단4(꼭대기)에 도달하려면 계단2에서 두칸 뛰거나 계단3에서 한칸 뛰어야 한다.

 

 

 

계단을 뛰는데 걸리는 비용을 트리로 표현해보자.

 

 

 

계단2에서 계단4까지는 비용이 4가 든다. 그러나 Top-Down 방식이므로 계단2까지 오는데 걸린 비용도 고려해야한다. 

 

 

 

1) 계단0 → 계단2 ( 비용 = 0 )

2) 계단0 → 계단1 → 계단2 ( 비용 = 1 )

 

계단2까지 가는데 최소비용은 0과1 중 0이다. 계단 별 도착시 최소비용을 배열로 정리한다.

 

계단 별 도착시 최소비용 배열

 

 

계단3은 최소비용을 모르니 분할(Down)해야한다. 

 

 

1) 계단2 → 계단3 ( 비용 = 4 )

2) 계단1 → 계단3 ( 비용 = 1 )

 

계단1과 계단2는 이미 최소비용을 계산했다. 

 

계단 별 도착시 최소비용 배열

 

그러므로 다시 분할하여 검토할 필요가 없다. 1)과 2) 최소비용을 비교하면 1이 나온다. 그러므로 계단3의 최소비용은 1이다. 

 

계단 별 도착시 최소비용 배열

 

이렇게 계단2와 계단3의 도착 시 최소비용을 구했으니 이제 계단4의 최소비용을 구해보자.

 

1) 계단2 → 계단4 ( 비용 = 0 + 4 = 4 )

2) 계단3 → 계단4 ( 비용 = 1 + 6 = 7 )

 

1)이 2)보다 작으므로 계단4(꼭대기)까지 가는데 걸리는 최소비용은 4가 된다. 

 

계단 별 도착시 최소비용 배열

 

 

Bottom-Up

 

Top-Down 방식은 보통 재귀함수로 구현된다. 재귀함수는 같은 함수를 반복적으로 호출하는 방식이다. 함수는 영역(local)을 갖는다. 그래서 많이 호출되면 그만큼 스택메모리를 잡아먹는다. 엄청나게 큰 수를 구하고 싶으면 그만큼 많은 함수가 호출되므로 스택오버플로우가 발생할 수 있다.

 

 

 

계단0부터 하나씩 도착시 최소비용 배열을 채워가며 구해볼 것이다.

 

계단 별 도착시 최소비용 배열

 

계단1의 최소비용은 0이다.

 

계단2는 두 가지 방법이 있다.

 

1) 계단0 → 계단2 ( 비용 = 0 )

2) 계단0 → 계단1 → 계단2 ( 비용 = 1 )

 

min( 0 , 1 ) = 0 이므로 0을 채워준다. 

 

계단 별 도착시 최소비용 배열

 

 

이와 같은 방식을 반복하면 계단4까지 값을 구할 수 있다.

 

 

계단 별 도착시 최소비용 배열

 

---

 

 

참고자료