동적 계획법

동적 계획법(Dynamic programming)란 컴퓨터 과학에서, 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. 영어 약자로 DP(디피)라고도 한다.

개요[편집]

동적 계획법(DP)의 원리는 일반적으로 주어진 문제를 풀기 위해서 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다. 동적 계획법 알고리즘은 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용된다. 왜냐하면 동적 계획법은 문제를 해결하기 위한 모든 방법을 검토하고, 그 중에 최적의 풀이법을 찾아내기 때문이다. 이에 우리는 동적 계획법을를 모든 방법을 일일이 검토하여 그 중 최적해를 찾아내는 주먹구구식 방법이라고 생각할 수 있다. 그러나 문제가 가능한 모든 방법을 충분히 빠른 속도로 처리할 수 있는 경우, 동적 계획법은 최적의 해법이라고 말할 수 있다. 때로는 단순한 재귀함수에 저장 수열(이전의 데이터를 모두 입력하는 수열)을 대입하는 것 만으로도 최적해를 구할 수 있는 동적 알고리즘을 찾을 수 있다. 그러나 대다수의 문제는 이보다 훨씬 더 복잡한 프로그래밍을 요구한다. 그 중에 일부는 여러 개의 매개 변수를 이용하여 재귀 함수를 작성해야 하는 것도 있고, 아예 이러한 방법으로 동적 알고리즘을 짤 수 없는 문제 또한 존재한다. 이러한 퍼즐로는 대표적으로 에그 드로핑 퍼즐(Egg Dropping Puzzle)이 있다.^[1]

역사[편집]

동적 계획법(DP)이라는 용어는 리처드 벨먼(Richard Bellman)이 1940년대에 최고의 결정을 차례로 찾아야 하는 문제를 해결하는 과정을 설명하기 위해 사용했던 용어이다. 1953년까지 그는 특히 더 큰 의사결정에 더 작은 의사결정 문제를 내포하는 것을 언급하면서 이를 현대적 의미로 다듬었고, 이후 이 분야는 전기전자기술자협회(IEEE)에 의해 시스템 분석 및 엔지니어링 주제로 인식되었다. 벨먼의 기여는 반복적인 형태로 최적화 문제를 재현하는 동적 계획법의 중심 결과인 벨먼 방정식의 이름으로 기억된다. 벨만은 그의 자서전, '태풍의 눈'(Eye of the Hurricane)에서 다음과 같이 말했다.^[2]

나는 랜드(RAND) 코퍼레이션에서 1950년의 가을을 보냈다.
여기에서 내게 주어진 첫 과제는 다단계(multistage) 의사 결정 프로세스에 대해 적절한 용어를 명명하는 것이었다.
'DP'라는 이름이 어디에서 왔는지 궁금하지 않은가?
1950년대는 내가 수학에 대해 연구하기에는 좋지 못한 시기였다.
우리는 그 때 워싱턴에서 윌슨이라는 사람과 함께 일하고 있었다.
윌슨은 연구라는 것에 대해 굉장히 병적인 공포를 가지고 있었다.
사람들이 그 앞에서 연구에 대해 이야기를 꺼내면 그는 완전히 미치다시피 했다.
그러나 불행히도 랜드는 공군 소속의 회사였고, 윌슨은 그 공군의 간부인 국방 위원장이었다.
그래서 내가 랜드 안에 있었을 때 윌슨을 비롯한 공군들이 내가 수학에 대해 연구하는 것을 보이지 않게 막는다는 것을 알 수 있었다.
처음 올 때는 나는 위의 문제에 대해 '의사 결정 프로세스'라는 이름을 사용했지만,
여기에서 '프로세스(Process)'라는 단어를 사용하는데 여러가지 차질이 생겨버리고 만 것이다.
그래서 나는 사람들이 알지 못하게 '계획법(Programming)'이라는 단어를 붙였다.
또한 나는 이 프로세스가 다단계로 이루어져 있으며, 시가변적(time-varing)이며, '동적(Dynamic)'이다라는 개념(idea)이 전달되길 원했다.
이 단어야말로 내가 연구하는 알고리즘의 성질을 정확하게 짚어내었고,
게다가 윌슨에게도 피해를 입히지 않으며 공군도 이 단어에선 꼬투리를 잡지 못했으니 그야말로 일석이조의 효과를 누린 것이다.

즉, 'Dynamic'이라는 말은 벨먼이 이런 알고리즘의 '시가변적이며 다단계적인' 특성을 나타내기 위해서 채택한 용어인 것이다. 또한 'Programming'이라는 단어는 공군 내에서도 워드 프로세스 교육이나 군수 물자 운송 등에 이용되는 단어였기 때문에 사용하는데 아무 제약이 없었던 것이다. 이렇게 만들어진 'DP'라는 단어는 선형 계획법이나 수리 계획법처럼 하나의 프로그래밍 기법을 나타내는 단어가 되었다.^[1]

이론[편집]

동적 계획법이 적용되기 위해서 문제가 가져야 하는 두 가지 핵심 속성이 있는데, 바로 최적의 하부 구조와 중복되는 하위 문제이다. 오버랩되지 않는 서브 문제에 최적의 솔루션을 결합해 문제를 해결할 수 있다면 그 전략을 대신 '분할과 정복'이라고 한다. 병합 분류와 빠른 분류가 동적 프로그래밍 문제로 분류되지 않는 이유이다. 최적 하위 구조란 주어진 최적화 문제에 대한 해결책을 하위 문제에 대한 최적 해결책의 조합에 의해 얻을 수 있다는 것을 의미한다. 그러한 최적의 하부 구조는 대개 재귀의 수단으로 설명된다. 예를 들어, 그래프 G=(V,E)를 보면, 꼭지점 u에서 꼭지점 v까지의 최단 경로 p는 최적의 하부 구조를 나타낸다. 즉, 이 최단 경로 p에서 중간 정점 w를 취한다. p가 정말로 최단 경로인 경우, 이는 실제로 해당 정점 사이의 최단 경로(알고리즘 소개에서 설명한 단순 절단 및 붙여넣기 인수에 의해)가 되도록 u에서 w까지, p2로 하위 경로 p1로 분할될 수 있다. 따라서 벨만-포드(Bellman–Ford) 알고리즘이나 플로이드-워셸(Floyd–Warshall) 알고리즘이 하는 재귀적인 방법으로 최단 경로를 찾기 위한 솔루션을 쉽게 공식화할 수 있다. 하위 문제가 중복되는 것은 하위 문제의 공간이 작아야 한다는 것을 의미하며, 즉 문제를 해결하는 모든 재귀 알고리즘은 새로운 하위 문제를 생성하는 것이 아니라 동일한 하위 문제를 반복해서 해결해야 한다. 예를 들어, 피보나치(Fibonacci) 영상 시리즈 생성을 위한 재귀적 공식은 다음과 같다. Fi = Fi-1 + Fi-2, 베이스 케이스 F1 = F2 = 1. 그 다음 F43 = F42 + F41, 그리고 F42 = F41 + F40. 현재 F41은 F42뿐만 아니라 F43의 재귀 하위 트리에서 해결되고 있다. 하위문제의 총수가 실제로 작더라도(그 중 43개만) 이와 같은 순진한 재귀적 해결책을 채택하면 결국 같은 문제를 반복해서 해결하게 된다. 동적 계획법(DP)은 이 사실을 감안하여 각각의 하위 문제를 단 한 번만 해결한다. 이에 대한 접근 방식은 다음과 같다.

하향식 접근 방식: 이것은 어떤 문제의 재귀적 공식화에서 직접적인 탈락이다. 만약 어떤 문제에 대한 해결책을 그것의 하위 문제에 대한 해결책을 사용하여 반복적으로 공식화할 수 있고, 그것의 하위 문제가 중복된다면, 그 해결책을 쉽게 메모하거나 표에 하위 문제에 대한 해결책을 저장할 수 있다. 새로운 하위 문제를 해결하려고 할 때마다 먼저 테이블에서 이미 해결이 되었는지 확인한다. 해결책이 기록된 경우에는 직접 사용할 수 있고, 그렇지 않으면 하위 문제를 해결하고 그 해결책을 표에 추가한다.
상향식 접근법: 일단 하위 문제처럼 반복적으로 문제에 대한 해결책을 공식화하면, 우리는 하위 문제를 먼저 해결하고 그들의 해결책을 빌드온(built-on)하여 더 큰 하위 문제에 대한 해결책에 도달하는 바텀업 방식으로 문제를 개혁해 볼 수 있다. 이것은 또한 작은 하위 문제에 대한 해결책을 사용하여 더 크고 더 큰 하위 문제에 대한 해결책을 반복적으로 생성함으로써 표 형식으로 이루어진다. 예를 들어 F41과 F40의 값을 이미 알고 있다면 F42의 값을 직접 계산할 수 있다.^[2]

메모이제이션

동적 계획법 알고리즘의 대표적인 예 중 하나는 이항 계수(nCr)의 계산이다. bino(a, b) = bino(a - 1, b) + bino(a - 1, b - 1) 이라고 정의해 보자. bino(4, 2)를 호출했을 때 함수가 재귀적으로 호출된다. bino(2,1)는 bino(3,1)과 bino(3,2)에서 모두 호출된다. bino(2,1)은 bino(1,0), bino(1,1)을 재귀 호출하여 이 경우도 두 번씩 호출된다. 동적 계획법에는 이처럼 중복된 계산을 막기 위해 저장된 결과를 배열에 저장한 뒤, 다음에 계산이 필요할 때는 저장된 값을 불러와서 중복을 없애면 함수 호출이 줄어드는 것을 알 수 있다. 따라서, 시간 복잡도도 훨씬 줄어들게 된다. 이러한 기법을 메모이제이션(memoization)이라고 한다.^[3]

알고리즘[편집]

예시[편집]

데이크스트라 알고리즘[편집]

동적 계획법(DP)의 관점에서 최단 경로 문제에 대한 데이크스트라(Dijkstra)의 알고리즘은 최단 경로 문제에 대한 동적 프로그래밍 기능 방정식을 도달 방법에 의해 해결하는 연속적인 근사 체계이다. 실제로 알고리즘 뒤에 숨겨진 논리, 즉 데이크스트라의 설명은 다음과 같다.

문제: 주어진 두 노드 $P$ 와 $Q$ 사이의 최소 총 길이의 경로를 찾으십시오.

우리는 $R$ 이 $P$ 에서 $Q$ 까지의 최소 경로에 있는 노드라면, 후자의 지식은 $P$ 에서 $R$ 까지의 최소 경로에 대한 지식을 내포한다는 사실을 이용한다. 최단 경로 문제의 맥락에서 벨먼의 유명한 최적성의 원리를 패러프레이징한 것이다.^[2]

피보나치 수열[편집]

피보나치 수열의 n번째 멤버 계산에 동적 계획법을 사용하면 성능이 크게 향상된다. 다음은 수학적 정의에 직접 기초하여 순진한 구현이다.

   function fib(n)
       if n <= 1 return n
       return fib(n − 1) + fib(n − 2)

fib(5)를 호출하면 동일한 값으로 함수를 여러 번 호출하는 콜 트리가 생성된다는 점에 유의해야 한다.

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

특히 fib(2)은 처음부터 세 번 계산했다. 더 큰 예에서, fib의 더 많은 값, 즉 '하위 문제'가 다시 계산되어 지수 시간 알고리즘으로 이어진다. 이미 계산된 각 섬유 값을 그 결과에 매핑하는 간단한 지도 객체 $m$ 을 가지고 있다고 가정해 보자. 그리고 그것을 사용하고 업데이트하도록 우리의 기능을 수정한다. 결과 함수는 지수 시간 대신 O(n) 시간만 필요하다.

   var m := map(0 → 0, 1 → 1)
   function fib(n)
       if key n is not in map m 
           m[n] := fib(n − 1) + fib(n − 2)
       return m[n]

이미 계산된 값을 저장하는 이 기법을 메모이제이션(memoization)이라고 하는데, 이것은 우리가 먼저 문제를 하위 문제로 분리한 다음 값을 계산하고 저장하기 때문에 톱다운 방식의 접근법이다. 상향식 접근법에서 우리는 먼저 작은 섬유 값을 계산한 다음 그것들로부터 더 큰 값을 만든다. 이 방법은 n - 1회 반복하는 루프를 포함하고 있어 O(n)시간도 사용하지만 지도를 저장하는 데 O(n)공간이 필요한 하향식 접근법과는 대조적으로 일정(O)공간만 소요된다.

   function fib(n)
       if n = 0
           return 0
       else
           var previousFib := 0, currentFib := 1
           repeat n − 1 times // loop is skipped if n = 1
               var newFib := previousFib + currentFib
               previousFib := currentFib
               currentFib  := newFib
       return currentFib

두 예 모두 fib(2)를 한 번만 계산한 다음, 두 가지 모두 평가될 때마다 계산하는 대신 fib(4)와 fib(3) 모두를 계산하는 데 사용한다. 위의 방법은 각각 $\Omega (n)$ 비트를 가진 두 개의 정수를 더하는 데 $\Omega (n)$ 시간이 걸리기 때문에 실제로 큰 n에 $\Omega (n^{2})$ 시간이 걸린다. (nth 피보나치 번호는 $\Omega (n)$ 비트를 가지고 있다.) 또한 비넷의 공식으로 알려진 피보나치 수열의 폐쇄형식이 있는데, 여기서 $n$ -th 용어는 약 $O(n(\log n)^{2})$ 시간 내에 계산될 수 있으며, 이는 위의 DP 기법보다 효율적이다. 그러나 단순 반복은 빠른 행렬 지수에 의해 대략 $O(n\log n)$ 알고리즘으로 이어지는 행렬 형태를 직접 제공한다.^[2]

균형 0–1 행렬의 유형[편집]

각 행과 각 열이 정확하게 $n/2$ 0과 $n/2$ 를 포함하도록 $n\times n$ 행렬의 위치에 값을 $0$ 또는 $1$ 로 할당하는 문제를 고려한다. 우리는 주어진 $n$ 에 대해 얼마나 많은 다른 과제가 있는지 물어본다. 예를 들어 $n=4$ 일 때 가능한 4가지 해결책은 다음과 같다.

{\begin{bmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{bmatrix}}{\text{ and }}{\begin{bmatrix}0&0&1&1\\0&0&1&1\\1&1&0&0\\1&1&0&0\end{bmatrix}}{\text{ and }}{\begin{bmatrix}1&1&0&0\\0&0&1&1\\1&1&0&0\\0&0&1&1\end{bmatrix}}{\text{ and }}{\begin{bmatrix}1&0&0&1\\0&1&1&0\\0&1&1&0\\1&0&0&1\end{bmatrix}}.

적어도 세 가지 가능한 접근법이 있다. 바로 무차별 대입 공격 (Brute-force attack), 퇴각검색, DP이다. 무차별 대입 공격은 0과 1의 모든 할당을 확인하고 행과 열이 균형 잡힌 행과 컬럼이 $n/2$ 와 $n/2$ 인 행을 세는 것으로 구성된다. ${\tbinom {n}{n/2}}^{n}$ 가능한 과제가 있기 때문에 이 전략은 $n=6$ 까지가 아니면 실용적이지 않다. 이 문제에 대한 퇴각검색은 매트릭스 요소의 일부 순서를 선택하고 매트릭스 요소 또는 0을 재귀적으로 배치하는 것으로 구성되며, 모든 행과 컬럼에서 할당되지 않은 요소의 수와 1 또는 0의 수가 둘 다 $n/2$ 이상인지 점검한다. 이러한 접근 방식은 맹렬한 힘보다 정교하지만, 우리가 보게 될 것처럼 $n=8$ 에 대한 해결책의 수가 이미 116,963,796,250이기 때문에 6보다 큰 $n$ 은 모든 해결책을 한 번 방문할 수 없을 것이다. 다음으로, DP를 통해 솔루션 수를 모두 방문하지 않고도 셀 수 있다. 첫 번째 행의 역추적 값을 상상해 보자. 우리는 $k$ 행이 $n/2$ 0과 $n/2$ 를 포함하는 $k\times n$ 보드를 고려한다. 메모이제이션이 적용되는 $f$ 함수는 허용되는 보드 수에 $n$ 쌍의 정수 벡터를 매핑한다. 각 열에 한 쌍이 있으며, 각 열의 두 성분은 각각 0과 해당 열에 아직 배치되지 않은 0의 수를 나타낸다. 우리는 $f((n/2,n/2),(n/2,n/2),\ldots (n/2,n/2))$ ( $n$ 인수 또는 $n$ 원소의 하나의 벡터)의 가치를 추구한다. 하위 문제 생성 과정에는 보드의 맨 위 행에 대한 ${\tbinom {n}{n/2}}$ 가능한 모든 할당을 반복하고, 맨 위 행에 대한 할당에 0이 포함되었는지 아니면 그 위치에 0이 포함되었는지에 따라 해당 열에 대한 쌍의 적절한 요소에서 하나를 빼면서 모든 열을 거치는 과정이 포함된다. 결과 중 하나라도 음수이면 할당이 무효가 되고 해결책 집합에 기여하지 않는다. 그렇지 않으면 $k\times n$ 보드의 맨 위 행에 대한 할당을 가지고 나머지 $k-1\times n$ 보드에 대한 해결책 수를 재귀적으로 계산하여, 맨 위 행의 모든 허용 가능한 할당에 대한 해결책 수를 추가하고, 그 합계를 반환하여 메모한다. 기본 사례는 $1\times n$ 보드에 발생하는 사소한 하위 문제이다. 벡터가 $n/2$ $(0,1)$ 와 $n/2$ $(1,0)$ 쌍의 순열인지 여부에 따라 이 보드의 용액 수는 0 또는 1이 된다. 예를 들어, 벡터의 시퀀스 위에 표시된 처음 두 보드의 경우 다음과 같다.

((2, 2) (2, 2) (2, 2) (2, 2))       ((2, 2) (2, 2) (2, 2) (2, 2))     k = 4
  0      1      0      1              0      0      1      1

((1, 2) (2, 1) (1, 2) (2, 1))       ((1, 2) (1, 2) (2, 1) (2, 1))     k = 3
  1      0      1      0              0      0      1      1

((1, 1) (1, 1) (1, 1) (1, 1))       ((0, 2) (0, 2) (2, 0) (2, 0))     k = 2
  0      1      0      1              1      1      0      0

((0, 1) (1, 0) (0, 1) (1, 0))       ((0, 1) (0, 1) (1, 0) (1, 0))     k = 1
  1      0      1      0              1      1      0      0

((0, 0) (0, 0) (0, 0) (0, 0))       ((0, 0) (0, 0), (0, 0) (0, 0))

문제의 답은 $1,\,2,\,90,\,297200,\,116963796250,\,6736218287430460752,\ldots$ 이다.^[2]

체커보드[편집]

정사각형이 $n\times n$ 인 체커보드와 제곱 c(i, j)과 관련된 비용을 반환하는 비용 함수 (i,j)를 고려해야 한다. 예를 들어 다음과 같은 5 × 5 체커보드가 있다.

	1	2	3	4	5
5	6	7	4	7	8
4	7	6	1	1	4
3	3	5	7	8	2
2	–	6	7	0	–
1	–	–	5	–	–

따라서 c(1, 3) = 5이 된다.

첫 번째 행의 어느 정사각형에서나 시작할 수 있는 체커가 있었고, 마지막 순위에 도달하기 위해 최단 경로(각 방문 순위별 최소 비용의 합계)를 알고 싶었다고 하자. 그리고 체커가 대각선 방향으로만, 직선으로 이동할 수 있다고 가정하자. (1,3)의 체커는 (2,2), (2,3) 또는 (2,4)로 이동할 수 있다.

	2	3	4
5
4
3
2	x	x	x
1		o

이 문제는 최적의 하부 구조를 보여준다. 즉, 전체 문제에 대한 해결책은 하위 문제에 대한 해결책에 의존한다. 함수 q(i, j)를 q(i, j) = 제곱에 도달하기 위한 최소 비용 q(i, j)으로 정의한다. n등급에서 시작하여 1등급으로 내려감으로써, 우리는 이 함수의 값을 각 연속적인 등급의 모든 제곱에 대해 계산한다. 각 등급에서 최소값을 가진 사각형을 선택하면 n등급과 1등급 사이의 최단 경로가 나온다. 함수 q(i, j)는 아래에 있는 세 개의 제곱 중 하나에 도달하기 위한 최소 비용과 같다. 이 제곱에 도달할 수 있는 유일한 제곱이기 때문이다. 예를 들자면 다음의 체크보드와 같다.

	2	3	4
5
4		A
3	B	C	D
2
1

q(A)=\min(q(B),q(C),q(D))+c(A)\,

이제 좀 더 일반적인 용어로 q(i, j)를 정의해 보자.

q(i,j)={\begin{cases}\infty &j<1{\text{ or }}j>n\\c(i,j)&i=1\\\min(q(i-1,j-1),q(i-1,j),q(i-1,j+1))+c(i,j)&{\text{otherwise.}}\end{cases}}

이 방정식의 첫 번째 선은 가장 낮은 경계에서 1에 지수화된 정사각형, 가장 높은 경계에서 n으로 지수화된 보드를 다룬다. 두 번째 줄은 베이스 케이스를 제공하는 마지막 순위에서 일어나는 일을 명시한다. 세 번째 선인 재귀가 중요한 부분이다. 예시에서 A,B,C,D 용어를 나타낸다. 이 정의에서 q(i, j)에 대한 간단한 재귀 코드를 도출할 수 있다. 다음의 유사 코드에서 n은 보드의 크기, c(i, j)는 비용 함수, min()은 숫자의 최소값을 반환한다.

function minCost(i, j)
    if j < 1 or j > n
        return infinity
    else if i = 1
        return c(i, j)
    else
        return min( minCost(i-1, j-1), minCost(i-1, j), minCost(i-1, j+1) ) + c(i, j)

이 함수는 실제 경로가 아니라 경로 비용만 계산한다. 이것은 피보나치-숫자의 예처럼, 중복되는 하위 문제 속성도 나타내기 때문에 끔찍하게 느리다. 즉, 동일한 경로 비용을 반복해서 재평가한다. 그러나 함수를 사용하는 것이 아니라 경로 비용을 2차원 배열 q[i, j]로 저장하면 상향식 방식으로 훨씬 빠르게 계산할 수 있다. 이는 재조정을 피할 수 있다. 배열 q[i, j]에 필요한 모든 값은 단 한 번만 미리 계산된다. (i,j)에 대한 사전 계산된 값은 필요할 때마다 간단히 조회된다.

실제 최단길이 무엇인지도 알아야 한다. 이를 위해 다른 배열 p[i, j]를 사용한다. 이 배열은 모든 사각형 s에 대한 경로를 기록한다. s의 이전 버전은 s의 사전 계산된 경로 비용의 지수(q[i, j])에 상대적인 오프셋으로 모델링된다. 완전한 경로를 재구성하기 위해 우리는 시작 광장에 도달할 때까지 s의 전신, 그 광장의 전신, 그 광장의 전신 등을 재귀적으로 찾아본다.

 function computeShortestPathArrays()
     for x from 1 to n
         q[1, x] := c(1, x)
     for y from 1 to n
         q[y, 0]     := infinity
         q[y, n + 1] := infinity
     for y from 2 to n
         for x from 1 to n
             m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1])
             q[y, x] := m + c(y, x)
             if m = q[y-1, x-1]
                 p[y, x] := -1
             else if m = q[y-1, x]
                 p[y, x] :=  0
             else
                 p[y, x] :=  1

이제 나머지는 최소한의 것을 찾아서 출력하는 간단한 문제다.^[2]

 function computeShortestPath()
     computeShortestPathArrays()
     minIndex := 1
     min := q[n, 1]
     for i from 2 to n
         if q[n, i] < min
             minIndex := i
             min := q[n, i]
     printPath(n, minIndex)

 function printPath(y, x)
     print(x)
     print("<-")
     if y = 2
         print(x + p[y, x])
     else
         printPath(y-1, x + p[y, x])

시퀀스 정렬[편집]

유전학에서 시퀀스 정렬은 동적 계산법이 필수적인 중요한 응용 프로그램이다. 일반적으로 문제는 요소를 교체, 삽입 또는 제거하는 편집 작업을 사용하여 한 시퀀스를 다른 시퀀스로 변환하는 것으로 구성된다. 각 운영에는 관련 비용이 있으며, 가장 낮은 총 비용으로 편집 순서를 찾는 것이 목표다. 이 문제는 자연적으로 재귀로 나타낼 수 있으며, 다음 중 하나에 의해 순서 A가 최적으로 시퀀스 B로 편집된다.

B의 첫 번째 문자를 삽입하고 A와 B의 꼬리의 최적 정렬을 수행한다.
A의 첫 번째 문자 삭제, A와 B의 꼬리 맞춤 최적화
A의 첫 번째 문자를 B의 첫 번째 문자로 바꾸고, A와 B의 꼬리와 최적의 정렬을 수행한다.

부분 맞춤은 행렬로 표로 만들 수 있으며, 셀(i,j)은 A[1..i]와 B[1..j] 사이의 최적 정렬 비용을 포함한다. 셀 내 비용(i,j)은 관련 운용 비용을 인접 셀의 비용에 더하고 최적값을 선택하여 계산할 수 있다.^[2]

하노이 탑 퍼즐[편집]

하노이의 탑

하노이의 탑은 수학적인 게임이나 퍼즐을 말한다. 그것은 3개의 막대들과 어떤 막대 위로 미끄러질 수 있는 다른 크기의 많은 디스크들로 구성되어 있다. 퍼즐은 원반들이 맨 위에서 가장 작은 한 봉에 사이즈가 오름차순으로 깔끔하게 쌓여 원뿔형 모양을 만드는 것으로 시작한다.

퍼즐의 목적은 다음 규칙을 준수하여 스택 전체를 다른 로드로 이동하는 것이다.

한 번에 하나의 디스크만 이동할 수 있다.
각 이동은 로드 중 하나에서 상부 디스크를 꺼내 다른 로드 위로 밀어 넣는 것으로 구성되며, 로드 위에 이미 존재할 수 있는 다른 디스크 위로 이동한다.
어떤 디스크도 작은 디스크 위에 놓을 수 없다.

동적 계산법 솔루션은 기능 방정식의 해결로 구성된다.

S(n,h,t)=S(n-1,h,hnot(h,t)),S(1,h,t);S(n-1,not(h,t),t)

여기서 n은 이동할 디스크의 수를 나타내고, h는 홈 로드를 나타내며, t는 대상 로드를, (h,t)는 세 번째 로드(h 또는 t)를 나타내지 않고, ";"는 연결 상태를 나타낸다. S(n, h, t)은 로드 h에서 로드 t로 이동해야 하는 n개의 디스크로 구성된 문제에 대한 해결책이다. n=1의 경우 문제는 사소한 것으로, S(1,h,t) = "디스크를 로드 h에서 로드 t로 이동"(디스크가 하나만 남아 있다)는 뜻이다. 이 솔루션에 필요한 이동 횟수는 사이클링 없이 2n - 1회이다. 이동 횟수를 최대화하는 것이 목표라면 동적 계산법 기능 방정식은 약간 더 복잡해지고 3n - 1회 이동이 필요하다.^[2]

에그 드롭 퍼즐[편집]

다음은 N=2개의 달걀과 H=36층의 건물을 포함한 이 유명한 퍼즐의 예시에 대한 설명이다.

36층 건물의 어떤 층에서 계란을 떨어뜨리는 것이 안전하며, 어떤 층이 착륙할 때 계란이 깨지는지 알고 싶다고 가정해 보자. 우리는 다음과 같은 몇 가지 가정을 한다.

낙상에도 살아남은 달걀은 다시 사용할 수 있다.
깨진 달걀은 버려야 한다.
낙하의 효과는 모든 달걀에 동일하다.
알을 떨어뜨렸을 때 깨진다면, 더 높은 창문에서 떨어뜨리면 깨질 것이다.
계란이 추락에서 살아남는다면 더 짧은 추락에서도 살아남을 수 있을 것이다.
1층 창문이 달걀을 깨는 것도, 36층 창문에 달걀이 생존할 수 있다는 것도 배제하지 않는다.

단 한 개의 달걀만 구할 수 있고, 올바른 결과를 얻기를 희망한다면, 그 실험은 한 가지 방법으로만 수행될 수 있다. 1층 창문에서 계란을 떨어뜨리고, 그것이 살아남으면 2층 창문에서 떨어뜨린다. 그것이 깨질 때까지 계속 위로 올라간다. 최악의 경우, 이 방법은 36번이나 낙하할 수 있다. 달걀 2개가 있다고 가정하자. 모든 경우에 효과가 보장되는 계란 드로핑의 가장 낮은 숫자는? 이 퍼즐에 대한 동적 계산법 기능 방정식을 도출하려면 동적 계산법 모델의 상태를 쌍 s = (n,k)로 설정해야 한다.

n = 사용 가능한 테스트 계란 수, n = 0, 1, 2, 3, ..., N - 1

k = 아직 테스트할 (연속) 층수, k = 0, 1, 2, ..., H - 1

예를 들어 s = (2,6)는 2개의 테스트 알이 있고 6개의 (연속) 바닥이 아직 테스트되지 않았음을 나타낸다. 공정의 초기 상태는 s = (N, H)이며, 여기서 N은 실험 시작 시 사용할 수 있는 시험 난자의 수를 나타낸다. 공정은 더 이상 시험란이 없을 때(n = 0) 또는 k = 0 중 먼저 발생하는 경우 종료된다. 상태 s = (0, k) 및 k > 0에서 종료가 발생하면 테스트가 실패한다.

W(n, k) = 공정이 상태 s = (n, k)인 경우 최악의 경우 임계 바닥의 값을 식별하는 데 필요한 최소 시험 수이다.

이는 다음과 같이 나타낼 수 있다.

W(n, k) = 1 + min{max(W(n - 1, x - 1) W(n, k - x)): x = 1, 2, ..., k }

다른 파라메트리제이션을 사용한 더 빠른 동적 계산법 솔루션

위의 솔루션은 동적 계산법 솔루션과 함께 $O(nk^{2})$ 시간이 소요된다는 점에 유의해야 한다. 이는 위의 반복에서 최적의 $x$ 에 대한 바이너리 검색을 통해 $O(nk\log k)$ 시간으로 개선할 수 있는데, 이는 $W(n-1,x-1)$ 는 $x$ 에서 증가하고 $W(n,k-x)$ 는 $x$ 에서 감소하고 있기 때문에 $\max(W(n-1,x-1),W(n,k-x))$ 의 국소 최소치는 글로벌 최소값이기 때문이다. 또한 각 셀에 대한 최적 $x$ 를 동적 계산법 표에 저장하고 이전 셀에 대한 값을 참조함으로써, 각 셀에 대한 최적 $x$ 를 일정한 시간에 찾아 $O(nk)$ 시간으로 개선할 수 있다. 그러나 문제의 다른 매개변수를 포함하는 훨씬 더 빠른 해결책이 있다.

$k$ 를 $k$ 층에서 떨어뜨렸을 때 계란이 깨지는 총 층수로 한다. 위의 예는 $k=37$ 를 가져가는 것과 같다. $m$ 를 달걀이 깨지기 위해 떨어뜨려야 하는 최소 바닥이 되게 한다. $t$ try와 $n$ alg를 사용하여 구별할 수 있는 $m$ 의 최대 값 $f(t,n)$ 가 되도록 한다. 그렇다면 $f(t,0)=f(0,n)=1$ 는 $t,n\geq 0$ 이다. $a$ 는 최적의 전략에서 첫 번째 계란이 떨어지는 층이 되도록 한다. 만약 첫 번째 알이 깨졌다면, $m$ 는 $1$ 에서 $a$ 까지이고, 대부분의 $t-1$ 시도와 $n-1$ Eggs를 사용하여 구별할 수 있다. 만약 첫 번째 알이 깨지지 않았다면 $m$ 는 $a+1$ 에서 $k$ 까지이고 $t-1$ 시도와 $n$ 알로 구별할 수 있다. 따라서 $f(t,n)=f(t-1,n-1)+f(t-1,n)$ 이다. 그렇다면 문제는 $f(x,n)\geq k$ 와 같은 최소 $x$ 를 찾는 것과 같다. 그러기 위해서는 $t$ 를 증가시키기 위해 $\{f(t,i):0\leq i\leq n\}$ 를 계산하면 되는데, $O(nx)$ 시간이 걸릴 것이다. 따라서 $n=1$ 의 경우를 별도로 처리한다면 알고리즘은 $O(n{\sqrt {k}})$ 시간이 걸릴 것이다. 그러나 재발관계는 사실상 해결될 수 있는데, $f(t,n)=\sum _{i=0}^{n}{\binom {t}{i}}$ 는 모든 $i\geq 0$ 에 대해 신원 ${\binom {t}{i+1}}={\binom {t}{i}}{\frac {t-i}{i+1}}$ 를 이용하여 $O(n)$ 시간대에 계산할 수 있다. 모든 $t\geq 0$ 에 대해 $f(t,n)\leq f(t+1,n)$ 가 있기 때문에, 우리는 $x$ 를 찾기 위해 $t$ 에서 2진법으로 검색할 수 있고, $O(n\log k)$ 알고리즘을 부여한다.^[2]

매트릭스 체인 곱셈[편집]

매트릭스 체인 곱셈은 동적 프로그래밍의 효용을 보여주는 잘 알려진 예시이다. 예를 들어, 엔지니어링 애플리케이션은 종종 일련의 행렬을 곱해야 한다. 예를 들어 100×100과 같은 큰 차원의 행렬을 찾는 것은 놀라운 일이 아니다. 따라서 우리의 과제는 행렬 $A_{1},A_{2},\cdots A_{n}$ 을 곱하는 것이다. 기본 선형대수학에서 알 수 있듯이 행렬 곱셈은 교류가 아니라 연관성이 있으며, 한 번에 두 행렬만 곱할 수 있다. 그래서 우리는 이 행렬의 사슬을 여러 가지 다른 방법으로 곱할 수 있다. 예를 들면 다음과 같다.

((A_{1}\times A_{2})\times A_{3})\times \ldots A_{n}

A_{1}\times (((A_{2})\times A_{3})\times \ldots )\times A_{n})

(A_{1}\times A_{2})\times (A_{3}\times \ldots A_{n})

이 행렬의 사슬을 곱하는 방법은 수없이 많다. 이들은 모두 동일한 최종 결과를 산출하지만, 특정 행렬이 곱해지는 것에 기초하여 계산하는 데 다소 시간이 걸릴 것이다. 행렬 A의 치수가 m×n이고 행렬 B의 치수가 n×q인 경우, 행렬 C=A×B는 치수 m×q를 가지며 m*n*q 스칼라 곱셈을 요구한다. 예를 들어, 행렬 A, B, C를 곱해 보자. 그리고 그들의 치수가 각각 m×n, n×p, p×s 라고 가정해 보자. 매트릭스 A×B×C는 m×s 크기이며, 아래와 같은 두 가지 방법으로 계산할 수 있다.

Ax(B×C) 이 행렬 곱셈 순서는 nps + mns 스칼라 곱셈이 필요하다.
(A×B)×C 이 행렬 곱셈 순서는 mnp + mps 스칼라 계산이 필요하다.

m = 10, n = 100, p = 10, s = 1000이라고 가정해 보자. 그래서 체인을 곱하는 첫 번째 방법은 100만 + 100만 계산이 필요할 것이다. 두 번째 방법은 1만+10만 계산만 하면 된다. 분명히 두 번째 방법이 더 빠르며, 괄호 배열을 사용하여 행렬을 곱해야 한다. 따라서 결론은 괄호 순서가 중요하므로 괄호 순서의 최적 순서를 찾아야 한다. 이 시점에서 여러 가지 선택권이 있는데, 그 중 하나는 문제를 중복되는 문제로 나누어 최적의 괄호 배열을 계산하는 동적 계산법 알고리즘을 설계하는 것이다. 동적 계산법 솔루션은 아래에 제시되어 있다.

m[i,j]을 매트릭스 i에서 매트릭스 j로 매트릭스 체인을 곱하는 데 필요한 스칼라 곱의 최소 개수로 호출한다. 지금까지 어떤 매트릭스 k로 체인을 나누어서 m <= k < j>와 같이 어떤 조합이 최소 m[i,j]을 생산하는지 알아보려고 시도했다. 공식은 다음과 같다.

       if i = j, m[i,j]= 0
       if i < j, m[i,j]= min over all possible values of k (m[i,k]+m[k+1,j] +  $p_{i-1}*p_{k}*p_{j}$ )

여기서 k의 범위는 i부터 j - 1까지이다.

$p_{i-1}$ 는 행렬 i의 행 치수,
$p_{k}$ 는 행렬 k의 열 치수,
$p_{j}$ 는 행렬 j의 열 치수다.

이 공식은 아래와 같이 코딩할 수 있으며, 여기서 입력 매개변수 체인은 행렬의 체인 $A_{1},A_{2},\cdots A_{n}$ 이다.

 function OptimalMatrixChainParenthesis(chain)
     n = length(chain)
     for i = 1, n
         m[i,i] = 0    // Since it takes no calculations to multiply one matrix
     for len = 2, n
         for i = 1, n - len + 1
             j = i + len -1
             m[i,j] = infinity      // So that the first calculation updates
             for k = i, j-1
                 1=q = m[i, k] + m[k+1, j] +  $p_{i-1}*p_{k}*p_{j}$ }}
                 if q < m[i, j]     // The new order of parentheses is better than what we had
                     m[i, j] = q    // Update
                     s[i, j] = k    // Record which k to split on, i.e. where to place the parenthesis

지금까지 가능한 모든 m[i, j]에 대한 값, 즉 매트릭스 'i'에서 매트릭스 'j'로 체인을 곱하기 위한 최소 계산 횟수를 계산했고, 그에 상응하는 분할점 s[i, j]를 기록하였다. 예를 들어, 체인 $A_{1}\times A_{2}\times A_{3}\times A_{4}$ 를 곱하고 있는데 m[1, 3] = 100와 s[1, 3] = 2가 밝혀진다면, 그것은 행렬 1에서 3까지의 괄호 배치는 $(A_{1}\times A_{2})\times A_{3})$ 이고 그 행렬을 곱하기 위해서는 100 스칼라 계산이 필요하다는 것을 의미한다. 이 알고리즘은 i와 j의 가능한 모든 값에 대한 입력을 갖는 테이블 m[, ]과 s[, ]를 생성한다. 전체 체인의 최종 용액은 m[1, n]이며, s[1, n]에서 해당 분할이 이루어진다. 해결 방법을 푸는 것은 반복적이며, 위에서 시작하여 기본 사례에 도달할 때까지 계속될 것이다. 따라서 다음 단계는 체인을 실제로 분할하는 것, 즉 괄호가 속하는 곳에 배치하는 것이다. 이를 위해 다음과 같은 알고리즘을 사용할 수 있다.

 function PrintOptimalParenthesis(s, i, j)
     if i = j
        print "A"i
     else
        print "(" PrintOptimalParenthesis(s, i, s[i, j]) PrintOptimalParenthesis(s, s[i, j] + 1, j) ")"

물론 이 알고리즘은 실제 곱셈에는 유용하지 않다. 이 알고리즘은 단지 결과가 어떻게 보이는지 알 수 있는 사용자에게 친숙한 방법이다. 적절한 분할을 사용하여 행렬을 실제로 곱하기 위해서는 다음 알고리즘이 필요하다.^[2]

  function MatrixChainMultiply(chain from 1 to n)       // returns the final matrix, i.e. A1×A2×... ×An
     OptimalMatrixChainParenthesis(chain from 1 to n)   // this will produce s[ . ] and m[ . ] "tables"
     OptimalMatrixMultiplication(s, chain from 1 to n)  // actually multiply

  function OptimalMatrixMultiplication(s, i, j)   // returns the result of multiplying a chain of matrices from Ai to Aj in optimal way
     if i < j
        // keep on splitting the chain and multiplying the matrices in left and right sides
        LeftSide = OptimalMatrixMultiplication(s, i, s[i, j])
        RightSide = OptimalMatrixMultiplication(s, s[i, j] + 1, j)
        return MatrixMultiply(LeftSide, RightSide) 
     else if i = j
        return Ai   // matrix at position i
     else 
        print "error, i <= j must hold"

   function MatrixMultiply(A, B)    // function that multiplies two matrices
     if columns(A) = rows(B) 
        for i = 1, rows(A)
           for j = 1, columns(B)
              C[i, j] = 0
              for k = 1, columns(A)
                  C[i, j] = C[i, j] + A[i, k]*B[k, j] 
              return C 
     else 
         print "error, incompatible dimensions."

활용[편집]

단백질-디엔에이(DNA) 결합을 위한 격자 모델에 대한 반복적인 솔루션
유한 수평 이산 시간 동적 최적화 문제를 위한 솔루션 방법으로서의 역방향 유도
결정되지 않은 계수의 방법을 사용하여 무한 수평, 이산 시간, 할인, 시간 변동성 동적 최적화 문제
가장 긴 공통 부속, 가장 긴 증가 부속, 가장 긴 공통 하위 문자열, 레벤슈테인(Levenshtein) 거리를 포함한 많은 문자열 알고리즘
그래프의 트리 분해에 동적 프로그래밍을 사용하여 경계 트리 너비 또는 경계 클라이크 너비의 그래프
더 코크-주어진 문맥이 없는 문법에 의해 주어진 문자열이 생성될 수 있는지 여부와 어떻게 생성될 수 있는지를 결정하는 CYK(E-Kasami) 알고리즘
워드 래핑 텍스트 시 누더기를 최소화하는 크누스(Knuth)의 워드 래핑 알고리즘
컴퓨터 체스에서 전이 테이블과 리퓨테이션 테이블의 사용
비터비(Viterbi) 알고리즘: 히든 마르코프(Hidden Markov) 모델, 특히 음성 태그 지정의 일부에 사용됨)
얼리 알고리즘(차트 파서의 일종)
니들맨-순서 정렬, 구조 정렬, RNA 구조 예측을 포함한 생물정보학에서 사용되는 알고리즘 및 기타 알고리즘
플로이드의 올페어 최단 경로 알고리즘
체인 매트릭스 곱하기 순서 최적화
부분 집합 합, 배낭 및 파티션 문제에 대한 유사 폴리노멀 시간 알고리즘
두 시계열 사이의 전역 거리 계산을 위한 동적 시간 뒤틀림 알고리즘
셀링거 관계형 데이터베이스 쿼리 최적화를 위한 시스템 알고리즘
B-분할 곡선 평가를 위한 데보르(De Boor) 알고리즘
크리켓 경기가 중단될 때 문제를 해결하기 위한 덕워스-루이스(Duckworth-Louis) 방법
마르코프 의사결정 프로세스 해결을 위한 가치 반복 방법
포토샵의 마그넷 선택 도구와 같은 선택 방법에 따른 일부 그래픽 이미지
간격 스케줄링 문제를 해결하는 몇 가지 방법
여행 중인 세일즈맨 문제를 해결하기 위한 몇 가지 방법(예: 지수 시간) 또는 대략(예: 비트소닉 투어)
재귀 최소 제곱법
음악 정보 검색 시 비트 추적
인공신경망 적응성 비판적 훈련전략
스테레오 비전에 사용되는 통신 문제 해결을 위한 스테레오 알고리즘
심 조각(콘텐츠 인식 이미지 크기 조정)
그래프에서 최단 거리를 찾기 위한 벨먼-포드(Bellman-Ford) 알고리즘
선형 검색 문제에 대한 몇 가지 대략적인 해결 방법
최대 서브 어레이 문제에 대한 카다네(Kadane)의 알고리즘^[2]

각주[편집]

↑ ^1.0 ^1.1 동적 계획법 위키백과 - https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95
↑ ^2.00 ^2.01 ^2.02 ^2.03 ^2.04 ^2.05 ^2.06 ^2.07 ^2.08 ^2.09 ^2.10 Dynamic programming Wikipedia - https://en.wikipedia.org/wiki/Dynamic_programming#History
↑ all about coding, 〈동적계획법(Dynamic Programing, DP)〉, 《티스토리》, 2017-08-27

참고자료[편집]

동적 계획법 위키백과 - https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95
Dynamic programming Wikipedia - https://en.wikipedia.org/wiki/Dynamic_programming#History
all about coding, 〈동적계획법(Dynamic Programing, DP)〉, 《티스토리》, 2017-08-27

같이 보기[편집]

강화학습

이 동적 계획법 문서는 인공지능 기술에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

인공지능 : 인공지능 기술^□^■^⊕, 인공지능 활용, 인공지능 개발업체, 인공지능 인물

인간적 행위	로봇공학 • 로봇기술 • 인지과학 • 자동추론 • 자연어 처리 • 지식표현 • 컴퓨터 비전 • 튜링 테스트

합리적 사고	결정이론 • 논리학 • 논리주의자 • 삼단논법 • 선호도 • 최대기대효용 • 효용이론

강화학습	ADP • DDPG • DQN • SARSA • 결정이론적 메타추론 • 계통적 강화학습 • 동적 계획법 • 모델 기반 강화학습 • 모델 프리 강화학습 • 반영식 아키텍처 • 수시 알고리즘 • 심층믿음망 • 어니 • 에이전트 • 확률적 경사하강법

인공지능 프로그램	A2I • 어니 • 알파고 • 알파고제로 • 왓슨 • 카페 • 텐서플로 • 토치 • 한돌

인공지능 알고리즘	AGI • 관계형 네트워크(RN) • 다층퍼셉트론 • 데이터마이닝 • 딥러닝 • 딥큐러닝 • 머신러닝(기계학습) • 방사신경망 • 분산 샌드박스 • 비지도학습 • 생성대립신경망(GAN) • 생성형 AI • 수퍼 얼라인먼트 • 순전파 • 순환신경망(RNN) • 시그노이드 함수 • 신경망 구조 • 심층신경망(DNN) • 심층신뢰신경망(DBN) • 양방향 비고정값 암호 체계(TSID) • 역전파 • 인공신경망(ANN) • 인공지능(AI) • 제한 볼츠만 머신(RBM) • 전방전달신경망 • 지도학습 • 코헨 자기조직 신경망 • 텍스트마이닝 • 파이 • 퍼셉트론 • 합성곱 신경망(CNN)

문자인식	ICR • OCR • OMR • 문자인식

인공지능 특징	계산상의 합리성 • 분산성 • 불확실성 • 예측곤란성 • 완벽한 합리성 • 유계 합리성 • 이유 불충분의 원리 • 자율성 • 할루시네이션

계산 복잡도	NP • NP-완전 • 공간복잡도 • 시간복잡도 • 여 NP • 여 NP-완전

인공지능 기술	BCI • GPT • 딥블루 • 딥페이크 • 멀티모달 • 모달 • 모달리티 • 모달창 • 알렉스넷 • 왓슨 • 텔레파시 • 환각

인공지능 법적 지위	권리주체성 • 전자대리인 • 전자적 인간 • 책임법 • 코파일럿

인공지능 업무	데이터라벨러 • 데이터라벨링 • 크라우드워커

위키 : 자동차, 교통, 지역, 산업, 기업, 단체, 업무, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반

[.EC.9C.84.ED.82.A4.EB.B0.B1.EA.B3.BC-1] 1.0 ^1.1 동적 계획법 위키백과 - https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95

[.EC.9C.84.ED.82.A4.ED.94.BC.EB.94.94.EC.95.84-2] 2.00 ^2.01 ^2.02 ^2.03 ^2.04 ^2.05 ^2.06 ^2.07 ^2.08 ^2.09 ^2.10 Dynamic programming Wikipedia - https://en.wikipedia.org/wiki/Dynamic_programming#History

[3] ut coding, 〈동적계획법(Dynamic Programing, DP)〉, 《티스토리》, 2017-08-27

[1]

[2]

[3]

위키

이름공간

변수

보기

더 보기

검색