동적 계획법(Dynamic Programming)

동적 계획법은 정말 가장 많이 대회에서 출제되는 문제 유형임과 동시에 반드시 알아야만 하는 내용이기도 하다. 명확하게 '이것이 동적 계획법 문제다' 라고 분류하기 보다는 앞선 브루트 포스나 그리디 알고리즘과 같이 문제를 풀어나가는 하나의 방법으로 접근하는 것이 올바르다고 생각한다.

 

백준에 분류된 문제에서도 dp가 압도적인 문제의 양을 차지한다. 그리디 겁나 안풀었네...

동적 계획법 역시 큰 문제를 작은 문제로 나누는 것에서 출발한다. 지금까지의 내용을 정리하면 아래와 같다.

1. 브루트 포스(Brute Force): 작은 문제 하나하나 다 살펴볼거야!
2. 탐욕법(Greedy): 작은 문제마다 답을 선택해 버릴거야!

그렇다면 동적 계획법의 메커니즘은 어떤 것일까?

다른 작은 문제에서 만들어 놓은 값을 다시 쓸거야!

즉, 작은 문제들로 분류하여 연산을 하는 과정에서 같은 연산을 반복적으로 수행해야 한다면 이를 캐싱(caching)하여, 두 번 이상 연산하지 않도록 처리하는 것이다. 두 번 이상 계산되는 부분 문제는 '중복되는 부분 문제(overlapping subproblems)'라고 한다.

 

사실 DP는 실무와도 가장 밀접한 연관성이 있는 알고리즘 테크닉이라고 생각이 든다. 우리가 특정 비즈니스 로직을 구현함에 있어서 하나의 function이 말그대로 하나의 기능만을 수행하게끔 모듈화 작업을 해나갈텐데, 이를 몸에 내재하기에 가장 좋은 테크닉이 아닐까 생각하기도 한다.

 

아무튼 각설하고 이 DP를 다룰 때 흔히 예제로 언급되는 문제는 '이항계수(binomial coefficient) 계산(파스칼의 삼각형)'과  '피보나치(fibonacci) 수열'이다. 

 

이항계수 점화식(출처: https://codecrucks.com/binomial-coefficient-using-dynamic-programming/)

만약 우리가 C(6, 4) 을 구해야 하는 상황이라고 가정해보자. 이는 이항계수 점화식에 따라 C(5, 3) + C(5, 4)을 구하면 되는데, 큰 문제가 작은 문제로 쪼개지고 있음을 확인할 수 있을 것이다. 그럼 먼저 재귀 호출을 통해 무식하게 풀어보자.

public int binomial(int n, int r) {
  if (r == 0 || n == r) return 1;
  return binomial(n - 1, r - 1) + binomial(n - 1, r);
}

문제는 풀 수 있겠으나, n과 r이 증가하면 할수록 binomial function이 수행해야 할 연산의 수는 늘어날 것이고 stackoverflow를 뱉어 버릴 것이다. 이유는 아래 그래프를 살펴보자.

 

출처: https://codecrucks.com/binomial-coefficient-using-dynamic-programming/

트리의 상위 노드에 (5, 3)과 (5, 4)만 보더라도 두 이항계수를 연산하기 위해서는 (4, 3)을 공통적으로 필요로 하는 것을 확인할 수 있다. 즉, 이미 한 번 연산을 마쳤다 하더라도 재귀로 푼 위 코드의 경우 매번 같은 연산을 반복적으로 수행하게 되는 것이다.

 

앞서 언급한 바와 같이 우리는 이제 '만들어 놓은 값을 다시 쓸 것'이고 이를 메모이제이션(memoization)이라고 부른다. 그럼 다음 코드를 살펴보자.

// -1로 초기화 해둔 2차원 배열
int[][] memo = new int[10][10];

public int binomial(int n, int r) {
  if (r == 0 || n == r) return 1;
  if (memo[n][r] != -1) return memo[n][r];
  return memo[n][r] = binomial(n - 1, r - 1) + binomial(n - 1, r);
}

이미 연산된 값을 저장해 놓음에 따라, 모든 부분 문제들은 단 한 번만 연산된다는 보장을 할 수 있게 된다. 따라서 binomial 함수를 호출해 Stack에 쌓이는 횟수가 압도적으로 감소하는 것을 확인할 수 있다.

 

이항계수 C(N, N/2)를 계산한다고 가정했을 때, 재귀와 DP의 함수 호출 수는 아래와 같다.

(출처: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략 1권_동적계획법_210p_구종만 지음)

n	2	3	4	5	6	...	18	19
recursive	3	5	11	19	39	...	97239	184755
dp	3	5	8	11	15	...	99	109

추가적으로 이 메모이제이션을 진행하는 방식에는 크게 'TOP-DOWN' 방식과 'BOTTOM-UP' 방식으로 나뉘기도 한다. 먼저 탑다운의 경우 예제로 풀이한 이항계수 문제와 같이 큰 문제에서 출발하여 부분 문제들을 메모이제이션 해 나가는 방식이며, 바텀업의 경우 부분 문제들의 해답을 만들어가면서 최종적인 문제의 해를 구하는 방식이라고 볼 수 있다. 이항계수의 경우, 바텀업으로 풀이한다면 파스칼의 삼각형을 그려나가면서 풀이할 수 있겠다.

 

마지막으로 메모이제이션을 활용한 이항계수 문제 풀이의 시간복잡도는 아래와 같다.

출처: https://codecrucks.com/binomial-coefficient-using-dynamic-programming/

 

---

정리

• 동적 계획법은 큰 문제를 부분 문제로 분할하여, 각 부분 문제들을 단 한 번만 연산되게 처리하는 것이다.
• 탑다운 혹은 바텀업 메모이제이션을 채택하여 부분 문제들에 대한 답을 미리 저장해둔다.

---

참고문제

1. Bronze 1 - 알고리즘 수업 - 피보나치 수 1

24416번: 알고리즘 수업 - 피보나치 수 1

2. Silver 5 - 파스칼의 삼각형

16395번: 파스칼의 삼각형

3. Silver 2 - 가장 긴 증가하는 부분 수열

11053번: 가장 긴 증가하는 부분 수열

---

Reference

1.  프로그래밍 대회에서 배우는 알고리즘 문제해결전략 1권_동적계획법_207p_구종만 지음

2. https://codecrucks.com/binomial-coefficient-using-dynamic-programming/