Dynamic Programming 문서 원본 보기

[[분류:알고리즘 설계와 분석]]
[[분류:컴퓨터 공학]]
상위 문서: [[알고리즘 설계와 분석#문제|알고리즘 설계와 분석]] 

==개요==
동적 프로그래밍(Dynamic Programming)은 좌우 순서로 배열된 문제들<ref>문자열, 수열 등에 관한 문제이다.</ref>에 대한 최적화 문제를 효율적으로 푸는 방법이다. 동적 프로그래밍의 핵심적인 아이디어는 복잡한 문제를 작은 하위 문제(subproblem) 로 나누고, 중복 계산을 피하기 위해 이전 결과를 저장(memoization)하는 것이다. 이때 동적 프로그래밍은 재귀적으로 구현한다는 것을 의미하지 않는다. 동적 프로그램의 본질은 어디까지나:
# 중복되는 하위 문제(Overlapping Subproblems): 예를 들면, 피보나치에서 fib(3)을 여러 번 계산하지 않는 것이 있다.
# 최적 부분 구조(Optimal Substructure): 큰 문제의 최적해가 작은 문제의 최적해들로 구성되는 것이다.
따라서 DP를 구현하는 방식은 아래와 같이 두 가지로 나뉜다:
# Top-Down(Memoization): 큰 문제에서 출발해 재귀를 통해 하위 문제를 호출하며, 이미 계산된 값은 저장하여 활용한다.
# Bottom-Up(Tabulation): 가장 작은 하위 문제부터 순서대로 반복문으로 해결하며, 결과를 테이블에 저장한다. 

동적 프로그래밍은 완전탐색(Exhaustive Search) 방식에 같이 사용된다. 완전 탐색 기법은 모든 가능한 해를 탐색하므로 항상 정답은 구하지만 비효율적이지만 동적프로그램과 같이 응용하여, 중복 계산을 제거하여 효율을 높일 수 있다. 이를 이용한 대표적인 알고리즘으로는 [[Shortest Paths#Floyd’s Algorithm|Floyd’s Algorithm]]이 있다. 

==Recurrence Relations==
점화식(Recurrence Relation)은 어떤 수열을 “이전 항들로 정의하는 식”이다. 즉, "자기 자신을 기반으로 정의된 함수"이다. 예를 들면, 아래와 같은 식이 있다:
 <math>a_n=a_{n-1}+1,a_1=1 \Rightarrow a_n = n</math>
 <math>a_n=2a_{n-1},a_1=2\,\,\,\,\,\,\, \Rightarrow a_n = 2^n</math>
 <math>a_n=na_{n-1}, a_1=1\,\,\,\,\,\,\, \Rightarrow a_n=n!</math>
이와 같이 점화식을 통해 문제의 구조를 반복되는 관계로 표현함으로서 프로그램이 재귀적으로 계산할 수 있다. 즉, 동적 프로그래밍은 이러한 점화식을 효율적으로 계산하기 위해 부분 결과를 저장하는 기법이다. 

===Master Theorem===
이때 점화식은 문제를 작은 하위 문제로 나누었을 때 이를 표현하는 수식이므로, 주어진 점화식을 이용해 알고리즘의 시간복잡도를 추론할 수 있다. 이를 마스터 정리(master theorem)이라고 하며, 이는 [[Sorting Problem#Mergesort#Divide and Conquer|분할 정복 알고리즘]]에도 적용될 수 있다. 마스터 정리는 점화식이 아래와 같은 형태임을 가정한다:
 <math>T(n) = a\cdot T(n/b)+f(n)</math>
위에서 a는 분할할 때 문제의 개수, n/b는 분할된 각 문제의 크기, f(n)은 부분 문제의 해를 합치는데 걸리는 비용을 의미한다. 일반화한 이 식을 통해 T(n)의 점근적인 시간복잡도를 구하면 아래와 같다:
*Case 1: <math>f(n) = O(n^{log_b{a-\epsilon}}),</math> for some <math>\epsilon > 0</math>
** 즉, 합치는 비용이 부분 문제 비용보다 작다. 이 경우, <math>T(n) = \Theta(n^{log_ba})</math>
* Case 2: <math>f(n) = \Theta(n^{log_ba}),</math>
** 즉, 합치는 비용이 부분 문제 비용과 비슷하다. 이 경우, <math>T(n) = \Theta(n^{log_ba}\cdot log(n))</math>
* Case 3: <math>f(n) = \Omega(n^{log_b{a+\epsilon}}),</math> for some <math>\epsilon > 0</math>
** 즉, 합치는 비용이 부분 문제 비용보다 크다. 이 경우, <math>T(n) = \Theta(f(n))</math>
** 단, 정규성 조건이 필요하다: <math>a\cdot f(n/b) \le c\cdot f(n)</math> for some <math>c < 1</math>

===Three Steps to Dynamic Programming===
마스터 정리를 바탕으로, 동적 프로그래밍을 하기 위한 3단계를 요약하면 아래와 같다:
# 점화식 세우기: 문제를 작은 하위 문제로 나누고, 이들 결과를 결합하는 수식을 만든다.
# 서브문제 개수의 다항성 보장: 가능한 하위 문제 수가 너무 많지 않아야 한다.<ref>마스터 정리를 통해 계산했을 때 전체 알고리즘의 시간 복잡도가 <math>O(n^2), O(n^3)</math> 정도이면 적당하다.</ref>
# 계산 순서 결정: 하위 문제의 결과를 이미 계산된 값으로부터 효율적으로 구할 수 있도록 순서를 정한다.

==[[Fibonacci Numbers]]==
피보나치 수열(Fibonacci Numbers)은 동적 프로그래밍의 대표적인 구현 예시 중 하나이다.

[[Fibonacci Numbers|피보나치 수열]]에 대한 자세한 설명은 해당 문서를 참조해주십시오.

==[[Binomial Coefficients]]==
이항 계수(Binomial Coefficients)는 동적 프로그래밍의 고전적인 응용 중 하나이다. 

[[Binomial Coefficients|이항 계수(Binomial Coefficients)]]에 대한 자세한 설명은 해당 문서를 참조해 주십시오.

==The Gas Station Problem==
Gas Station Problem은 아래와 같은 문제 정의를 가진다:
 가정 1: 뉴욕에서 플로리다까지 가는 길에 주유소 <math>g_1, g_2, \cdots, g_n</math>이 있다.
 가정 2: 각 주요소는 mile marker <math>m_i</math>에 위치해 있으며, 자동차는 한 번 주유로 R마일을 달릴 수 있다.
 목표: 목적지까지 가기 위해 최소 몇 번 주유해야 하는가?
이때 위 문제를 해결하기 위해서 <math>G[i]</math>를 주유소 <math>g_i</math>에 도달하기 위해 필요한 최소 주유 횟수라고 하면 점화식은 아래와 같이 정의된다: 
 <math>G[1]=0</math><ref>첫 번째 주유소는 출발점이므로 주유 횟수가 0이다.</ref>
 <math>G[i]=\min_{j<i,(m_i-m_j<R)}(G[i]+1)</math>
이는 이전 주유소 중에서 i까지 한 번에 갈 수 있는 모든 j에 대해, 가장 적은 주유 횟수의 경우를 선택하고 한 번 추가한다는 것을 의미한다. 

이에 대한 시간복잡도를 계산하면 <math>O(n^2)</math>이다. 이때 모든 i에 대해 가능한 j를 확인하므로 이 문제는 [[BFS]]로도 해결할 수 있다. 각 주유소를 정점, 도달 가능한 관계를 간선으로 보면 unweighted shortest path 문제이기 때문이다. 사실 많은 DP 문제는 실제로 DAG(Directed Acyclic Graph)에서 최단 경로를 찾는 문제의 변형이다. 

===Minimum Average Station Price===
이번에는 문제를 변형하여, 각 주요소마다 단가 <math>p(s)</math>가 다르다고 가정하여 “평균 가격이 최소가 되도록 어느 주유소들에서 멈춰야 하는가?”를 구해야 한다고 가정하자. 이때에는 얼마나 자주 넣는가를 고려하지 않고 방문하는 주유소들의 주유비 평균만 최소화하면 된다고 하자. 이를 해결하기 위해 <math>G[i,k]</math>를 주유소 <math>g_i</math>에 정확히 k번 주유한 뒤 도달할 때의 총 단가 합계라고 하면, 아래와 같이 점화식이 정의된다:
 <math>G[1,0]=0</math>
 <math>G[i,k]=\min_{j<i,(m_i-m_j<R)}(G[j,k-1]+p(j))</math>
즉, 해당 점화식은 이전 주유소 j에서 k-1번째 주유까지의 최소 단가합과 이번에 방문하는 주유소의 단가의 합을 의미한다. 최종적으로는 아래와 같은 식을 통해 평균 주유비가 최소가 되는 k를 찾는다:
 <math>\min_{k}\frac{G[n,k]}{k}</math>
하지만 이 방식은 “싼 곳에서 많이 넣고 비싼 곳에서 덜 넣는” 실제 전략을 반영하지는 못한다.

===Cheapest Filling Schedule===
해당 문단에서는 위 문제를 더욱 현실적으로 변형하여, 한 번에 “정수 갤런” 단위로만 주유가 가능하며, 각 주유소마다 가격이 다를 때, “최소 총비용으로 목적지까지 가는 주유 스케줄은 무엇인가?”를 구해야 한다고 가정하자. 이를 해결하기 위해 <math>G[i,k]</math>를 주유소 <math>g_i</math>에 도착했을 때 k갤런의 기름이 남은 상태로의 최소 비용을 의미한다고 가정하자. 이를 이용하면 점화식은 아래와 같이 구해진다:
 <math>G[1,0]=0</math> 
 <math>G[i,k]=\min_c \min_{j<i,(m_i-m_j<R_c)}\{G[j,c]+p(j)\cdot (k-c')\}</math>
위에서 <math>c'</math>은 출발 시 남은 기름량이며, <math>p(j)</math>는 j번째 주유소의 단가를 의미한다. 또한 <math>(m_i-m_j<R_c)</math>은 주유 후 남은 연료로 i까지 도달 가능한 경우만 고려한다는 것을 의미한다.

==각주==