동적 계획(Dynamic Programming, DP), Python

간단한 소개

다이나믹 프로그래밍이란 단순하게 말해서 이전에 생성한 값을 가져다가 쓰는 것을 의미한다.

 

예를 들어서 1과 2만을 가지고 N이라는 숫자를 만든다고 생각해보자. 이때 N이 3이라면 '1+1+1', '1+2', '2+1'이라는 경우의 수가 나올 것이다. N이 4라면 어떻게 될까. '1+1+1+1', '1+2+1', '2+1+1', '1+1+2', '2+2'이라는 경우의 수가 나온다. 이렇게 일일히 세줄 수도 있지만 N이 1억일 경우에는 그 연산의 횟수가 너무 커져 시간이 많이 걸린다. 바로 이럴 때 동적 계획을 이용하면 연산 횟수를 줄이면서 빠르게 문제를 해결할 수 있다.

 

위의 문제를 동적 계획으로 푸는 방법을 소개한다.

N = 1

'1' -> 1개

 

N =2

'1+1', '2' -> 2개

 

N = 3

'1+1+1',  '2+1', '1+2', -> 3개

여기서 주목할 점은 바로 각 경우의 수 맨 뒤에 있는 숫자이다. '1+1+1'에서 맨 뒤에 있는 숫자 1을 빼고 앞에 두 숫자를 더하면 2가 된다. 또한 '2+1'에서 맨 뒤에 있는 숫자 1을 뺀 나머지 숫자는 2이다(값이 하나이므로 더할 필요가 없다). '1+2'의 경우에는 맨 뒤의 숫자 2를 빼면 나머지 숫자는 1이 된다. 무언가 느껴지는 게 없다면 다음 숫자 4를 보도록 하자.

 

N=4

'1+1+1+1', '1+2+1', '2+1+1', '1+1+2', '2+2' -> 5개

먼저 맨 뒤 숫자가 1인 경우의 수는 '1+1+1+1', '1+2+1', '2+1+1'이 있다. 여기서 맨 뒤의 1을 빼고 나머지 숫자를 더하면(1+1+1=3, 1+2=3, 2+1=3) 전부 3이 되는 것을 알 수 있다. 즉, 저렇게 풀어서 쓰여 있지만 결국에는 '3+1'이 세 번 나온다는 것이다. 그렇다면 바로 위에서 구해 놓은 N이 3일 때의 경우의 수를 확인해보자.

N이 3일때 만들 수 있는 경우의 수는 '1+1+1', '2+1', '1+2'이고 N이 4일때 맨 마지막 숫자가 1인 경우의 수는 '(1+1+1)+1', '(2+1)+1', '(1+2)+1'이다. 바로 N이 3일때 만들 수 있는 경우의 수가 그대로 N이 4일때 1만 붙여서 사용됐다는 것을 알 수 있다.

 

마찬가지로 맨 마지막 수가 2일때를 확인해보면 '1+1+2', '2+2'이고 이는 '(1+1)+2', '(2)+2'로 볼 수 있다. 해당 경우의 수 중 가로를 친 부분은 2이기에 자연스럽게 N이 2일때의 경우의 수가 이용되고 있음을 알 수 있다.

 

그러므로 N이 4일때 1과 2로 만들 수 있는 경우의 수는 (4-1로 만들 수 있는 경우의 수) + (4-2로 만들 수 있는 경우의 수)가 되는 것이다. 이 식을 일반화시킨다면 (N-1의 경우의 수) + (N-2의 경우의 수)로 만들 수 있다. 때문에 이전에 만든 경우의 수를 알고 있다면 N의 값을 쉽게 구할 수 있다.

 

이렇게 동적 계획법을 이용해서 문제를 푸는 방법은 총 두 가지가 있다. 하나는 아래에서 위로 올라가는 Bottom-up방식이고 다른 하나는 위에서 아래로 내려가는 Top-down방식이다. 전자는 일반 반복문을 사용하고 후자는 재귀 함수를 이용한다.

바텀 업(Bottom-up)

내가 위에서 소개한 문제 풀이 방식이 바로 바텀 업 방식이다. N이 주어졌을 때 나는 문제를 N에서부터 접근하지 않고 1에서부터 접근했다. 맨 아래부터 시작해 목표 지점까지 도달하는 방식을 이용한 것이다. 즉, 이것이 아래에서부터 위로 올라가는 바텀 업 방식이다.

 

사실 나는 재귀를 풀 때 제일 먼저 바텀 업 방식을 생각한다. 제일 직관적이면서 점화식을 빠르게 생각할 수 있는 방법이기 때문이다 적어도 나는.

 

탑 다운(Top-down)

아래에서 위로 올라가는 바텀 업과 다르게 탑 다운은 위에서부터 아래로 내려간다. 이는 재귀 함수로 구현할 수 있다. 다이나믹 프로그래밍하면 무조건 나오는 문제 피보나치 수열을 보면서 이해해보자.

 

피보나치 수열이란 이전 두 수를 합해서 현재의 수를 만드는 수열이다. 점화식은 An = An-1 + An-2로  만들 수 있다. 재귀로 푼 코드를 보자면

dp = [0 for _ in range(10)]

def fib(n):

    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    elif dp[n] != 0:
    # 만일 이전에 계산한 값이 있으면 그 값을 이용한다.
    # 다이나믹 프로그래밍.
    	return dp[n]
    
    dp[n] = fib(n-1) + fib(n-2)

    return dp[n]

 

이렇게 원하는 숫자 n에서부터 -1과 -2만큼 내려가 0, 1, 2까지 도달한 다음에 차례대로 위로 올라가는 방식을 알 수 있다. 또한 dp[n]이 0이 아니라 이전에 계산한 값이 존재하면 굳이 계산하지 않고 이전에 구한 값을 이용해주는 것을 알 수 있다.

 

접근 방법

바텀 업 방식을 이용해서 내가 DP를 접근하는 방식을 설명하자면. 사실 나도 DP 문제 나오면 능숙하게 풀지는 못하는데... 흠흠.

 

1. 일단 Bottom-up 방식을 이용할 것이기에 제일 아래에 존재해야 할 수를 생각해준다.

2. 맨 아래 있어야 할 수가 정해지면 그 수들을 이용해서 만들 수 있는 다음 수를 생각한다.

3. 보통은 2에서 점화식이 잘 나오지 않기 때문에 2에서 생각한 수보다 더 큰 수들을 생각하면서 점화식을 완성한다. 이때는 종이와 팬을 가지고 경우의 수를 따져봐야 문제를 빠르고 정확하게 풀 수 있다.

4. 점화식이 구해지면 반복문을 이용하여 코드를 구현한다.

문제

https://www.acmicpc.net/workbook/view/7836

문제집: 좋은 DP문제들 (khanjhy)

참고로 말하자면 백준 9095는 '간단한 소개'에서 설명한 문제와 그 원리가 같다.