다이나믹 프로그래밍 이론

다이나믹 프로그래밍이란 일반적인 알고리즘 문제를 더 빠르게 해결하기 위해 생긴 기법이다. 다이나믹 프로그래밍은 다음 두 가지 조건을 만족할 때 사용 가능하다.

 

1. 최적 부분 구조
   • 큰 문제를 작은 문제로 나누고, 작은 문제들의 답을 모아 큰 문제를 해결할 수 있다.
2. 중복되는 부분 문제
   • 동일한 작은 문제들이 반복된다.

 

이렇게 얘기한다면 크게 와닿지 않는다. 재귀함수의 기본인 피보나치 수열을 예시로 들어보겠다.

def fibo(n):
    if (n == 1 or n == 2):
        return 1
    return (fibo(n - 1) + fibo(n - 2))

피보나치 수열 함수는 다음과 같이 작성할 수 있다. 이 부분을 잘 모르겠다면 재귀함수를 공부해야한다.

피보나치 수열의 동작 구조

위의 함수를 이용해 f(6)을 구하고자 한다면 그 함수는 f(5), f(4)를 호출하고, 각각의 함수는 f(4), f(3), f(3), f(2)를 호출한다. 또 그 함수들은 아래 함수들을 호출한다. 이는 큰 문제가 작은 문제로 나뉘어진다는 의미이다. f(5)와 f(4)의 결과를 이용해 f(6)이라는 큰 문제를 해결할 수 있다. 이는 아까 말했던 조건1, 최적 부분 구조에 해당한다.

자세히 보면 파란색 칠해진 f(2)가 5번이나 등장한다. 만약 f(7)에서는 8번, f(8)에서는 13번 등장하게 될 것이다. 또한 이는 기하급수적으로 증가하게 될 것이다. 이렇듯, 같은 문제를 계속해서 반복 반복한다. 이는 조건 2, 중복되는 부분 문제에 해당한다.

 

다이나믹 프로그래밍이란?

그렇다면 다이나믹 프로그래밍이란 무엇일까? 이를 어떻게 더 빠르게 만들 수 있는 것일까?

다이나믹 프로그래밍은 메모리를 적절히 사용하여 작은 문제들의 결과들을 저장해두고, 반복되어 해결해야 할 때 저장된 결과를 꺼내어 사용하는것이다. 예를 들어 위의 문제에서 결과값을 저장해 둘 리스트를 만들고, f(1), f(2), f(3), ... 를 해결할 때마다 그 리스트에 결과를 저장하는 것이다. 그렇게 한다면 반복해서 해결할 필요 없이 한 번만 풀고 그 결과를 사용하기만 하면 된다. 아래의 코드를 보자.

def fibo(n):
    # 만약 dp에 저장된 값이 있다면 그 값 리턴
    if (dp[n] != 0):
        return dp[n]
    # 값이 없다면 그 값을 저장해주고 리턴
    dp[n] = fibo(n - 1) + fibo(n - 2)
    return dp[n]

n = int(input())
# fibo(1), fibo(2)는 1. 미리 저장
dp = [0, 1, 1] + [0] * (n - 2)
print(fibo(n))

fibo(10)의 dp를 실행시켜본다면 다음과 같은 결과가 나온다.

---

위의 코드를 실행하게 되면 실제로 계산을 하게 되는 함수는 색칠한 함수이다. 나머지 점선으로 둘러싸인 함수들에서는 그냥 dp리스트에서 꺼내어 사용하기만 할 뿐이다. 여기 꺼내어 사용하는 부분에서는 리스트 인덱스에 접근하는 것 이므로 시간복잡도가 O(1)이다.

실제로 호출되는 함수

실제로 호출되는 함수를 구조화시키면 위의 그림과 같다. 오른쪽의 점선 f(3)에서는 dp리스트에서 꺼내어 사용하기 때문에 그 아래의 함수는 호출하지 않는다. 그래서 시간을 엄청나게 단축시킬 수 있다.

원래 피보나치 수열 함수는 한 함수당 2개의 함수를 재귀적으로 호출하기 때문에 시간복잡도가 O(2^N)이다.

반면에 다이나믹 프로그래밍을 이용하여 작성한 코드는 2개의 함수를 호출하긴 해도, 그 중 한 함수에서만 연산이 실행되고, 남은 한 함수에서는 시간복잡도가 O(1)이므로 결국 한 개의 함수만 호출한 것과 같은 시간이 걸린다. 즉 이 함수의 시간복잡도는 O(N)이다.

---

다이나믹 프로그래밍에는 탑다운(하향식)방식과 보텀업(상향식)방식이 있다.

탑다운 방식은 메모이제이션 기법을 사용한다. 메모이제이션 기법이란 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다. 위에서 아래 방향으로 더 작은 단위의 재귀함수를 호출했을 때 만약 그 결과가 이미 구해졌다면, 메모리 공간에서 꺼내어 사용한다. 위에 작성된 코드가 탑다운 방식이다.

다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다. 보텀업 방식으로 작성된 아래 코드를 보자.

# 100번째 피보나치 수를 구하기 위한 dp테이블
dp = [0] * 101

# 첫 번째, 두 번째 수 저장
dp[1] = 1
dp[2] = 2

n = 100

# 보텀업 방식으로 계속해서 다음 수를 구하고 저장.
for i in range(3, n + 1):
	dp[i] = dp[i - 1] + dp[i - 2]

print(dp[n])

---

마지막으로 다이나믹 프로그래밍과 분할 정복의 차이에 대해 배워보자.

다이나믹 프로그래밍은  첫째, 최적 부분 구조를 가질 때, 둘째, 부분 문제가 중복될 때 사용 가능한 알고리즘이다. 그러나 분할 정복에서는 이 조건에서 차이가 있다. 최적 부분 구조, 즉 큰 문제를 작은 문제로 나누어 해결할 수 있어야 하는 것은 동일하지만, 분할정복은 부분 문제가 중복될 때 사용하는 것은 아니다. 그냥 계속해서 작은 문제로 쪼개어 구하는 것이 분할 정복이다.

아직 분할 정복은 공부하지 않아서 '아 이런게 있구나'정도만 이해하고 넘어가겠다.