동적 계획법(Dynamic programming)
겹치는 작은 문제의 답을 표에 적어 두고 다시 쓰는 방법. 편집 거리(edit distance), 최단 경로(shortest path), 배낭 문제(knapsack problem)가 이 방법으로 풀린다.
재귀(recursion)로 문제를 작은 문제로 쪼개다 보면 같은 작은 문제가 여러 번 다시 나오는 일이 많습니다. 피보나치 수
격자의 왼쪽 아래 칸에서 오른쪽 위 칸까지, 오른쪽이나 위로만 한 칸씩 가는 길은 몇 가지일까요? 어떤 칸에 이르는 길은 모두 그 칸의 왼쪽 칸이나 아래 칸을 거쳐 옵니다. 그러니 그 칸의 수는 왼쪽 칸의 수와 아래 칸의 수의 합입니다(위의 식). 막힌 칸이 없으면 이 표는 비스듬히 누운 파스칼의 삼각형(Pascal's triangle)이고, 답은 이항계수(binomial coefficient)
칸을 누르면 막히거나 다시 열립니다. 채운 칸에 마우스를 올리면 그 수가 어떻게 나왔는지 보입니다.
여기에 동적 계획법의 두 조건이 다 들어 있습니다. 첫째, 큰 문제의 답이 작은 문제들의 답으로 정해집니다. 가장 좋은 답을 찾는 문제에서는 이것을 '최적 부분 구조(optimal substructure)'라 부릅니다. 둘째, 작은 문제들이 여러 큰 문제에 겹쳐 쓰입니다(겹치는 부분 문제, overlapping subproblems). 필요한 칸이 늘 먼저 채워지도록 순서만 잘 정하면 칸 하나에 덧셈 한 번으로 끝납니다. 막힌 칸이 없을 때 길 210가지를 하나하나 따라가는 대신, 표는 35칸이면 됩니다. 1950년대에 미국의 수학자 리처드 벨먼이 이 방법에 이름을 붙이고 체계를 세웠습니다.
이어지는 곳. 두 문자열의 편집 거리는 두 낱말의 앞부분끼리의 거리를 표에 채워 구하고, 최단 경로는 '가장 짧은 길의 일부도 가장 짧은 길'이라는 같은 원리 위에 서 있습니다. 관측된 소리나 낱말들 뒤에 숨은 상태들의 가장 그럴듯한 줄을 찾는 은닉 마르코프 모델(hidden Markov model)의 비터비 알고리즘(1967년 앤드루 비터비), 무게 제한 안에서 가장 값진 물건을 고르는 배낭 문제(무게가 정수(integer)이면 물건 수 × 무게 한도 크기의 표로 풉니다), 분할수(partition number)를 세는 표도 모두 동적 계획법입니다. 분할 정복(divide and conquer)과 달리 하위 문제가 겹칠 때 쓰고, 매 순간 하나만 고르는 욕심쟁이 알고리즘(greedy algorithm)이 틀리는 문제도 모든 작은 문제의 답을 표에 담아 바르게 풉니다. 벨먼의 '최적 경로의 뒷부분도 최적'이라는 원리를 확률(probability)로 움직이는 세계에 쓴 식이 강화 학습(reinforcement learning)의 벨먼 방정식이고, 그 해를 구하는 가치 반복(value iteration)은 표를 되풀이해 고쳐 채우는 동적 계획법입니다. 최단 경로의 표를 채우는 식
이 개념이 나오는 긴 글
이 개념 위에 세워진 것
이 개념을 언급하는 페이지
- 피보나치 수열
… 자신과 같은 속도, 곧 \varphi^n 에 비례해 늘지만, 앞의 두 값을 적어 두며 차례로 올라가는동적 계획법은 n걸음이면 끝납니다. 수열 전체를 급수 \sum F_n x^n 의 계수로 담으면 생성함수 …
- 파스칼의 삼각형
… 그것으로 다음 줄을 만드니, 계승( n! = 1 \cdot 2 \cdots n )을 한 번도 계산하지 않는동적 계획법입니다. 맨 윗줄을 0번째 줄, 각 줄의 맨 왼쪽을 0번째 칸으로 세면, n 번째 줄 k 번째 수 …
- 이항계수
… 그대로 파스칼의 삼각형이 됩니다. 작은 칸의 답을 표에 적어 두고 더해 큰 칸의 답을 얻는 이 방식은동적 계획법의 가장 단순한 예입니다. 이항정리. (a+b)^n = (a+b)(a+b)\cdots(a+b) 를 전개하면 …
- 차원의 저주
… 늘어납니다. 축마다 10칸으로 나누면 10^d 칸이 필요합니다. 미국의 응용수학자 리처드 벨먼이동적 계획법을 다루며 이 어려움을 '차원의 저주'라고 불렀고, 흔히 1957년 책 《동적 계획법》이 처음으로 …
- 편집 거리
… 첫 행과 첫 열은 빈 문자열 ε에서 시작하므로 0, 1, 2, …입니다. 이렇게 표를 채우는 방법을동적 계획법이라고 합니다. 단어 쌍은 입니다. 편집 거리는 , 해밍 거리는 입니다. 아래 단추와 막대로 표를 처음부터 …
- P 대 NP 문제
… 정도로 줄어듭니다. 또 T가 작으면 '0부터 T까지 각 합을 만들 수 있는가'를 표로 채워 가는동적 계획법이 n × T걸음 정도로 풉니다. 하지만 T가 100자리 수라면 이 표는 쓸모가 없습니다. 걸음 수가 T의 …
- 문맥 자유 문법
… 안 됩니다. 주어진 문장의 트리를 찾는 일(구문 분석)은 작은 문제의 답을 표에 적어 가며 큰 문제를 푸는동적 계획법으로 풀 수 있습니다. 1960년대에 코크, 영거, 가사미가 따로 찾아내 세 사람의 머리글자를 딴 CYK …
- 은닉 마르코프 모델
… 수 있기 때문입니다. 그래서 일은 T N^2 에 비례하는 횟수의 곱셈으로 끝납니다. 편집 거리와 같은동적 계획법입니다. 확률에 −로그를 씌우면 곱이 합으로, 최대가 최소로 바뀌어, 이 계산은 날짜별 상태를 점으로 …
- 역전파
… 한 번만 계산해 적어 두고, 왼쪽 칸들은 그 값을 다시 씁니다. 겹치는 작은 문제의 답을 표에 적어 두는동적 계획법과 같은 생각입니다. 층 단위로 보면 각 층의 국소 미분은 층의 출력 하나하나를 입력 하나하나로 미분한 …
- 점화식
… 수열⟧ a_n = F_{n+1} 이 됩니다. 작은 경우의 답으로 큰 경우의 답을 짓는 이 생각이 재귀와동적 계획법의 뿌리입니다. 아래는 a_n = p\,a_{n-1} + q\,a_{n-2} + c 꼴의 점화식입니다. …
- 카탈랑 수
… C_n 가지입니다. 이 수는 금세 너무 커지므로, 모두 따지지 않고 가장 싼 곱셈 순서를 찾는 문제는동적 계획법의 교과서 예제입니다. 닫힌 식. 오르기 n번, 내리기 n번인 길은 모두 \binom{2n}{n} …
- 알고리즘
… 반으로 나눠 각각 풀고 합치는 분할 정복, 겹쳐 나오는 작은 문제의 답을 표에 적어 두고 다시 쓰는동적 계획법, 매 순간 가장 좋아 보이는 것을 고르는 욕심쟁이 알고리즘, 계산 도중 동전을 던지는 ⟦무작위 …
- 재귀
… 수가 F_n 에 비례해 불어나는데, 한 번 구한 답을 적어 두고 다시 쓰면 n번 남짓이면 됩니다. 이것이동적 계획법입니다. 이어지는 곳. 유클리드 호제법 \gcd(a, b) = \gcd(b,\ a \bmod b) 은 …
- 분할 정복
… 수 있습니다. 이진 탐색: 반쪽 하나만 남기고 나머지를 버리는, a = 1, d = 0인 경우입니다.동적 계획법: 하위 문제들이 서로 겹치면 분할 정복은 같은 일을 되풀이하게 됩니다. 그때는 한 번 푼 답을 적어 두고 …
- 욕심쟁이 알고리즘
… 나중의 가능성을 막아 버린 것입니다. 이럴 때는 1원부터 차례로 모든 금액의 최소 개수를 표에 채우는동적 계획법으로 정확한 답을 구합니다. 아래 줄이 그렇게 구한 답입니다. 욕심쟁이가 옳다는 것은 보통 바꿔치기로 …
- 콜모고로프 복잡도
… 프로그램 길이는 글자 수입니다. 가장 짧은 프로그램은 부분 문자열마다의 최적 답을 표에 채워 가는동적 계획법으로 정확히 찾을 수 있고, 답은 되풀이 안에 되풀이가 든 재귀적인 모양입니다. 문자열: . 비트를 …
- 기계 학습
… 합니다. 앞날에 받을 보상의 합을 지금 상태의 값으로 거꾸로 계산하는 식은 1950년대 리처드 벨먼의동적 계획법에서 왔고, 이 식을 경험으로 어림해 푸는 것이 많은 강화 학습 알고리즘의 뼈대입니다. 배우는 방법. …
- 선형 계획법
… 넓혀집니다. 가장 좋은 것을 고르는 일 전반은 가장 좋은 것 고르기에서, 가능한 조합이 폭발하는 문제는동적 계획법과 욕심쟁이 알고리즘에서 이어집니다.
- 자동 미분
… 가는 수많은 길을 하나하나 따로 더할 필요가 없습니다. 겹치는 부분 문제의 답을 적어 두고 다시 쓰는동적 계획법과 같은 생각입니다. 수치 미분은 왜 안 쓸까. 입력이 n개면 기울기 하나에 f를 n + 1번 계산해야 …
- 강화 학습
… 가서, 도착한 곳에서부터 다시 가장 잘 행동한다고 생각하면 됩니다. 이 식은 1950년대 리처드 벨먼이동적 계획법을 세우며 쓴 최적성의 원리를 적은 것입니다. 최적 계획의 뒷부분은 그 자체로 (그 지점에서 출발하는) …
- 게임 트리 탐색: 미니맥스와 몬테카를로 트리 탐색
… 게임 트리는 트리의 한 예이고, 같은 국면에 여러 길로 도달할 때 값을 표에 적어 다시 쓰는 요령은동적 계획법과 같습니다. 값을 끌어올리는 이 계산에서 상대 대신 주사위처럼 확률로 움직이는 환경이 있으면, 최솟값 …
- 디코딩: 온도, top-p, 빔 탐색
… 가장 그럴듯한 상태 열을 정확히 찾습니다. 다음 단계가 지금 상태 하나(몇십 가지)에만 달려 있어서,동적 계획법으로 겹치는 계산을 한 번씩만 할 수 있기 때문입니다. 트랜스포머의 '상태'는 앞의 토큰 전체라서, 서로 …
- 풍부화된 범주: 거리를 범주로
… 방법( W, W^{\odot 2}, W^{\odot 4}, \dots )도 됩니다. 모두 같은 D를동적 계획법의 서로 다른 순서로 계산하는 것입니다. V를 바꾸면 '길을 잇는 방법'이 바뀝니다. 그림의 선택지를 …
- 반환
… 대해 지수적으로 늘 수 있지만, 표 채우기는 한 단계에 n³번 정도의 연산이면 됩니다(n은 마을 수).동적 계획법의 많은 알고리즘이 바로 이런 반환 위의 표 채우기입니다. 아래 그림에서 물음은 , 길의 변 수는 k = …
- 님과 스프라그–그런디 정리
… 수가 아닌 게임도 있습니다.) 이어지는 곳. 끝에서부터 국면에 이름을 매기는 원리는 게임 트리 탐색과동적 계획법이 공유하고, 그 원리가 우연이 없고 모든 것이 보이는 유한한 게임에 모두 통한다는 것이 체르멜로의 …