동적계획법 [Dynamic Programming - DP](1) - 개념편

○들어가는 글

저번 시간부터는 동적 계획법의 대해서 알아보려고 합니다. 간략하게 개요에서는 왜 이것을 사용하게 되었는지 간략하게 소개하고 어떠한 방법론을 가졌는지 까지 해서 간단히 이론의 대해 설명드리도록 하겠습니다.

 

○개요

이전 글에서 간략하게나마 재귀알고리즘 즉 분할 정복의 단점의 대해서 알려드렸습니다. 재귀가 많이 일어나서 비용이 많이 발생한다는 것이었죠.

위와 같은 이야기를 꺼낸 것은 동적 계획법은 분할정복법에 뿌리를 두고 있기 때문입니다. 동적계획법은 분할 정복법과 비슷한 알고리즘으로 동작합니다.  큰 문제를 해결하기 위해서 작은 문제로 분할하고, 이를 재귀적으로 해결하는 것까지 동일합니다. 

하지만 차이점이 있다면 재귀로 구한 작은 문제의 결과들을 저장하였다가, 나중에 같은 문제가 나왔을 때, 재귀를 수행하지 않고 저장한 값을 대신 사용한다는 것입니다.

이것만 본다면 한 번에 이해하기 힘들 수도 있습니다. 때문에 우선 분할 정복을 구하는 과정을 살펴보도록 합시다. 

 

 

한번 10번째 피보나치를 구하는 과정을 알아봅시다.  아래는 10번째 피보나치수를 구하기 위해 분할 정복을 수행하는 과정을 그림으로 나타내었습니다. 

최대한 그려보면 저렇게 많은 재귀가 수행되어야 합니다.

 

10번째 피보나치 수는 9번째 피보나치 수와 8번째 피보나치 수, 총 2개의 수를 더하는 것으로 구할 수 있습니다.  우선  9번째 피보나치 수인 fibo(9)를 구해보도록 합니다. 

우선 10번째 피보나치 수인 fibo(10)을 구하기 위해서는 fibo(9)가 필요합니다. 그리고  fibo(9)를 구하기 위해서는  fibo(8)가 필요하지요. 결국 fibo(10)을 구하기 위해서라면  fibo(9)부터 바닥 조건인  fibo(1)까지 모두 구해야 할 것입니다. 

 

우선 그림으로써는 다음과 같은 영역을 모두 구한다고 볼 수 있겠습니다. 우선 우리는 재귀적으로 수행하면서 fibo(1)부터 fibo(9)를 모두 구한 셈입니다. 

9번째 피보나치 수를 구한 상태 (연두색)

이제 fibo(9)를 구했으니, 8번째 피보나치 수인 fibo(8)을 구해야만 합니다. 이때 잠깐 위 그림을 잠깐 되돌아봅시다. 우선 위 그림에서 각 피보나치 수를 구하는 부분 중 겹치는 부분을  한번 표시해 보았습니다. 

 

진하게 칠한 연두색이 같은 값이라는 것을 알 수 있습니다.

 

거의 대부분이 겹치는 것을 알 수 있습니다. 즉 이미 우리는 이미 fibo(9)~fibo(1)의 모든 피보나치 수를 구했음에도 불구하고  fibo(8)을 구하기 위해서 다시 fibo(8)~fibo(1)의 모든 피보나치 수를 재귀적으로 구해야만 합니다. 

이는 비효율 적이지만, 재귀적으로 구성되어 있는 분할 정복법 특성상 이는 비용에 매우 큰 부담으로 다가오게 됩니다. 

○동작

위의 내용에서 이어서, 이번에는 9번째 피보나치 수를 구하는 과정에서 각 피보나치 수들을 배열 같은 선형 자료구조에 저장한다고 해 봅시다. 우선 위에서 우리가 했던 것처럼, fibo(9)를 구한 것 처럼 fibo(1) ~ fibo(9)까지의 수를 모두 구한 상태라고 가정해 봅시다. 

 

피보나치 수를 구하면서, 구한 값들을 모두 어디엔가 저장하였습니다.

 

이제 8번째 피보나치 수인 fibo(8)을 구해봅시다. 우선 분할 정복을 수행하기 전에 지금까지 구한 피보나치수 중 하나라면, 굳이 구할 필요는 없을 것 같습니다. 우리는 이미 fibo(8)을 구했기 때문에, 더 이상의 재귀 연산은 필요 없습니다. 따라서 다음과 같이 재귀 연산은 생략됩니다. 

 

8번째 피보나치 수를 이미 구했었기 때문에 빗금 친 부분은 따로 구할 필요가 없습니다. 

 

우리는 지금 fibo(8)의 한에서만 다루어 보았습니다. 하지만 이는 분할정복 즉 재귀적인 구조라는 것을 알아야 합니다. 다른 피보나치 수를 구하더라도, 재귀적으로 구하는 과정은 생략됩니다. 따라서 최종적으로 분할 정복하여, 재귀가 발생되는 부분은 다음과 같습니다. 

 

실제 동적계획법을 사용하면 진하게 칠해진 부분만 구하는 것으로 해를 두출할 수 있습니다.

 

위와 비교하였을 때, 매우 간결해진 것을 알 수 있습니다. 이렇게 한다면 계산에 들어가는 비용도 많이 줄어들 것입니다. 실제 분할 정복으로 구현했을 때와 비교하면 과정과 비용 측면에서 유리합니다. 

 

 

 ○동적 계획법 방법론

피보나치수를 구하는 것은 결국 분할 정복의 개념이지만, 위의 방법에서 하나 다른 점이 있었다면 그것은 바로 창고를 구현하고 재사용한다는 것입니다.

 

창고를 구현하는 것 이것을 메모지에이션 (Memoization)이라고 합니다. 무언가를 메모해 놓는다는 뜻이죠. 그리고 이러한 메모지에이션을 분할 정복과 결합해서 사용하는 것이 바로 DP 즉 동적 계획법(Dynamic Programming, DP)입니다. 간단히 설명하면 다음과 같이 설명할 수 있습니다.

 

 

메모지에이션의 대해서 더 설명할 수도 있고, 또 이것 외에도 타뷸레이션이라는 것도 있는데 우선 우리가 알고 싶은 것은 DP니 여기까지만 하죠

 

결과적으로 우리가 기억해야 하는 것은 분할 정복에 창고를 만들어 값을 저장하고, 값을 재사용하는 것이 바로 동적 계획법(DP)이다.라고 기억해 주시면 될 것 같습니다.

 

 

 

○이진트리의 DP

예시를 한번 들어보죠. 트리도 DP로 구현할 수 있습니다. 저번에 우리가 재귀로 이진트리를 구현했었죠? +1과 +0을 담는 이진트리였습니다. 이것 또한 분할 정복으로 풀었으니, DP로 구현할 수 있을 것입니다.

우선 구현은 다음 시간에 하고 방법에 초점을 맞춰봅시다. 우선 트리를 표현해 보았습니다. 최대 레벨이 3인 빈 트리를 만들어 보았습니다. 

 

DP의 핵심중 하나는 메모지에이션입니다. 우선 하나의 창고를 만들어 봅시다.

 

그리고 한번 살펴봅시다. 트리에서 위에서 아래로 내려가는 경우를 봅시다. 루트 노드로부터 시작해서 각 노드는 자기 자신을 또다시 호출하게 되어 있습니다. 호출하면서 한쪽 노드로는 +1을, 한쪽 노드로는 +0을 하고 있지요.

 

만약 재귀를 호출하지 않고 구현할 수 있다면 어떨까요? 핵심은 트리의 각 층(레벨) 끼리 같이 묶어서 저장하는 것입니다.

 

우선 처음에 루트 노드인 0을 창고에 저장합니다. 그렇게 한 다음, 다음 레벨에서는 저장했던 0을 통해서 다음 레벨을 만들 수 있습니다.

 

다음 레벨에서는 0을 이용해서 한쪽은 +1 한쪽은 +0 인 것을 생각해서 1과 0을 구합니다. 이것을 묶어서 창고에 [1 , 0]을 저장할 수 있습니다. (직접적인 구현은 다음 글에서 하겠습니다. 우선 이런 흐름이다 라는 것만 생각해 주세요)

 

 다음 레벨에서는 아까 저장했었던 [1 , 0]를 불러오고 각 요소 [1]과 [0] 마다 한번 더 처리해서 [2,1 , 1,0]을 다시 저장

 

다음 레벨에서는 아까 저장했었던 [2,1 , 1,0]를 불러오고 각 요소 [2] [1] [1] [0]에 한번 더 처리해서 [3,2 , 2,1 , 2,1 , 1,0]

 

 

이렇게 하면 최종적으로 +0과 +1의 해당 모든 조합의 수를 구할 수 있다고 할 수 있습니다.

 

 

 

다음 시간에는 이것을 실제로 구현하는 방법의 대해서 알아보도록 하겠습니다.

( 다음시간에 계속.... )