동적계획법

동적 프로그래밍

동적 프로그래밍은 세부 계산으로 나뉘어지는 하나의 큰 문제를 세부 계산 결과를 미리 구해서 저장한 후 큰 계산의 결과를 빠르게 도출해내는 문제해결 기법이다.(이름과는 달리 프로그래밍 테크닉은 아니다.) 흔히 피보나치 수열을 계산할 때 memoization도 동적 프로그래밍의 범주로 볼 수 있다.

피보나치 수열은 자연수 n에 대해서 다음과 같이 정의된다.

a(n) = 1 (n <= 2)
a(n) = a(n-1) + a(n-2)

정의 자체는 깔끔하지만 실제로 컴퓨터를 통해서 저 식을 계산하는 것은 많은 무리가 따른다.

a(3) = a(2) + a(1) = 1 + 1 = 2
a(4) = a(3) + a(2) = (a(2) + a(1)) + a(2) = ( 1 + 1)  + 1 = 3
a(5) = (a(4) + a(3)) = ((a(3)+a(2)) + (a(2) + a(1))) = (((a(2) + a(1)) + a(2)) + (a(2) + a(1)))

n의 값이 커지면 커질 수록 계산량이 지수적으로 증가한다. 문제는 이런 대부분의 계산이 한 번 했던 계산을 게속해서 반복하게 된다는 점이다. 예를 들어 100번째 항을 구한다고 하면

a(100) = a(99) + a(98) 

이 되는데, 이 때 99번째 항은 a(98) + a(97) 이며, 다시 a(98)a(100)을 계산하는 시점에 한 번 더 쓰이게 된다. 따라서 한 번 계산한 작은 계산의 결과를 저장해두고, 보다 큰 계산을 수행하는 대신 작은 계산 결과의 합으로 대체한다. 또 비교적 큰 계산의 결과도 모두 저장해두면 반복계산으로 인한 시간 낭비를 줄일 수 있다.

먼저 재귀적인 방법으로 이 문제를 푼다면

def fib(n):
    if n < 2:
        return 1
    return fib(n-1) + fib(n-2)

피보나치 수열의 일반항의 수학적 정의는 매우 간단하며, 이를 코드로 옮긴 위 표현 역시 매우 단순하다. 그렇지만 이 문제 구조는 컴퓨터가 풀어내기에 매우 불리하다. 앞서 말했던 것과 마찬가지로 n이 크면 클수록 지수적으로 계산량이 증가한다.

만약 한 번 계산한 결과를 재활용한다면? 메모이제이션을 통해서 확인해보자.

memo = {0:1, 1:1}
def fib(n):
    if n in memo:
        return memo[n]
    else:
        result = fib(n-1) + fib(n-2)
        memo[n] = result
        return result

함수 외부에 계산 결과를 저장하는 해시테이블을 하나 준비하여 계산 결과를 캐시하도록 한다. 메모이제이션은 일반적인 알고리듬이므로, 이는 파이썬의 경우 다음과 같은 방식으로 데코레이터로 일반화할 수 있다.

def memoize(func):
    memo = {}
    def wrapped(n):
        if n in memo:
            return memo[n]
        else:
            result = func(n)
            memo[n] = result
            return result
    return wrapped

@memoize
def fibonacci(n):
    return fibonacci(n-1) + fibonacci(n-2)

동적 계획법은 이러한 종류의 문제를 풀어내는 강력한 기술이다. 동적 계획법의 접근은 단순한 아이디어이며, 코딩 역시 매우 단순하다. 이는 정확히는 알고리듬이라기보다는 패러다임에 가깝다.

  1. 탑-다운: ‘메모이제이션’이라고도 불린다. 위 피보나치 문제와 같이 큰 계산을 작은 계산으로 나누고 작은 계산의 결과를 저장, 재사용한다.
  2. 바텀-업: 문제를 분석하여 작은 문제들이 풀려나가는 순서를 확인한 후 사소한 문제부터 풀어나가기 시작한다. 이 과정에서 작은 문제들은 전체 문제가 풀리기 전에 모두 풀리는 것이 보장된다. 이것이 동적 계획법이라 불리는 것이다.

분할정복 알고리듬은 이 보다는 좀 차이가 있다. 분할정복에서 서브 문제들은 오버래핑되지 않는다. 예를 들어 병합정렬이나 퀵소트 정렬이 분할 정복에 해당된다. 또한 그리디 알고리듬과도 다르다. 그리디 알고리듬은 특정 조건 내의 최적의 근사 해를 구하는 방법이며 별도의 수학적 증명을 요구하지만, 동적 계획법은 수학적인 유도에 의해서 만족된다.

시스템 재귀와 동적 계획간의 냉전

재귀는 탑다운 방식의 해결에 자주 쓰인다. 즉 큰 문제를 작은 문제들로 나누고 작은 문제는 같은 방식 (더 작은 문제로 나눔)으로 계산한다. 이 접근법에서는 CPU 시간이 점점 더 많이 쓰이게 되고, 시간 복잡도가 증가한다. 반면 동적 계획법에서는 작은 문제는 여러번 풀어지지 않으며 한 번 풀린 서브 문제의 답은 전체 문제를 최적화하는데 사용된다.

예를 들어 피보나치 수열을 다시 생각해보면

fib(4) = fib(3) + fib(2) 
    = fib(2) + fib(1) + fib(1) + fib(0)
    = fib(1) + fib(0) + fib(1) + fib(1) + fib(0)

이 된다. 동적계획의 문제는 중간과정에서 불필요한 서브문제의 해도 모두 구한다는 점이다. (반면 재귀는 필요한 계산만한다) 따라서 동적 계획으로 문제를 풀때는 이런 부작용을 최소화할 필요가 있다. 조합의 가지수를 구하는 계산에서 동적 계획법은 다음의 파스칼 삼각형을 계속 만들어 나가게 된다.

             1
            1  1
           1  2  1
          1  3  3  1
         1  4  6  4  1
        1  5  10 10 5 1

재귀와 동적 계획은 서브 문제가 겹치지 않은 케이스에 대해서는 거의 동일한 접근법이라 할 수 있다. 대신 이 문제에 대해서는 분할정복이라는 다른 계산법도 적용이 가능하다.

문제: 1까지의 최단 경로

어떤 양의 정수 n에 대해서, 이 n을 감소시키는 방법에는 여러 가지 방법이 있다. 1) 1을 뺀다. 2) n이 짝 수 인 경우 2로 나눈다. 3) n이 3의 배수인 경우 3으로 나눈다. 임의의 양의 정수 n에 대해 1까지 가는 최소 단계의 수를 구하면?

이 문제는 그리디 알고리듬으로 푸는 게 가장 쉬워 보인다. 예를 들어 10의 경우,

10 (/2) -> 5 (-1) -> 4 -> 2 -> 1

이렇게 5단계가 나오게 된다. 하지만 10의 최단 경로는

10 (-1) -> 9 (/3) -> 3 (/3) -> 1

로 4가 답이다. 즉 n에 대한 경로의 길이는 1 + min( Pn-1, Pn/2, Pn/3) 으로 결정된다. 이 문제는 ‘중첩되는 서브 문제’의 성질의 것이다. 주어진 수에 대한 최적해는 주어진 수에 대한 서브 문제(n보다 작은 양의 정수들의 경로의 길이)에 의존한다. 따라서 메모이제이션이나 bottom-up 방식으로 문제를 풀어나갈 수 있을 것이다.

메모이제이션으로 이 문제를 풀어보면

@memoization
def path_memo(n):
    if n < 2:
        return 0
    else:
        test = [path_memo(n-1)]
        if n % 2 == 0:
            test.append(path_memo(n/2))
        elif n % 3 == 0:
            test.append(path_memo(n/3))
        result = 1 + min(test)
        return result

이런 코드가 나오게 된다. 동적 계획은 앞에서부터 전부 계산한다.

def path_dp(n):
    paths = [0, 0] + [0] * (n)
    #        ^0 ^1    .....n
    # path[1] = 0
    intervals = [1,2,3]
    for i in range(2, n+1):
        paths[i] = paths[i-1] + 1
        if i % 2 == 0:
            paths[i] = min((paths[i], 1 + paths[i/2]))
        elif i % 3 == 0:
            paths[i] = min((paths[i], 1 + paths[i/3]))
    return paths[n]

필요한 n개 만큼의 배열을 생성한 다음, 1번 항에서부터 계산하여 n까지의 항을 계산하여 배열에 저장해 나가면 n번째 항을 기록하게 되고, 이 때 계산을 완료하게 된다.

문제: 가장 긴 증가하는 부분 수열

이번 문제는 주어진 수열에 대해 그 부분 수열 중, 각 항이 증가하는 순서로 구성된 가장 긴 부분 수열을 찾는 것이다.

가장 평이한 로직은 A1부터 다음 항이 이전 항보다 크면 부분 수열에 추가하는 식으로 검사한다. 최악의 경우 이 방식은 O(n^2)의 시간 복잡도를 가지게 된다. 이는 수열의 맨 뒤에서부터 앞의 항이 뒤의 항보다 큰 경우 (증가하는 부분 수열의 끝)에서 시작하여 앞으로 나가면서 길이값을 1씩 늘려나가고, 다시 앞의 항이 더 큰 경우를 만나면 0으로 초기화하는 방법을 사용하면 n의 시간복잡도로 줄일 수 있게 된다.

def LIS(aList):
    _length = len(aList)
    lis = [0] + [0] * _length
    for i in xrange(_length-2, 0, -1):
        if aList[i] < aList[i + 1]:
            lis[i] = lis[i+1] + 1
    max_index = lis.index(max(lis))
    return aList[max_index:max_index+lis[max_index]+1]

aList = [8, 3, 2, 4, 5, 6, 2, 7, 1, 2, 4, 7, 8, 9, 7]
print LIS(aList)
  • 유제아

    저도 프로그래밍을 합니다

  • 유제아

    고맙습니다.

  • 유제아

    ??