다이나믹 프로그래밍

안녕하세요. 이번에 다이나믹 프로그래밍에 관하여 기술세미나를 드릴 김원상입니다.

다이나믹 프로그래밍은 코딩테스트를 처음 접하시는 분들에게는 진입장벽, 조금 익숙하신 분들에게는 알다가도 모를것 같은 알고리즙인데요. 제 나름대로 다이나믹 프로그래밍 문제를 접근하는 방법과 어떤 식으로 공부하면 좋을지에 대한 생각을 나눌 수 있을 것 같아 선택한 주제입니다. 커널360 코딩테스트에도 나왔고, 다른 기업 코딩테스트 후기를 봐도 조금씩 나오기 때문에 연습을 많이 해두시면 분명 원하는 회사를 가시는데 도움이 될 거라 생각합니다.

1. 리처드 E. 벨만

다이나믹 프로그래밍은 리처드 E. 벨만이라는 수학자가 처음 고안한 알고리즘입니다. 벨만에 따르면 일련의 결정은 정책(Policy)을 구성합니다. 그리고 정책은 결과값으로 이익 또는 비용(Cost)를 제공하게 되는데요. 가장 높은 이익 또는 가장 낮은 비용을 제공하는 정책을 최적 정책(Optimal Policy)라고 합니다. 아래 세가지는 최적 정책에 관하여 가장 중요하다 싶은 부분을 최초로 다이나믹 프로그래밍이 발표된 논문에서 발췌하여 요약한 것입니다.

최적 정책을 구할 때 모든 가능한 정책을 구하는 것은 보통 실용적(Practical)하지 않다.
어느 시점에서 어떤 행동을 선택할지에 대한 일반적인 처방(Prescription)만 있으면 최적 정책을 구하기에 충분하다.
다이나믹 프로그래밍의 기본적인 아이디어(Principle of Optimality) : 초기 상태 또는 선택이 무엇이든 간에 그에 따르는 선택은 반드시 최적 정책을 구성해야한다.

2. 다이나믹 프로그래밍의 두 가지 분류

결정론적이냐 확률론적이냐 그것이 문제로다!

위 최적 정책에 대한 설명 이외에 다이나믹 프로그래밍에서 주목할 부분은 결정론적 알고리즘이냐 확률론적 알고리즘이냐 하는 문제가 있는데요. 보통 코딩테스트에 나오는 문제는 결정론적 알고리즘이라 보시면 되겠습니다. 즉, 여러번 동일한 코드를 돌려도 같은 결과가 나온다는 것인데요. 논리적으로 사고하고 코드를 직접 작성할 수 있는 능력을 보는게 코딩테스트라면 그에 맞는 문제를 내기위해선 결정론적 알고리즘을 준비하는게 필요할 것입니다.

3. 알고리즘 개론

앞으로는 알고리즘의 교과서라고 할 수 있는 Introduction to Algorithms의 다이나믹 프로그래밍 부분을 발췌한 것입니다. 해당 알고리즘을 풀 수 있는 기본적인 가이드라인과 구체적인 예제로 Rod Cutting을 다루어 보겠습니다.

4. 다이나믹 프로그래밍을 푸는 4단계 과정

이 책에 따르면 다음과 같은 4단계를 거쳐 문제를 풀 수 있다고 합니다.

최적해의 구조를 특징지음
재귀적으로 최적해의 값을 정의
계산(주로 Bottom-up 방식)
최적해를 구성

구체적이고 대표적인 예시인 Rod Cutting문제를 통해 다음과 같은 단계를 거쳐 보겠습니다.

4-1. 최적해의 구조를 특징지음

Rod는 통나무 또는 철근이라고 볼 수 있습니다. 일정한 정수 길이 n을 지니며 양의 정수 길이로 자를 수 있습니다. 각 길이마다 가격이 형성되어 있는데 해당 길이를 지니는 Rod를 잘라 얻을 수 있는 가장 높은 가격의 합을 구하는 것이 Rod Cutting 문제입니다. 유관한 수식을 정리하고 가격표를 그리면 다음과 아래와 같습니다. 여기서 최적해는 r_n에서 보는 것처럼 잘린 Rod의 가격의 총합이 되겠지요.

수식

$$ Rod의 전체 길이 : n
$$ $$ i 길이의 Rod 가격 : p_i
$$ $$ 주어진 n에서 Rod를 잘라 얻을 수 있는 최대 수익 : r_n = p_{i1} + p_{i2} + … + p_{ik}
$$ $$ \sum_{j=1}^{k} ij = n $$

가격표 |*length i*|1|2|3|4|5|6|7|8|9|10| |—|—|—|—|—|—|—|—|—|—|—| |*price pi*|1|5|8|9|10|17|17|20|24|30|

이렇게만 봐서는 문제를 이해하기 힘들 수 있습니다. 그럼 구체적인 예시를 들어볼까요?

아래 그림에 n이 4인 경우 최적해를 구하는 방법이 도식화되어 있습니다

그림을 보시면 Rod를 자를 수있는 모든 경우가 표시되어있고 각 부분의 가격이 위에 적시되어있습니다. 그렇다고 보았을 때 최적해의 값은 세번째의 가격의 합인 10이 됩니다.

하지만 이런식으로 모든 경우를 구하여 최적해를 구하는 것은 매우 비효율적이라고 볼 수 있습니다. 자세한 설명은 아래 재귀적으로 최적해의 값을 정의하는 부분에서 자세히 알아보겠습니다.

4-2. 재귀적으로 최적해의 값을 정의

이 부분은 다이나믹 프로그래밍 풀이와 공부의 핵심이자, 우리가 알고리즘을 꾸준하게 공부해야하는 이유가 된다고 하겠습니다.

왜냐하면 코딩테스트는 이 문제를 어떠한 알고리즘을 사용하여 풀 수 있다고 가르쳐주지 않기 때문이죠. 따라서 이 문제가 다이나믹 프로그래밍으로 풀 수 있는지, 그리고 어떠한 점화식으로 풀 수 있는지를 명쾌하게 풀이해내는 능력이 매우 중요합니다. Rod Cutting 문제에 대하여 최적해의 값을 정의해보겠습니다.

n의 값이 주어져있고 그 이전의 n-1부터 1일 때의 최적해의 값을 알고있다고 가정하겠습니다. 길이가 0인 r값은 0이라는 가정하에 Rod는 n길이부터 1까지 자를 수 있으며 남은 길이는 앞서 알고 있는 최적해의 값으로 변환될 수 있습니다. 앞서 알고 있는 최적해의 값은 Optimal Substructure라고 할 수 있으며, 이를 가장 적게 활용한 방식이 아래 그림의 두번째 수식이라 할 수 있습니다.

재귀적으로 최적해의 값을 정의하는 것도 성공했습니다. 그럼 이를 코드로 옮겨 봐야죠 ~

의사코드로 표현한다면 다음과 같은 방식으로 표현이 됩니다.

이렇게 표현된 의사코드를 Python으로 작성하면 다음과 같습니다.

def cut_rod(p, n):
    if n == 0:
        return 0
    q = -9999
    for i in range(1, n + 1):
        q = max(q, p[i-1] + cut_rod((p, n-1)))
    return q

그럼 Rod Cutting 문제를 다이나믹 프로그래밍을 사용하여 효과적으로 계산한 것이 될까요? 그렇지 않습니다! n이 10인 경우는 그 이전의 9일 때와 계산 시간에서 유의미한 차이를 보이지 않습니다만, 25와 26일때를 상정하여 코드를 돌려보았을 때 기하급수적인 차이를 관찰할 수 있습니다.

소요시간 |*n*|25|26| |—|—|—| |*elapsed time*|00:00:14.8|00:00:32.2|

이유는 재귀 함수가 호출하는 수많은 서브 함수로 인해 시간복잡도가 무수히 늘어나기 때문이죠. 정확히는 2^n으로 기하급수적으로 함수호출의 개수가 늘어납니다. 몇가지 가정과 간단한 점화식으로 이를 증명해 보겠습니다.

위의 재귀적 정의나 코드에 따르면, 호출되는 함수의 개수를 T라고 할 때 0인 시점에 호출되는 함수를 1이라하고 시점이 1씩 늘어날 때마다 다음과 같은 산식이 됩니다.

$$ T(0) = 1
$$ $$ T(n) = 1 + \sum_{j=0}^{n-1} T(j) $$

이 때 우리의 목표는 T를 이전 Substructure를 사용하지 않고 n에 대한 산식으로 표현하는 것입니다. 가장 간단하게 시점 1인 경우 T 값은 다음과 같이 구할 수 있습니다.

$$ T(1) = 1 + T(0) = 2 $$

위의 점화식과 더불어 n이 2보다 큰 상황을 가정하여 해당 점화식이 어떤 식으로 일반화 될 수 있는지 살펴보겠습니다.

$$ T(n) = 1 + \sum_{j=0}^{n-1} T(j)
$$ $$ T(n-1) = 1 + \sum_{j=0}^{n-2} T(j)
$$ $$ if n \geqq 2 $$

위 두 식을 위 아래로 차감하면 다음과 같은 산식을 얻을 수 있습니다.

$$ T(n) - T(n-1) = T(n-1)
$$ $$ T( if n \geqq 2 $$

따라서 T를 n에 관한 식으로 풀어쓰면 다음과 같이 기하급수적인 2의 거듭제곱 꼴로 나타납니다.

$$ T(n) = 2 ^ n ( n\geqq 0 ) $$

직관적으로 해석해도 호출되는 함수의 양이 2배씩 증가함을 알 수 있습니다. 아래는 4를 호출할 경우 “재귀적으로만” 문제를 풀었을 때 호출되는 함수의 양입니다.

어기서 1을 늘려 5를 호출하였을 때 기대되는 함수의 개수는 다음과 같이 표현이 되는데, 정확하게 노드가 2배로는 것을 확인할 수 있게됩니다.

여기까지 최적해를 재귀적으로 정의하고 해를 구성한다는 것이 어떤 것인지 알아보았습니다. 여기서 재귀적으로 문제를 정의할 경우 생길 수 있는 시간복잡도 문제를 해결해야한다는 것도 알아보았습니다. 마지막으로 Bottom-up방식으로 최적해를 구할 때 얻을 수있는 시간복잡도상 이점이 무엇인지 알아보겠습니다.

4-3. Bottom-up 방식의 계산 최적화

Bottom-up 방식의 계산 최적화는 캐시메모리에 순차적으로 최적해의 값을 추가함으로써 재귀함수가 반복적으로 호출되지 않도록하는 것을 의미합니다. 다음의 의사코드가 그것을 표현합니다.

r은 최적해를 담아두는 배열로써 활용되고 이 중 반복문이 사용되어 이전 최적해를 불러오지만 지난번처럼 기하급수적으로 재귀함수를 호출하지는 않습니다. Python으로 작성한 코드는 다음과 같으며 앞서 보았던 25와 26으로 올라가는 n값에서 기하급수적인 시간소요는 보이지 않습니다.

def cut_rod(p, n):
    r = [0 for _ in range(n + 1)]
    for j in range(1, n + 1):
        q = -9999
        for i in range(1, j + 1):
            q = max(q, p[i] + r[j-i])
        r[j] = q
    return r[n]

소요시간 |*n*|25|26| |—|—|—| |*elapsed time*|00:00:00|00:00:00|

끝으로 다이나믹 프로그래밍을 풀기위해 다음 4가지 단계를 다시 한번 더 리마인드 해보겠습니다. 그리고 꾸준히 문제를 푸는 것도 잊지 맙시다.

최적해의 구조를 특징지음
재귀적으로 최적해의 값을 정의
계산(주로 Bottom-up 방식)
최적해를 구성

감사합니다.