[Algorithm] Dynamic Programming 1

익히 들어봤을 다이내믹  프로그래밍에 대해 정리해보려 한다.

 

Dynamic programming

 

먼저 dynamic programming (이하 DP)이란 sub-problem의 solution들을 결합하여 문제를 해결하는 방식이다. 이는 앞서 배웠던 분할 정복 (Divide and conquer) 알고리즘과 비슷해 보이지만, 분명한 차이점이 존재한다. 분할 정복 알고리즘도 마찬가지로 문제를 서브 문제들로 나누고 해결한 다음에 합치는 것이지만 각각의 서브 문제들이 중복되지 않는다는 점이 다르다. DP는 각각의 서브 문제들을 단 한 번만 풀고, 이를 테이블에 저장해 둔 후에 필요할 때마다 꺼내서 사용한다. 이는 같은 문제를 다시 계산하는 문제를 해결할 수 있다는 장점이 있다.

 

DP는 전형적으로 최적화 문제에 적용된다. 최적화 문제란 주어진 조건 하에서 어떤 목적 함수의 값을 최대화하거나 최소화하는 변수의 값을 찾는 문제를 의미한다. 각각의 sub-problem들의 최적화된 solution을 상위 문제의 instance로 사용하고 또 이를 통해 최적화된 solution을 찾는 방식이다.

 

Four steps of DP

 

1. Characterize the structure of an optimal solution

2. Recursively define the value of an optimal solution

3. Compute the value of an optimal solution, typically in a bootom-up fashion

4. Construct an optimal solution from computed information

 

이 중에서 4번은 DP를 통해 optimal value를 구하는 것뿐만 아니라 이를 구하기 위한 optimal solution을 원할 때에 필요한 과정이다. 이를 위해서는 optimal value를 구하는 과정에서 추가적인 정보를 버리지 않고 저장해둬야 한다.

 

Rod cutting

 

DP의 대표 격 예제인 나무 막대 자르기 문제이다. 특정 길이의 나무 막대가 있고, 막대 길이에 따라 가격이 다양하다고 했을 때 어떻게 잘라서 팔아야 수익의 최댓값을 얻을 수 있는지에 대한 문제이다.

 

각 나무의 길이에 따른 가격표는 다음과 같다. 길이가 $n$인 나무 막대가 있다고 생각해 보자. 만약 우리가 모든 경우를 다 고려한다고 하면 $n - 1$ 개의 자를 수 있는 공간마다 자를지 말지 2가지 선택지가 있기 때문에 $2^{n - 1}$의 경우의 수를 고려해야 할 것이다. 하지만 이건 너무 많다!

 

Top down

 

그럼 이번에는 좀 더 효율적인 방법을 생각해보자. 우리가 $r_{n}$을 길이가 n인 막대로 얻을 수 있는 최대 수익이라고 한다면, 이에 대한 식을 이렇게 나타낼 수 있을 것이다.

$$r_{n} = max(p_{n}, r_{1} + r_{n - 1}, r_{2} + r_{n - 2}, ... , r_{n - 1} + r_{1})$$

여기서 $p_{n}$은 길이가 n인 막대의 가격을 의미한다. 이를 의사 코드로 나타내면 다음과 같다.

이는 얼마나 오래 걸리는 코드일까? 시간복잡도를 계산해 보자.

다음은 막대의 길이가 4 ($n = 4$)인 경우이다. 깊이가 1일 때의 연산인 2, 1, 0은 깊이가 2일 때에도 발생하고 있다. 이 모든 연산들을 계속해서 다시 해주는 것만큼 비효율적이고 수고스러운 일은 없을 것이다.

 

길이가 n인 막대를 계산하는 데에 걸리는 시간을 $T(n)$이라고 한다면 위 코드를 실행시켰을 때 걸리는 시간은 다음과 같다.

$$T(n) = 1 + T(n - 1) + T(n - 2) + ... + T(0)$$

시간복잡도 계산에 대한 증명은 다음과 같다.

따라서 $T(n)$의 러닝 타임은 $(2^{n})$가 된다.

 

Top-down with memoization

 

위 그림에서 봤듯이 똑같은 경우를 계산해줘야 하는 경우가 생기는데, 이를 저장해 둔다면 효율이 많이 올라갈 것으로 예상된다. 이렇듯 계산해야 하는 상황에서 이미 그 값이 계산되어 있는지를 확인해 보는 시행을 거쳐주는 방식을 memoization이라고 한다.

왼쪽 코드는 저장해 줄 배열을 초기화하는 녀석이라 별로 안 중요하고, 중요한 것은 오른쪽 코드이다. 1번째 줄에서는 값이 이미 저장되어 있는지를 확인한다. 한번 저장된 값이 그 경우에서의 최적화 정답이므로, 0 이상인지만 봐주면 된다. 코드를 보면 알겠지만, 한 번 저장된 정답은 바뀔 일이 없다. 3번째 줄은 막대의 길이가 0일 때이므로 0을 반환하고, 나머지 경우에서는 top-down 방식으로 q의 값을 계산한다. 한 가지 다른 점은 8번째 줄처럼 계산된 값을 배열에 저장한다는 것이다.

 

Bottom-up

그런데 어차피 이렇게 계산할 바에는, 그냥 더 작은 막대 길이에서의 최댓값을 미리 구해놓으면 되지 않겠는가? 그렇게 하면서 원하는 길이에 도달할 때까지 올려준다면 우리는 결국 이 순서로도 해답을 구할 수 있을 것이다. 이렇게 아래서부터 차근차근 정답을 찾아가는 과정을 bottom-up 방식이라고 한다.

 

 

마지막으로, 그러면 두 방식 중에 어떤 게 더 오래 걸릴까? 시간 복잡도 측면에서는 같은 asymptotic running time을 가지지만, bottom-up 방식이 constant factor 부분에서 이점을 취한다. 왜냐하면 top-down에서의 재귀적 호출은 더 큰 오버헤드를 가지고 있기 때문이다.