[Algorithm] 동적 계획법 (Dynamic Programming)

1. 개요

동적 계획법 (Dynamic Programming) (이하 DP) 은 문제를 여러 작은 문제들로 쪼개어 해당 문제를 해결하는 방식을 의미한다.

DP를 적용하기 전, 다음의 경우를 만족하는가를 파악할 필요가 있다.

문제를 더 작은 문제로 쪼갤 수 있는가
이전에 구한 해를 재사용 할 수 있는가

2. 의의

DP는 기본적으로 알고리즘을 최적화하기 위해 사용한다.

3. 조건

DP를 사용하기 위해서는 다음의 조건을 만족하여야 한다.

DP 의 적용 조건

1. Overlapping Subproblems (중복 하위 문제)
2. Optimal Substructure (최적 하위 구조)

3.1. Overlapping Subproblems (중복 하위 문제)

DP는 하위 문제 (Subproblems) 에서 중복 (Overlap) 이 발생하지 말아야 한다.

하위 문제에서 중복이 발생할 경우, 시간복잡도가 증가한다.

분할정복 (Divide & Conquer)과의 차이점

분할정복 (Divide & Conquer) 은 주어진 문제를 작은 하위 문제로 최대한 나눈 후(Divide), 하위 문제를 해결(Conquer)하면서, 합병(Merge) 해나가는 방식을 의미한다.

언뜻 보면 DP와 다를 게 없어 보이지만, 하위 문제에서 반복이 발생할 경우, 성능 면에서 큰 차이를 보인다.

• 분할정복 은 작은 문제를 해결하는 계산이 반복적으로 이루어져 처리 속도가 늘어날 수 있지만,
• DP 는 메모이제이션(Memoization) 기법을 통해 불필요한 계산을 최소화 할 수 있다.

* 대체적으로 분할정복을 구현하기 위해 재귀 (Recursive) 알고리즘 이 많이 사용되는 편이다.

예시) 피보나치 수열

분할정복 이용

def fibo_dq(n):
  if n < 2: return n
  return fibo_dq(n - 1) + fibo_dq(n - 2)

• 피보나치 수열의 점화식 $f(n) = f(n - 1) + f(n - 2)$ 에 맞게 재귀를 사용하여 코드를 구성하였다.
• 예를 들어 fibo_dq(4) 을 구하는 경우를 살펴보자.
  * 편의 상 fibo_dq() 를 f() 로 표현한다.
  • f(4) = f(3) + f(2) 이다.
  • f(4) 값을 구하려면 f(3) 와 f(2) 값이 필요하다.
  • f(3) 값을 구하려면 f(2) 와 f(1) 값이 필요하다.
  • 이때, f(3) 값을 구할 때 f(2) 값을 이미 구했지만, 다시 한 번 f(2) 값을 구해야 하므로 하위 문제의 중복이 발생한다.

DP 이용

def fibo_dp(n, memo = {}):
  if n in memo: return memo[n]
  if n < 2: memo[n] = n; return n
  memo[n] = fibo_dp(n - 1, memo) + fibo_dp(n - 2, memo)
  return memo[n]

• memo 라는 Dictionary 자료형 변수를 추가하여, 기존에 해결한 하위 문제에 대해서 불필요한 재연산이 이루어지지 않도록 코드를 구성하였다.
• 한 번 연산이 이루어져 도출된 값은 memo 에 저장된다. cache 역할
• 이러한 과정을 메모이제이션 (Memoization) 이라고 부른다.

성능 비교

import time

s = time.time()
print('fibo_dq(50) =', fibo_dq(50))
e = time.time()

print('%.7f' % (e - s), 's')

s = time.time()
print('fibo_dp(50) =', fibo_dp(50))
e = time.time()

print('%.7f' % (e - s), 's')

자 이제 fibo_dq() 와 fibo_dp() 의 성능을 비교해보자.

결과 출력은 다음과 같다.

fibo_dq(50) = 12586269025
2517.4534652 s
fibo_dp(50) = 12586269025
0.0001023 s

분할정복 이 적용된 fibo_dq() 의 경우 50번째 피보나치 수를 계산하는데 2,517초 (약 42분)가 걸렸고, DP 가 적용된 fibo_dp() 의 경우 0.0001초 (약 0.1밀리초)가 걸렸다.

분할정복 알고리즘이 DP 알고리즘의 약 2500만배나 더 오래 걸린 것이다.

위 결과에서 알 수 있듯이 두 알고리즘은 상당한 성능 차이가 발생한다는 것을 확인할 수 있다.

시간 복잡도

알고리즘	시간복잡도
분할정복	$O(n^2)$
DP	$O(n)$

3.2. Optimal Substructure (최적 하위 구조)

DP 는 하위 문제의 최적의 해 (Optimal Solution) 를 통해 전체 문제의 최적의 해를 구할 수 있어야 한다.

예시) 최적 경로 구하기

구역 $A$, $B$, $C$ 에 대해 $A$ 구역에서 $C$ 구역으로 가는 모든 경로 중 가장 최적의 경로를 찾아보자.
* 경로가 최적이다는 것은 "가장 적은 시간이 걸림"이나, "가장 거리가 짧음" 등 설정하기 나름이다.

$A$ 구역에서 $C$ 구역으로 바로(Directly)가는 경로가 없고 항상 $B$ 구역을 경유해야 한다고 가정할 때,

$A$ 구역에서 $C$ 구역으로 가는 최적의 경로를 찾는 문제는 다음의 두 하위 문제로 나뉠 수 있다.

1. $A$ 구역에서 $B$ 구역으로 가는 최적의 경로를 찾는 문제
2. $B$ 구역에서 $C$ 구역으로 가는 최적의 경로를 찾는 문제

위 하위 문제 1, 2 에서 각각 구한 최적의 경로를 통해 $A$ 구역에서 $C$ 구역으로 가는 최적의 경로를 찾을 수 있다.

가령, 서울 에서 대전 을 거쳐 부산 을 간다고 할 때, 서울 에서 대전 으로 가는 최적 경로와 대전 에서 부산 으로 가는 최적 경로를 선택해야 비로소 서울 에서 부산 으로 가는 최적 경로를 이용할 수 있다.

4. 구현

DP 는 다음의 두 가지 방식으로 구현할 수 있다.

DP 구현방식

1. Top-down 방식
2. Bottom-up 방식

4.1. Top-down 방식

상위 문제의 해를 구하기 위해 하위 문제를 호출하는 방식이다.

한마디로 최상층(Top)부터 내려가는(Down) 방식이다.

주로 재귀(Recursion)가 사용된다.

4.2. Bottom-up 방식

가장 하위의 문제의 해를 바탕으로 최종적으로 전체 문제의 해를 구하는 방식이다.

한마디로 최하층(Bottom)부터 올라오는(Up) 방식이다.

주로 반복문(Iteration)이 사용된다.

4.3. 비교

예시) 피보나치 구현

Top-down 으로 구현

def fibo_td(n, memo = {}):
  if n in memo: return memo[n]
  if n < 2: memo[n] = n; return n
  memo[n] = fibo_td(n - 1, memo) + fibo_td(n - 2, memo)
  return memo[n]

위 코드는 이미 위에서 소개한 피보나치 DP 구현 방식이다.

메모이제이션(Memoization) 기법이 사용되었으며, 재귀를 이용한 Top-down 방식이다.

Bottom-up 으로 구현

def fibo_bu(n, memo = [0, 1]):
  if n < 2: return memo[n]
  for i in range(n): 
    memo.append(memo[i + 1] + memo[i])
  return memo[n]

메모이제이션(Memoization) 기법이 사용되었으며, 반복문을 이용한 Bottom-up 방식이다.

4.4. 선택

어떠한 방식을 선택하여야 하는가에 대한 정답은 없다. 문제에 따라 구현에 대한 난이도가 다를 수 있으므로, 두 가지 방식 중 적절한 방식을 채택하여야 한다.

5. 적용

특정 문제를 해결하려고 할 때, DP 를 적용하기 위해서는 보통 다음의 절차를 따른다.

DP 적용 절차

1. DP 적용 가능 여부 파악
2. 변수 파악
3. 관계식 설정
4. 메모이제이션 기법 활용
5. 기저상태^* 파악  
6. 구현
   * 기저상태: 최하위 문제의 상태

5.1. DP 적용 가능 여부 파악

상위의 문제가 하위의 문제로 쪼개질 수 있는지 파악하는 것이 중요하다.

또한, 하위 문제가 중복되고, 최적의 하위 구조를 갖는지 살펴보아야 한다.

피보나치의 경우, $n$번째 피보나치 수는 보다 앞선 두 피보나치의 수의 합으로 표현할 수 있으므로 상위의 문제를 하위의 문제로 쪼갤 수 있다.

5.2. 변수 파악

문제의 가변값을 파악해야 한다.

피보나치의 경우, 수열의 $n$번째 수를 구해야 하므로 변수는 $n$ 이라고 할 수 있다.

5.3. 관계식 설정

변수에 따른 상위 문제와 하위 문제 간 관계식을 설정해야 한다.

(상위 문제) = (하위 문제들의 연산)

피보나치의 경우, $f(n) = f(n-1) + f(n-2)$의 관계식(점화식)을 세울 수 있다.

5.4. 메모이제이션 기법 활용

하위 문제의 중복 연산을 최소화하기 위하여 메모이제이션 기법을 활용해야 한다.

이미 구한 하위 문제의 해들을 기록한 뒤, 동일한 하위 문제가 호출될 때 재연산하지 않고 기록된 해를 찾아 사용한다.

5.5. 기저상태 파악

최하위 문제 상태(기저상태)를 파악해야 한다.

최하위 문제는 대부분 관계식(점화식)의 초기조건에 해당한다.

피보나치의 경우, $f(0) = 0, f(1) = 1$ 가 이에 해당한다.

5.6. 구현

Top-down 방식과 Bottom-up 방식 중 하나를 선택하여 구현한다.

---

관련 포스팅

• [Problem] 배낭 문제 (Knapsack Problem)
• [Baekjoon] 2096번 내려가기 G5

참고자료

• 알고리즘 - Dynamic Programming(동적 계획법)
• Top-down 방식과 Bottom-up 방식