Post

동적 계획법

Posted
By Park "ShapeLayer" Jonghyeon
13 min read
동적 계획법

도입

동적 계획법(DP; Dynamic Programming)은 계산한 값을 임시로 기록해두었다가, 이후에 다른 계산에 활용하는 최적화 전략이다.

동적 계획법을 적용하는 전형적인 방법이나 시나리오는 있지만 정해진 구현이 있는 것은 아니므로, 특정한 알고리즘보다는 문제해결에 사용할 수 있는 패러다임에 가깝다. 동적 계획법에서 사용하는 전략들은 분할 정복과 메모이제이션으로 따로 불리며, 백준 온라인 저지에서는 분할 정복을 별개의 알고리즘 유형으로 두고 있기도 하다.

(국방부 장관이었던) 윌슨은 ‘연구’라는 단어에 병적인 두려움과 증오심을 가지고 있었다. (…) 그렇다면 ‘수학’이라는 용어에 대해 그가 어떻게 느꼈을지 상상할 수 있을 것이다. (…) 나는 RAND Corporation에서 실제로는 수학을 하고 있다는 사실을 그와 공군으로부터 숨길 필요가 있었다. (…) ‘동적’이라는 단어를 경멸적인 의미로 사용하는 것은 불가능하다. 경멸적인 의미가 담긴 조합을 생각해보라. 불가능하다.

Bellman, Richard. Eye of the Hurricane. World Scientific, 1984.

원어 명칭인 Dynamic Programming도 실제와는 거리가 먼 이름이다. 리처드 벨먼이 의도적으로 실제와는 거리가 멀지만 흥미를 끌 수 있는 어휘의 조합을 선택하여, 자금을 지원받을 수 있게 정부 기관을 유도했기 때문이다.

전략

동적 계획법은 분할 정복, 메모이제이션 두 전략을 주로 사용한다.

우선 문제의 전체 범위를 반복 가능한 작은 문제들로 나눈다. 최대한 작은 규모로 나누면 동일한 문제들이 중복되는 경우가 발생한다. 중복되는 문제들의 처리 결과를 임시로 저장해두었다가, 같은 처리 결과가 필요할 때 새로 계산하는 것이 아니라 저장한 값을 인출하여 처리한다.

전반부에서 “반복 가능한 작은 문제들로 나누는 것”이 분할 정복, 후반부에서 “결과를 임시로 저장해두었다가, 새로 계산하지 않고 저장한 값을 사용하는 것”이 메모이제이션이다.

다만 동적 계획법에서는 분할해낸 작은 문제들이 서로 중복된 값을 요구하도록 충분히 작아야 하므로, 일반적으로는 널리 사용되는 분할 정복보다 문제를 더 잘게 자르는 경향이 있다.

동적 계획법의 구현

피보나치 수

백준 온라인 저지 2747번: 피보나치 수, 2748번: 피보나치 수 2 2749번: 피보나치 수 3 10826번: 피보나치 수 4

동적 계획법의 예시로서 자주 인용되는 피보나치 수 문제이다. 피보나치 수 $F_n$은 $n$이 그 어떤 값이라고 하더라도, $F_0$과 $F_1$에서부터 계산된다. $F_n$을 구하는 모든 문제 상황은 $F_0$과 $F_1$의 덧셈이라는 작은 문제로 대체될 수 있다.

\[F_n = \begin{cases} F_0 = 0 \\ F_1 = 1 \\ F_{n-1} + F_{n-2} & (n > 2) \end{cases}\]

구체적으로, $F_4$를 구하는 문제 상황은 아래의 순서대로 분할된다.

\[F_4 = F_3 + F_2 \\\\ = (F_2 + F_1) + (F_1 + F_0) \\\\ = ((F_1 + F_0) + F_1) + (F_1 + F_0)\]

$n=4$인 상황에서 $F_0$과 $F_1$은 각각 2회, 3회 참조되었고, $F_1 + F_0$ 도 2회 계산되었다. 피보나치 수는 $n$이 커질수록 이러한 계산이 기하급수적으로 증가하게 된다. 같은 계산을 충분히 큰 횟수만큼 반복하는 것보다, 처음 계산할 때 계산 결과를 임시 저장하여 필요할 때마다 불러오는 것이 더 적은 컴퓨팅 비용을 요구한다.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
  def __call__(self, n: int) -> int:
    if n == 0:
      return 0
    if n == 1:
      return 1

    return self(n - 1) + self(n - 2)

def compute(N: int) -> int:
  sol = Solution()
  return sol(N)

피보나치 수를 계산하는 기본적인 구현은 위와 같다. Solution 구현체는 피보나치를 분할 정복한다. $F_n$을 계산하기 위해 자신보다 더 작은 피보나치 수를 계산하여 합한다.

하지만 이 구현은 가장 난이도가 낮은 <2747번: 피보나치 수> 문제도 통과하지 못한다. 이 문제에서의 최대값인 $F_{55}$의 계산에 __call__(0)을 약 8백억(86,267,571,272)회, __call__(1)을 1천3백억(139,583,862,445)회 호출하고, __call__(1) + __call__(0)을 그에 준하는 수준의 횟수로 반복하기 때문에 매우 오랜 시간이 소요된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
  def __init__(self, N: int):
    self.dp = [-1 for _i in range(N + 1)]
    self.dp[0] = 0
    self.dp[1] = 1

  def __call__(self, n: int) -> int:
    if self.dp[n] != -1:
      return self.dp[n]
        
    self.dp[n] = self(n - 1) + self(n - 2)
    return self.dp[n]

def compute(N: int) -> int:
  sol = Solution(N)
  return sol(N)

위의 코드는 <2747번: 피보나치 수>를 포함하여 <2748번: 피보나치 수 2>를 통과한다. 이 구현체는 메모이제이션도 구현하였다. $F_n$의 $n$에 대해서 Solution.dp[n] 속성에 $F_n$ 값을 캐싱한다.

만약 $n$에 대해서 Solution.dp[n]이 캐싱되지 않았다면, Solution.dp[n - 1] 값과 Solution.dp[n - 2]값을 가져와 Solution.dp[n] 값을 계산하고 캐싱한다. 모든 $F_n$은 단 1회만 계산하고 임시 저장한다.

백준 온라인 저지, 9461번: 파도반 수열

동적 계획법에서는 대부분의 상황에서 메모이제이션할 분할 정복 대상을 점화식으로 표현할 수 있다. 사실 동적 계획법이 전체 문제를 표현할 수 있는 반복 과정을 찾는 것을 요구하므로 당연한 점이다.

그래서 동적 계획법만을 사용하는 것이 출제 의도인 알고리즘 문제들은, 이 점화식을 숨겨놓고 찾아내는 것을 목표로 하는 것이 많다.

충분한 관찰이 동반된다면, 논리적인 과정을 건너뛰고 귀납적으로 점화식을 찾을 수도 있다. 인터넷에서 동적 계획법 문제의 풀이를 찾아보면, 몇 개 예시를 계산해보고 식을 설정하는 사례가 있다.

백준 온라인 저지, 9461번: 파도반 수열

이 문제는 파도반 수열(Padovan sequence)의 정의를 찾아서 구현하는 것을 목표로 한다. 파도반 수열은 정수론에서는 상대적으로 널리 알려진 수열이지만, 처음 접하는 사람들은 이 수열의 정의에 대해 논리적인 근거를 찾아내기 어렵다.

주어진 정의에 맞게 파도반 수열을 나열하면 다음과 같다:

$n$$P_n$$n$$P_n$$n$$P_n$
11631112
21741216
31851321
42971428
521091537

시작 부분($n=1$)으로부터 떨어져 있는 $P_n$에서는 수에서 규칙을 찾을 수 있다.

\[P_n = P_{n - 2} + P_{n - 3}\]

수열에 따라서는 또 다른 식을 찾을 수도 있다. 파도반 수열도 오랜 연구를 거치면서 다양한 변형 수식이 등장했다.

\[P_n=P_{n - 1} + P_{n - 5}\] \[P_n=P_{n + 3} - P_{n + 1}\]

마무리

동적 계획법은 문제 상황을 재귀적으로 계산함으로써 해결할 수 있는 점화식, 다시 말해 관계식을 도출하여, 중간 계산 산출물을 캐싱하는 알고리즘 유형이다.

동적 계획법은 문제 자체의 난이도가 점화식의 난이도에 비례하는 경향이 있다. 동적 계획법 풀이를 요구하는 알고리즘 문제 해결 과제에서는, 일반적으로 메모이제이션보다는 관계식을 찾는 데 더 많은 노력이 요구된다.

파도반 수열 사례에서 보듯, 이러한 수열 유형들을 충분히 경험하고 직관이 쌓인 것이 아니라면, 개별 수열의 정의를 미리 알고 있지 않은 이상 첫 시도에 문제를 해결하는 것은 매우 어렵다.

때문에 많은 문제들 혹은 널리 알려진 다양한 수열들을 경험하거나, 정수론을 공부하는 형태로 직관과 경험을 쌓는 것이 권장된다. 소위 “양치기”로 유효하게 대응할 수 있다는 점에서 그리디 알고리즘 유형과 비슷한 방법으로 준비할 수 있다.

algorithm
ps baekjoon algorithm