[알고리즘] 동적 계획법(Dynamic Programming)

1. DP란?

동적 계획법은 간단히 말하면 전체 문제 혹은 큰 문제를 한 번에 해결하는 것이 아니라 작은 부분 문제들로 나눠서 해결하고 이것들을 활용해 전체 문제를 해결하는 방법이다. 말만 들어보면 다른 알고리즘인 분할정복과 유사하게 보인다. 다만 DP를 효율적으로 사용하기 위해서는 2가지 조건을 만족해야한다.

• 큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복해서 등장해야 한다.(중복 부분 문제)
• 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구성할 수 있어야 한다.(최적 부분 구조)

분할정복과 DP 모두 부분 문제로 나눠서 해결한 뒤 원래 문제의 해답을 얻지만, 분할정복은 반복되는 작은 문제가 없다. 반면에 위에서 살펴본 것처럼 DP는 반복되는 작은 문제가 있을 때 사용하는 알고리즘이다. 그렇기 때문에 분할 정복은 정렬 알고리즘에서 많이 활용되고, DP는 다익스트라 같이 각 노드의 최단 거리를 계산해서 종합적으로 구하는 최단 경로 문제 등에 활용된다.

사실 말로만 들었을 때는 DP가 어떤 방식으로 풀리는건지 잘 모르겠고, 대표적인 DP의 예제인 피보나치를 보면서 이해해보자.

---

2. 피보나치 수열

피보나치 수는 1, 2번 항이 1이며 그 뒤의 항들은 직전 두 개의 항의 합인 수열을 의미한다. 따라서 1,1,2,3,5,8,13... 과 같이 값이 나열되는데, 대표적인 DP의 개념으로 풀 수 있는 문제이다. 위에서 살펴본 조건을 기준으로 보자.

            F(5)
           /    \
        F(4)    F(3)
       /    \    /    \
    F(3)  F(2) F(2)  F(1)
   /   \   / \
F(2) F(1)F(1) F(0)
 / \
F(1) F(0)

• 중복 부분 문제 : 동일한 작은 문제의 반복
  • 두 개의 항의 합을 반복해서 구해나간다. 위 그림처럼 f(5)를 구한다고 가정하면 지속적으로 f(3), f(2), f(1) 같은 구조가 반복된다. 그렇다면 계산했던 값을 활용해서 큰 문제를 해결하는 구조를 만들 수 있을거라 추측가능하다.
• 최적 부분 구조 : 작은 문제의 결과값을 통해 전체 문제의 결과를 구할 수 있다.
  • 각 항의 합을 각각 계산한 후 그 값을 조합해서 최종적으로 F(N)을 계산한다. 
• 부분 문제의 해결 결과를 저장하고 재사용한다.(메모이제이션)

위와 같은 조건을 만족하는 것을 확인했을 때 코드로 구현해보되, 가장 간단한 과정부터 차례대로 구현해보자.

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

위 코드는 단순히 피보나치 수열을 재귀를 이용해서 구현했다. 다만 DP 형태로 풀었다고 보기에 아쉬운 점은 중복이 발생했을 때를 고려하지 않고 단순 반복하기 때문에 값이 커질수록 부하가 커진다.

memo = {}
def fibonacci_mem(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n in memo:
        return memo[n]
    # 결과값 기록하기!
    memo[n] = fibonacci_mem(n - 1) + fibonacci_mem(n - 2)
    return memo[n]

이번엔 메모이제이션을 활용해서 기존에 구했던 값이 있다면 추가로 구하지 않고 기존 값을 기억해서 재활용하는 방식이다. 반복 과정을 줄이기 때문에 메모이제이션을 활용하지 않았던 기존 코드보다 부하가 굉장히 많이 줄어든다. 

---

3. 구현 방법

DP에서는 구현 방식에 따라 크게 2가지의 유형이 있는데, 각각의 방식을 위에서 만들었던 피보나치 수열을 기준을 알아보자.

3-1 Top-Down

분할 정복과 비슷한 구조를 가지고 있는 구현 방법으로, 아래에서 부터 차례대로 계산을 수행하고 누적시켜 전체의 큰 문제를 해결하는 방식이다. DP 문제를 해결하는 방식 중에 재귀 함수를 활용한다면 이 방식이라고 생각하면 된다. 함수를 반복적으로 호출해서 가능한 작은 문제를 모두 해결하고 나서야 처음 호출했던 함수를 처리하기 때문에 구조적으로 Top-Down 방식을 따른다.

3-2 Bottom-Up

말 그대로 아래에서부터 계산을 수행하고 누적시켜 전체 큰 문제를 해결하는 방식이다. Bottom-Up에서는 메모이제이션을 테이블을 채워나간다는 뜻에서 Tabulation이라고 부르기도 한다. 예를 들어 1차원의 배열을 만들고 n까지 값을 구하는게 목적이라면 dp[0] ~ dp[n]까지 점화식으로 결과를 내서 그 값을 누적해나가는 방식이다. 위에서 설명한 피보나치 수열을 이 방식으로 구하면 다음과 같다.

def fibonacci_dp(n):
    fib = [0, 1]
    for i in range(2, n + 1):
        fib.append(fib[i - 1] + fib[i - 2])
    return fib[n]

쉽게 말해 2가지 방식을 간단하게 이해한다면 이렇게 이해하면 된다.

• Top-Down(Memoization) : 재귀함수를 활용해서 풀기
• Bottom-Up(Tabulation) : 반복문을 활용해서 풀기

---

4. 마무리

사실 DP는 이론적으로 이해하는건 어렵지 않지만 그걸 문제에 적용하는게 굉장히 어려운 알고리즘이다. 그래도 다른 글들에서 설명하고 있는 DP를 사용하는 방법을 보면 다음과 같다.

1. DP로 풀 수 있는 문제인지 확인한다.
   1. 위에서 쓴 조건들이 충족되는 문제인지 한번 확인한다.
   2. 보통 특정 데이터 내 최대, 최소를 구하거나 특정 조건의 데이터를 센다거나 확률 등의 계산이면 DP로 풀 수 있다.
2. 문제의 변수를 파악한다.
   1. 구하고자 하는게 무엇인지를 확인해야한다. 피보나치 라면 n번째 숫자를 구하는 것이므로 n이 곧 변수다.
3. 변수 간 관계식을 만든다.
   1. 이를 곧 점화식이라고 부르며 반복과 재귀를 통해 풀 수 있는 식을 의미한다. 피보나치면 f(n) = f(n-1) + f(n-2)
4. 메모이제이션(타뷸레이션) 활용
   1. 변수의 값에 따른 결과를 저장하고 재사용해야한다.
5. 기저 상태 확인
   1. 가장 작은 문제의 상태를 알아야한다. 피보나치 수열의 경우 0과 1이 제일 작은 문제이며 이 2개의 값이 나머지 전체의 값을 결정한다.

방법론이야 이렇지만 결국 많은 문제를 풀면서 방향을 확인해보는 수밖에 없다. 힘내자.