주요 내용으로 건너뛰기

Dynamic Programming

Divide and Conquer 라 함은, 주어진 N개의 Input에 대하여 disjoint인 작은 sub problem들로 나누고, 하위 문제들에 대하여 재귀적으로 각각의 솔루션을 구한 결과를 합쳐서 전체 문제에 대한 해답을 찾는 것이다.

Dynamic Programming 도 문제들을 쪼개어 각각 해결해나간다는 점에서 유사하지만, 한 가지 구별되는 큰 특징이 있다. sub problem들을 푸는 동안 각각의 문제 해결 과정에서 overlap 되는 현상이 나타난다는 것이다. 즉 공통되는 계산이 반복될 때 그 sub problem은 한 번만 계산한 후 메모리에 저장해두었다가 추후 다시 같은 문제에 대한 call이 발생할 때 저장했던 값을 바로 가져다 쓰는 것이다. 

만약 어떤 상황에서 최소 혹은 최대의 solution을 찾으라는 문제가 나왔다고 했을 때, 여러 가지 possible 한 solution 중 그 값이 최소 혹은 최대 인지만을 확인하고 그중 하나만을 찾는다. 이런 이유로 An optimal solution이라고 부르지만 The optimal solution이라고는 하지 않는다. 답이 여러 개 있을 수 있지만 하나만 찾으면 되기 때문이다. 

다이나믹 프로그래밍이 적용되려면 두가지 조건이 필요하다.

1) Optimal Substructure Property : 주어진 문제에 대한 최적해를 구하고자 할 때, 좀 더 작은 sub-problem들에 대한 optimal solution들을 찾은 후 그것들을 결합하면 결국 전체 문제의 optimal solution 이 되는 경우이어야 한다. (이는 그리디 알고리즘에서도 유사하게 적용된다.)

2) Overlapping Subproblems Property : sub-sub problem 간에 중복되는 경우가 여러 번 발생하는 경우이다. 그렇다면 이것을 매번 계산하지 않고 먼저 계산한 값을 배열이나 해시 테이블에 저장해두었다가 다음번 수행 시 즉시 반환할 수 있다. 

이 두가지 조건이 확인된다면 다이나믹 프로그래밍을 해결할 수 있는 문제이다.

우선 Optimal substructure인 것이 확인되면 다이내믹 프로그래밍으로 접근해볼 수 있겠다는 단서를 찾게 되지만, 구체적인 Overlapping Subproblem을 찾아낼 때까지는 다이내믹 프로그래밍으로 해결이 가능하다고 확신할 수는 없을 것이다. 


대표적인 예제인 Rod cutting problem 을 생각해보자. 주어진 막대기가 있을 때, 각각의 size마다 가격이 다르다면 어떻게 자르는 것이 가격을 최대로 할 수 있는지를 결정하는 문제이다.

이 문제를 naive 한 Recursive Top-down Implementation으로 풀면 아래와 같을 것이다. 

  1. size i=1 부터 i=n 까지 2 & 3을 반복한다. 
  2. i 번째에서 cut하는 경우와 그렇지 않은 경우에 대해 비교하여 판단한다.
  3. 해당 작업을 1부터 n-i에 이르기까지 반복한다.
  4. 루프를 종료할 때까지 max() 를 계산하여 그 결과를 q에 저장한다.
  5. 최종적으로 갱신된 q가 정답이 된다. 만약 최댓값에 이르기까지의 모든 q 값들을 저장하기 위해서는 추가적인 메모리가 요구된다.

하지만 이 해법은 exponential time complexity를 갖게된다. 때문에 이를 개선하기 위해서는 다른 방법이 필요하다. 컴퓨터는 메모리라는 저장공간을 갖는데, time과 memory를 trade-off 관계로 이용할 수 있다. 즉 메모리를 조금 더 활용함으로써 계산 시간에서 더 큰 이득을 얻는 것이다.


Dynamic Programming을 구현하는 방식은 크게 두가지 형태가 있다.


1) Top-down method with memoization

  • 일반적으로 recursively 방식으로 함수를 구현하되, 배열이나 해시테이블을 사용하여 subproblem의 결괏값을 저장해둔다.
  • 어떤 계산이 요구되었을 때, 먼저는 해당 값을 이전에 계산했던적이 있는지를 확인한다.
  • 만약 있다면, 저장되어 있는 해당 값을 바로 반환한다.
  • 만약 없다면, 계산한 후 이 값을 추가로 저장하고 반환한다.


2) Bottom-up method

  • subproblem 들의 size를 기준으로 정렬한 후 가장 작은 문제부터 하나씩 해결해간다.
  • 추가되는 subprobelm을 만날 경우에는 이미 그보다 작은 문제들의 optimal solution들을 가지고 있기 때문에 바로 가져다 쓸 수 있다. 그러므로 이 경우에는 계산되어 있는지 아닌지를 점검할 필요가 없다.
  • 모든 계산은 단 한번씩만 이루어지며, 원하는 값에 도달하면 종료한다.


일반적으로는 Bottom-up 방식을 많이 사용한다.  Top-down은 재귀에 의한 오버헤드가 발생할 수 있기 때문이다. 하지만 모든 sub problem에 대해 다 계산할 필요가 없는 경우라면 Top-down이 낫다.


Software Security Engineer

CPUU 님의 창작활동을 응원하고 싶으세요?

댓글

SNS 계정으로 간편하게 로그인하고 댓글을 남겨주세요.