[동적계획법] Decoding Ways

 

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

 

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

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

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

 

 

Decoding Ways

 

A, B, C, D , ... , X, Y, Z가 1, 2, 3, 4, ... , 24, 25, 26 에 매칭될 때 , 주어진 수들로 만들 수 있는 디코딩 개수는 몇 개인가?

 

 

[ 2, 3, 1, 1, 2, 4, 5 ]

 

 

Top-Down

 

문자는 한 자리수 거나 두 자리수로 표현된다. 2는 B를 의미하고 23은 W를 의미한다. 

 

[ 2, 3, 1, 1, 2, 4, 5 ] 는 [  B , 3, 1, 1, 2, 4, 5 ] 와 [ W, 1, 1, 2, 4, 5 ] 으로 나뉠 수 있다. 

 

 [  B , 3, 1, 1, 2, 4, 5 ] 는  [  B , C , 1, 1, 2, 4, 5 ] 와  [  B , 31, 1, 2, 4, 5 ]로 나뉠 수 있지만 31은 문자로 존재하지 않으므로 제외한다. 

 

 [  B , C , 1, 1, 2, 4, 5 ]은 [ B, C , A , 1, 2, 4, 5 ]와 [ B , C, K , 2, 4, 5 ] 로 나뉜다.

 

이런 분할 과정을 반복하고 결합하는 과정에서 디코딩 개수를 구할 수 있다.

 

 [  B , C , 1, 1, 2, 4, 5 ] 와 [ W, 1, 1, 2, 4, 5 ]는  분할과정이 중복되므로 결과를 저장시켜놓으면 중복계산을 줄일 수 잇다. 

 

 

Bottom-Up

 

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

 

[ 2, 3, 1, 1, 2, 4, 5 ] 을 앞이 아닌 뒤부터 하나씩 처리해보자. 

 

과정 0)

[ 2, 3, 1, 1, 2, 4, 5 ]에서 5는 E를 의미한다.  ( 한 가지 ) 

 

 

과정 1)

[ 2, 3, 1, 1, 2, 4, 5 ]는 [ 2, 3, 1, 1, 2, 4, 5 ] 와  [ 2, 3, 1, 1, 2, 45 ] 로 나뉜다. 45는 문자의 범위를 벗어난다.

 

[ 2, 3, 1, 1, 2, 4, 5 ]에서 [ 2, 3, 1, 1, 2, 4, 5 ]는 한 가지이다. 

고로, 총 디코딩 경우의 수는 한 가지이다. 

 

 

과정 2)

[ 2, 3, 1, 1, 2, 4, 5 ]는 [ 2, 3, 1, 1, 2, 4, 5 ]와  [ 2, 3, 1, 1, 24, 5 ]로 나뉜다. 24는 X를 의미한다.

 

[ 2, 3, 1, 1, 2, 4, 5 ]에서 [ 2, 3, 1, 1, 2, 4, 5 ]는 한 가지이다.

[ 2, 3, 1, 1, 24, 5 ]에서 [ 2, 3, 1, 1, 2, 4, 5 ]는 한 가지이다.

고로, 총 디코딩 경우의 수는 두 가지이다. 

 

 

과정 3)

[ 2, 3, 1, 1, 2, 4, 5 ]는  [ 2, 3, 1, 1, 2, 4, 5 ]와  [ 2, 3, 1, 12 , 4, 5 ]로 나뉜다. 

 

[ 2, 3, 1, 1, 2, 4, 5]에서 [ 2, 3, 1, 1, 2, 4, 5 ]는 두 가지이다. 

[ 2, 3, 1, 12 , 4, 5]에서 [ 2, 3, 1, 12 , 4, 5]는 한 가지이다. 

고로, 총 디코딩의 경우의 수는 세 가지이다. 

 

 

이 과정을 반복(for)하면 총 디코딩 경우의 수를 구할 수 있다. 

 

 

 

총 10가지이다. 

 

 

---

 

 

참고자료