동적계획법 [Dynamic Programming - DP](2) - 실전편

 

 

○ 이어가는 글

https://kuck-su-labor.tistory.com/92

위 글에서 이어집니다.

 

 

○ 들어가는 글

 이번 시간에는 DP실제로 구현하는 것에 초점을 맞추려고 합니다. 구현할 각각의 알고리즘은 다음과 같습니다.

1. 피보나치수열을 DP로 구현하기 2. 이진트리를 DP로 구현하기

 

 

○ 피보나치수열을 DP로 구현하기

 우선 앞서 설명하자면 이번 피보나치 수를 구하는 문제는 재귀를 수행하지 않고 작성하려고 합니다. DP는 굳이 재귀로 구현하지 않아도 되고, 그래야 비용도 더 싸기 때문입니다. 

피보나치수열을 DP로 구현해 보도록 하겠습니다. DP에서 가장 중요한 것은 메모지에이션을 구현하는 것입니다. 우선 우리는 간단하게 리스트를 만들었습니다. 10번째 피보나치 수를 구하기 위한 변수도 설정하겠습니다. 

 

여기에 우리는 먼저 바닥조건을 먼저 적어두기로 합시다. 우리는 이를 위해서 미리 리스트에 바닥 조건인 fibo(1)과 fibo(2)인 [1,1]을 추가할 것입니다. 이유는 크게 2가지인데, 첫 번째로는 단순히 구현을 쉽게 하기 위함이 있고, 나머지 하나는 피포나치는 전 단계의 피보나치 수가 있어야 다음 피보나치 수를 구할 수 있기 때문에, 미리적어두는 것입니다.

 

다음으로는 반복문을 구현합니다. 피보나치 1번과 2는 이미 있기 때문에 피보나치 3번째 부터 반복을 수행합니다. (인덱스 상으로는 2번부터 실행합니다.)

 

그리고 반복문 안에는 다음과 같은 로직을 추가합니다.

 

1. n번째 피보나치 수를 구하기 위해서 n-1과 n-2를 더하는 로직
2. 1번을 수행하기 위해 n-1과 n-2가 이미 구한값이라면, 배열에서 가져오는 로직
3. 구한 피보나치 수를 배열에 저장하는 로직

 

위의 로직을 추가하여 코드를 작성한다면, 그림으로는 다음과 같은 구조이지요

 

전체 코드는 다음과 같습니다.

 

fun main() {  
    val n = 10 // 구할 피보나치 수
    var fiboList : MutableList<Int> = mutableListOf(1,1) // 피보나치 수를 저장하는 리스트
    
 	// 피보나치 수 2부터 10까지 반복 (2번째 수까지는 있기 때문)
    for(i in 2..n-1){       
       fiboList.add(fiboList[i-1]+fiboList[i-2]) // 리스트에서 값을 가져와 연산 후 다시 저장하는 로직
    } 
    
    println(fiboList) // 최종 출력
   
   
}

 

위 코드를 보면 재귀를 위한 재귀 함수도 필요 없다는 것을 알 수 있습니다. 이렇게 되면 재귀적으로 호출할 때보다 더 빠르게 연산이 가능하고 비용도 줄어듭니다.

 

 

 

○ 이진트리를 DP로 구현하기

사실 방법은 여러가지이지만 우선 저번 글에서 설명했었던 방식처럼 구현해 보도록 하겠습니다. 지금부터 설명하는 방식은 좋은 알고리즘은 아닙니다. 지금은 설명을 위해 이렇게 진행하고, 추후에 더 좋은 방법을 소개하겠습니다.

 

우선 메모지에이션을 구현해 봅시다. 이번에는 list안에 list가 들어가는 구조입니다. 이 리스트에는 각 트리의 레벨 단위로 노드 내용을 저장하려고 합니다. 저는 다음과 같이 구현하였습니다.

 

그 다음 바닥 조건을 넣어봅니다. 루트 노드에 0부터 시작하는 트리입니다. 따라서 0이 들어있는 리스트를 기본값으로 넣어줍니다. 

 

그 다음으로는 반복문을 구현합니다. 높이가 4가 될 수 있도록 3번 반복합니다. (이미 루트 노드[=바닥 조건]를 구현했으므로)

 

다음으로는 리스트를 하나 준비합니다.( subArray ) 이 리스트는 비어있는 것 이여야 합니다. 그리고 우리가 값을 저장하는 treeArray에서 마지막 값을 가져와서 요소들을 순회합니다.

 

그리고 순회하면서 각 요소당 +1 한 값과 + 0 한 값을 계산 한 후에, 이를 리스트 subArray에 넣어줍니다. 마지막으로 이를 다시 treeArray의 마지막에 넣어주면 됩니다. 

( ps. kotlin에서는 +기호로 리스트를 자체를 서로 합쳐서 이을 수 있습니다. )

 

이제 이 과정을 3번 반복하면서 트리의 구성 할 수 있습니다. 전체적인 코드는 다음과 같습니다.

 

fun main() {  
	val n = 3 // 트리의 깊이
	var nodeList : MutableList<List<Int>> = mutableListOf(listOf(0)) // 레벨 당 노드의 정보를 저장

	for(i in 0..n-1){ 
       var leftNode : MutableList<Int> = nodeList[i].toMutableList() // 왼쪽 노드에 해당하는 임시 노드에 마지막 값을 가져옴
       
       for(j in 0..nodeList[i].size-1) leftNode[j] = leftNode[j]+1 // 순회하면서 모든 값에 1씩 더함

       nodeList.add(leftNode + nodeList[i]) // 계산 후 (왼쪽,오른쪽 노드를 모두 합침) 다시 리스트에 추가
    }
    println(nodeList) // 최종 출력
        
}

 

아까전보다 복잡한 것 같지만 그렇지도 않습니다. 아래의 그림을 보면 우리가 DP로 파보나치를 구현했을 때와 크게 다른 것은 없을 것입니다.

만약 위의 코드가 복잡해 보인다면 map() 함수를 쓸 수도 있을 것입니다. 스트림과 관련된 것은 다음 시간에 다루려고 했지만, 예습겸으로 위의 코드를 거 간략하게 줄여보겠습니다. 그렇다면 다음과 같습니다.

fun main() {  
	val n = 3 // 트리의 깊이
	var nodeList : MutableList<List<Int>> = mutableListOf(listOf(0)) // 레벨 당 노드의 정보를 저장

	for(i in 0..n-1) nodeList.add(nodeList[i].map{it->it+1} + nodeList[i]) // .map()을 이용한 연산
    
    println(nodeList) // 최종 출력
}

 

위의 두 코드는 결과적으로 같은 로직입니다. 함수형 프로그래밍에 관심이 있다면 저것에 익숙해져 보세요.

 

 

 

○ 이진트리를 DP로 구현하기 - 추가

 사실 설명을 위해서 리스트를 2차원으로 만들었습니다. 만약 리스트를 풀어서 정리하자면 다음과 같이 정리할 수 있을 것입니다.

우리는 리스트를 사용했지만, 이차원 배열로 생각해도 무방합니다.

 

추가적인 이야기이지만, 2차원으로 만들게 되면 시간은 줄어들지는 몰라도 공간의 낭비가 생길 것입니다. 전체 노드를 순회하는 경우가 아니라면 2차원이 아니더라도 1차원으로 구현도 가능합니다. 왜냐하면 해당 알고리즘의 경우 전체 리스트 중에서 바로 직전 요소를 참조하는 것이기 때문에 그냥 리스트를 덮어 씌우는 구조여도 상관은 없습니다. 

만약 트리를 Dp로 구현한다고 하고, 이를 좀 더 간단하게 해봅시다.  다음과 같이 구현이 가능합니다.

 

 

fun main() {  
	val n = 3 // 트리의 깊이
	var nodeTemp = listOf(0)
    
	for(i in 0..n-1) nodeTemp = nodeTemp.map{it->it+1} + nodeTemp 
    
	println(nodeTemp)
}

 

 이는 크게 중요하지 않습니다. 이럴 수도 있다 정도로 알아주세요

 

이진트리를 DP로 구현하는 것은 의의가 어느 정도 있습니다. 백 트레킹, 완전 탐색 등등을 구현하는 데 있어서 비용을 줄일 수 있기 때문입니다. 이렇게 되면 가능한 조합의 대해서도 더 빠르고 쉽게 구현이 가능합니다.

 

 

다음 글에서 계속….