#17 동적 계획법(Dynamic Programming) 1 - 기본

 동적 계획법은 어떤 문제를 보다 쉽게 해결하기 위해 작은 문제로 나누어 해결하는 방식의 알고리즘이다.  마찬가지로 큰 문제를 분할하여 해결하는 분할 정복(Divide and Conquer) 알고리즘과의 차이는 분할 정복과는 달리 동적 계획법의 분할된 문제들끼리는 중복되는 부분이 존재한다는 것이다. 

 

1. 메모이제이션(Memoization)

 피보나치 수는 동적 계획법을 설명할 때 굉장히 자주 언급되는 문제이다. n번째 피보나치 수를 f(n) 이라고 할 때, f(n) = f(n-1) + f(n-2) 이다.  이에 따라 5 번째 피보나치 수를 구한다고 할 때, 과정을 트리형태로 나타내면 다음과 같은 형태가 된다.

그림 1

보다시피 같은 피보나치 수를 구하는 연산이 여러번 중복되어있다.  고작 f(5)를 구하는데도 이정도의 중복연산이 발생한다면 n이 좀더 커지면 어떻게 될지는 짐작이 갈 것이다.  이를 해결하기 위해 한번 실행된 연산의 결과를 메모리에 저장해두고 재사용하는 기법을 사용하는데, 이를 메모이제이션(memoization)이라고 하며 동적 계획법을 핵심이라고 볼 수 있는 부분이다.  간단한 예시지만 동적 계획법을 활용한 문제풀이는 대체로 이와같이 점화식을 찾아 문제를 분할하여 해결하도록 구현한 뒤, 중복되는 연산은 한번만 실행하고 값을 메모리에 저장하여 재사용 하는 것으로 최적화한다는 흐름으로 이루어진다.

 

 

2. Top-Down 동적 계획법

 동적 계획법을 실제로 구현하는 형태중 하나로 함수의 재귀호출을 사용하는 top-down 방식이 있다.  피보나치 수를 예시로 들었을 때의 트리(그림 1)가 top-down의 형태를 가장 잘 나타낸다고 할 수 있을 것이다.  재귀함수를 다루는데 익숙하다면 구현이 편하고 가독성이 좋다는 장점이 있다. 하지만 재귀호출이라는 방식 자체의 한계로 속도 면에서 불이익이 있을 수 밖에 없다.  다만 간혹 n번째 값을 구하기 위해 n-1까지의 모든 값이 필요하지 않은 경우, top-down 형태의 구현이 불필요한 연산 횟수가 줄어들어 이후에 설명할 bottom-up 방식보다 더 나은 성능을 보이는 경우도 있어 어느쪽이 더 좋은지는 문제마다 다르다고 생각하는 것이 좋다. 

 

Top-down 방식으로 피보나치 수를 구하는 문제를 해결한 코드는 다음과 같다.

dp = {}


def fibo(n):
    # n이 1 이하일 경우 자기 자신을 반환 => f(0) = 0, f(1) = 1
    if n <= 1:
        return n

    # fibo(n-1)가 아직 계산되지 않았다면 계산하여 메모리에 저장
    if dp.get(n - 1, -1) == -1:
        dp[n - 1] = fibo(n - 1)

    # fibo(n-2)가 아직 계산되지 않았다면 계산하여 메모리에 저장
    if dp.get(n - 2, -1) == -1:
        dp[n - 2] = fibo(n - 2)

    # fibo(n) = fibo(n-1) + fibo(n-2)
    return dp[n - 1] + dp[n - 2]

   

 

3. Bottom-Up 동적 계획법

 동적  계획법을 실제로 구현하는 또다른 형태로 bottom-up 방식이 있다.  bottom-up 방식은 초기값 몇개를 구한 뒤 점화식을 토대로 계속해서 다음 값을 채워나가는 형태로 문제를 해결한다. 이미 계산된 값으로 다음값을 구해나가기 때문에 단순반복문으로 구현되며 초기값을 제대로 설정하고 점화식만 제대로 알아낸다면 놀라울정도로 간단하게 문제를 해결할 수 있고, 모든 경우를 따져봐야 답을 구할 수 있는 문제의 경우 재귀함수를 사용한 top-down 방식의 구현보다 속도가 빠르다.  다만 실제로 해결하려는 문제에 굳이 필요하지 않더라도 중간의 모든 값을 채워나가기 때문에 불필요한 연산이 추가적으로 발생할 수 있다는 단점도 존재한다.

 

bottom-up 방식으로 피보나치 수를 구하는 문제를 해결한 코드는 다음과 같다.

def fibo(n):
    # f(0) = 0, f(1) = 1
    fibo = [0, 1]

    # fibo(n) = fibo(n-1) + fibo(n-2)
    for i in range(2, n+1):
    	fibo.append(fibo[i-1] + fibo[i-2])
    
    return fibo[n]

 

 

4. 동적 계획법이 적용될 수 있는 경우

 동적 계획법은 특정 문제를 풀기위한 알고리즘이 아닌 문제를 해결하기위한 접근 방식, 방법론이기 때문에 그 활용도가 굉장히 높아 관련 문제도 다양하고 난이도 또한 문제에 따라 천차만별이다.  어떤 문제를 봤을 때, 동적계획법을 적용하여 해결 가능한지와 동적계획법을 어떻게 적용할 것인지를 빠르게 파악하는 것이 중요하다.  동적 계획법으로 풀 수 있는 문제들의 공통적인 특징 두가지에 대해 알아보자.

 

① 중복 문제의 발생

 동적 계획법은 문제를 작게 쪼갠 뒤 중복연산의 결과를 메모리에 저장해두고 재활용하는 것으로 쪼개진 문제들을 빠르게 해결하는 방법론이다.  달리 말하면 분할된 문제들이 서로 중복되는 부분이 없다면 동적 계획법이 적용될 여지는 없다.  이 경우는 분할 정복의 영역이 될 것이다.  이진 탐색 문제나 병합정렬 등이 이와 같은 경우이다. 

 

② 분할 가능 여부

 문제에 따라서는 부분문제로 나누어 최적해를 취한 것이 전체로 볼 때는 최적해가 아닌 경우도 존재한다.  그런 경우를 예시로 하나 살펴보자.

 

* A 에서 B로 가는 경로

	시간	요금
경로 1	3	15
경로 2	5	10

 

* B에서 C로 가는 경로

	시간	요금
경로 1	7	25
경로 2	4	37

A에서 B로, B에서 C로 가는 경로별로 걸리는 시간과 요금이 위와같이 주어졌을 때, A에서 B를 경유하여 C로 가야할 때, 비용이 50을 넘지 않으면서 가장 짧은 시간 내에 갈 수 있는 경로의 조합을 구해야 한다면 각 구간으로 문제를 나누어 더 짧은 시간이 걸리는 쪽을 고르던 더 적은 요금이 드는 쪽을 고르던 전체 문제의 최적해에는 도달하지 못한다.

 

이러한 문제가 발생하는 것은 부분 문제들이 서로 독립적이지 않기 때문이다.  비용이 50을 넘어선 안되기 때문에 A에서 B로 가는 경로를 하나 고를 경우 B에서 C로 가는 경로를 고를 때는 비용의 한도가 A에서 B로 가기위한 비용만큼 줄어든다. 즉, 한 부분 문제에서의 선택이 다른 부분 문제에 영향을 미친다.  이런 형태의 문제에서는 동적 계획법을 적용하기 어렵다.

 

 즉, 동적 계획법을 적용하기 위해서는 문제를 독립적인 부분문제들로 분할 가능해야하며 그 부분문제들 사이에 중복되는 부분이 있어야 한다 고 볼 수 있다.  다만 실전에서 문제를 봤을때 이런 부분들을 하나하나 계산해가며 동적 계획법을 적용할지 고민할 시간은 없기 때문에, 실제로 문제를 봤을때 동적 계획법의 적용 가능 여부를 판단할 수 있는 능력은 많은 문제를 풀어보며 경험으로 몸에 익히는 수 밖에 없을 것 같다.