위상 정렬 ↔ 동적 계획법의 계산 순서

요약

표를 채워 답을 구하는 방법(동적 계획법)에서 칸들은 “이 칸을 구하려면 저 칸이 먼저 있어야 한다”는 관계로 이어진다. 이 관계를 화살표로 그리면, 표를 채우는 올바른 순서는 화살표가 모두 앞에서 뒤로 가게 칸을 한 줄로 세운 것(위상 정렬)과 같다. 그래서 어떤 순서가 맞는지는 “읽는 칸이 늘 앞에 있나” 하나로 판정하고, 서로 기대지 않는 칸끼리는 순서를 바꿔도 된다. 다만 칸끼리 서로 기대면(고리) 채울 순서가 아예 없어 칸의 뜻을 바꿔야 하고, 순서가 맞아도 점화식이 맞다는 것은 따로 증명해야 한다.

먼저 비교해 보기

표를 펼치기 전에 두 사례의 공통 구조와 대응 관계를 먼저 적어 본다.

알고리즘: 구간 DP(행렬 A, B, C)	이산수학: 선수관계(함수 ~ 적분)
칸 6개: [A], [B], [C], [A,B], [B,C], [A,B,C]	개념 6개: 함수, 지수, 로그, 삼각, 미분, 적분
[A,B,C]를 구할 때 [A]와 [B,C], [A,B]와 [C]를 읽는다	미분 앞에 로그와 삼각함수가 와야 한다
[A], [B], [C]는 아무 칸도 읽지 않고 0이다	함수는 선수 개념이 없다
길이 순: [A], [B], [C], [A,B], [B,C], [A,B,C]	함수, 지수, 로그, 삼각, 미분, 적분
시작점이 큰 것부터: [C], [B], [B,C], [A], [A,B], [A,B,C]도 된다	함수, 삼각, 지수, 로그, 미분, 적분도 된다
시작점이 작은 것부터 채우면 [A,B]를 구할 때 [B]가 아직 비어 있다	로그를 지수보다 앞에 두면 틀린다
맞는 채우기 순서는 모두 16가지	맞는 줄 세우기는 모두 3가지

대응 관계

화살표 a → b는 “b를 구할 때 a를 읽는다”, 곧 a가 먼저라는 뜻이다. 부분순서와 위상 정렬의 선수관계 화살표와 방향이 같다¹.

알고리즘	수학	공통 구조
표의 칸(상태)	원소	줄 세울 대상
점화식이 b를 구할 때 a를 읽는다	간선 a → b. \(a \prec b\)는 화살표를 따라 a에서 b로 갈 수 있다는 뜻(도달 관계)²	의존 = 화살표
아무 칸도 읽지 않는 시작값들: 구간 DP의 행렬 하나짜리 구간, 트리 DP의 잎, 동전이 3원·4원일 때 dp[0], dp[1], dp[2]	극소 원소(여럿일 수 있다)	아무것에도 기대지 않는 것
미리 정한 채우기 순서: 금액 x 오름차순, 구간 길이 순	선형 확장	모든 화살표가 앞에서 뒤로
화살표를 따라가면 늘 커지는 값: 금액 x, 구간 길이, 플로이드–워셜의 k	순서를 지키는 번호 f: \(a \prec b\)이면 \(f(a) < f(b)\)	번호 순으로 세우면 선형 확장
여러 올바른 순서(행렬 3개 구간 DP는 16가지)³. 1원 동전이 있으면 x − 1 → x가 줄줄이 이어져 한 가지뿐	선형 확장이 여럿. 전순서면 하나	비교할 수 없는 칸끼리는 순서가 자유
위에서부터 기억하기: 읽는 쪽으로 내려가는 재귀가 칸을 끝내는 순서³	목표와 목표보다 앞서야 하는 원소들만 세운 선형 확장	필요한 것을 먼저 끝낸다
번호로 순서가 안 보이는 그래프 위의 DP(길의 수 세기)⁴	칸 알고리즘이나 DFS로 위상 정렬을 먼저 구한다	순서를 먼저 구하고 그 순서로 채운다
칸끼리 서로 읽으면 채울 순서가 없다	사이클이 있으면 위상 정렬이 없다	고리 판정

flowchart LR
    A["A"] --> AB["A, B"]
    B["B"] --> AB
    B --> BC["B, C"]
    C["C"] --> BC
    A --> ABC["A, B, C"]
    BC --> ABC
    AB --> ABC
    C --> ABC

먼저 비교해 보기 왼쪽 열의 구간 DP 칸 여섯 개를 화살표로 이은 그림이다. 화살표 a → b는 “b를 구할 때 a를 읽는다”이다. 맞는 채우기 순서는 모든 화살표가 앞에서 뒤로 가게 이 여섯 칸을 한 줄로 세운 것이다⁵.

어디까지 같은가

같은 범위. 상태가 유한하고, 칸마다 다른 칸의 최종 값만 읽으면 늘 맞는다. 채우는 순서가 선형 확장이면 칸을 구하는 순간 읽을 칸이 모두 채워져 있다. 선형 확장이 아니면 어떤 화살표 a → b에서 b가 a보다 앞에 온다. 그때 b를 구하며 빈 칸 a를 읽는다.
순서는 정답을 보장하지 않는다. 선형 확장은 귀납법을 어떤 순서로 돌릴지만 정한다. “작은 칸의 가장 좋은 답을 이어 붙이면 큰 칸의 가장 좋은 답”이라는 점화식 자체는 동적 계획법의 잘라 붙이기 논증으로 따로 보인다.
기억하기 재귀는 고리를 알아차리지 못한다. DFS의 세 가지 색과 달리, 기억하기 표에는 “계산 중” 표시가 없다. dp[x] = min(dp[x − 1], dp[x + 1]) + 비용[x]처럼 칸끼리 서로 읽으면 같은 칸을 끝없이 다시 불러 RecursionError가 난다.
나무에서만 맞는 규칙이 있다. 트리 DP는 뿌리부터 방문한 순서를 거꾸로 돈다. 칸마다 그 칸을 읽는 부모가 하나뿐이라 맞는다. 한 칸을 여러 칸이 함께 읽으면 틀릴 수 있다(확인 문제 C2). 재귀가 칸을 끝내는 순서는 고리만 없으면 늘 맞는다.
제자리에서 고치는 표는 순서가 더 묶인다. 0-1 배낭을 (물건 i, 무게 w)의 2차원 표로 보면 dp[i][w]는 i − 1 줄만 읽는다. 같은 줄의 칸끼리는 화살표가 없어 아무 순서로 채워도 된다. 1차원 표는 한 칸에 옛 줄의 값과 새 줄의 값을 차례로 쓴다. 새 dp[w + 무게]가 옛 dp[w]를 읽으니, dp[w]는 그 뒤에 덮어써야 한다. 큰 쪽부터 도는 규칙(동적 계획법의 확인 문제 C4)은 의존 관계가 아니라 이 덮어쓰기 조건에서 나온다⁶.
그래프에 고리가 있어도 상태에는 없을 수 있다. 플로이드–워셜은 고리가 있는 그래프에서도 돈다. 상태 (k, i, j)가 늘 k − 1 단계만 읽어서, 상태끼리는 고리가 없다. 벨만–포드도 “간선 t개 이하로 v까지 가는 최소 비용”을 상태로 두면 t − 1 단계만 읽는다⁶.

이 연결로 얻는 것

수학에서 알고리즘으로:

순서 판정 하나. “점화식이 읽는 칸이 모두 앞에 있나”만 보면 된다. 동전 문제가 x를 1부터 올라가는 것, 구간 DP가 짧은 구간부터 채우는 것, 트리 DP가 자식부터 계산하는 것, 플로이드–워셜이 k를 바깥 반복에 두는 것(플로이드–워셜의 확인 문제 C3)이 모두 이 판정 하나로 설명된다. 플로이드–워셜은 k마다 표를 따로 둔 상태 (k, i, j)로 볼 때 그렇다. k를 안쪽에 두면 (k, i, j)가 읽는 (k − 1, i, k)가 k > j일 때 아직 비어 있다.
늘 커지는 값을 찾으면 순서가 나온다. 화살표를 따라가면 늘 커지는 값 f가 있으면, f가 작은 칸부터 채우는 것이 곧 선형 확장이다. f가 같은 칸끼리는 서로 갈 수 없어 아무 순서로 채워도 된다. f가 있다는 것은 고리가 없다는 증명도 된다. 고리를 한 바퀴 돌면 f(a) < … < f(a)가 되어 모순이기 때문이다. 코딩 테스트 공부에서는 알고력 a와 코딩력 c가 줄지 않는다. 제자리로 돌아오는 경우를 빼면 둘 중 하나는 꼭 늘어나니 a + c가 이런 값이다. 그래서 (a, c)를 사전 순으로 돌아도, a + c가 작은 칸부터 돌아도 같은 답이 나온다.
고리가 있으면 다른 길을 고른다. 위상 정렬이 없으니 어떤 순서로도 칸마다 한 번씩 채워 끝낼 수 없다. 쓰는 길은 셋이다⁶.
1. 늘 커지는 차원을 상태에 더한다. 플로이드–워셜의 k, 벨만–포드의 간선 수 t가 이것이다.
2. 비용이 0 이상이면 다익스트라가 가까운 칸부터 확정하며 순서를 찾아 간다. 네 방향으로 움직이는 격자는 이웃 칸끼리 서로 읽어 고리가 생긴다. 가운데 줄의 왼쪽 두 칸만 9이고 나머지는 1인 3 × 3 격자에서, 왼쪽 위부터 왼쪽 아래까지 지나는 칸(처음과 끝 포함)의 합을 가장 작게 한다. 행 순서로 한 번 훑으면 칸마다 위·왼쪽 이웃만 읽게 되어 왼쪽 아래 칸이 11이 된다. 하지만 오른쪽으로 돌아가는 길이 있어 답은 7이다.
3. 가장 작은 비용을 구할 때, 제자리로 돌아오는 화살표(길이 1인 고리)는 비용이 음수가 아니면 답을 줄이지 못하니 뺀다. 코딩 테스트 공부에서 보상이 0이거나 이미 목표인 경우를 건너뛰는 까닭이다.

알고리즘에서 수학으로:

DFS를 화살표 반대로 돌면 뒤집지 않아도 된다. 기억하기 재귀는 화살표를 거슬러(읽는 쪽으로) 도는 DFS다. 읽을 칸을 모두 끝낸 뒤 자기를 끝내니, 끝내는 순서를 그대로 쓰면 선형 확장이다. 칸 알고리즘처럼 시작값(극소 원소)이 먼저 나온다. DFS로 위상 정렬을 구할 때 “끝나는 순서를 거꾸로” 하는 것은 화살표를 “먼저 → 나중” 방향으로 따라가기 때문이다¹.
필요한 부분만 줄 세우기. 기억하기 재귀는 목표에서 화살표를 거슬러 닿는 칸, 곧 목표와 목표보다 앞서야 하는 칸만 계산한다. 동전이 3원·4원이고 목표가 6원이면 dp[6], dp[3], dp[2], dp[0] 네 칸만 계산한다. 3원 쪽을 먼저 읽으면 끝내는 순서는 dp[0], dp[3], dp[2], dp[6]이다. dp[1], dp[4], dp[5]는 6원과 상관이 없다.

전이 문제

라면을 끓이는 여섯 단계가 있다. 단계마다 1분이 걸린다⁷.

단계	먼저 끝나 있어야 하는 단계
물 끓이기	없음
파 썰기	없음
면 넣기	물 끓이기
스프 넣기	물 끓이기
파 올리기	면 넣기, 파 썰기
그릇에 담기	스프 넣기, 파 올리기

혼자 한다면 가능한 순서를 두 가지 적고, 모두 몇 가지인지 세라.
일손이 넉넉해서 서로 기대지 않는 단계는 동시에 할 수 있다. 최소 몇 분에 끝나는지 DP로 구하라.
“물은 파를 올린 뒤에 끓인다”는 조건을 더하면 어떻게 되는가?

답

예: 물, 파 썰기, 면, 스프, 파 올리기, 담기. 또는 파 썰기, 물, 스프, 면, 파 올리기, 담기. 모두 11가지다.
단계 v가 끝나는 가장 이른 분 t(v) = 1 + (v보다 먼저 끝나야 하는 단계들의 t 중 최댓값)이다. 그런 단계가 없으면 1이다. 선형 확장 순서로 채우면 물 1, 파 썰기 1, 면 2, 스프 2, 파 올리기 3, 담기 4라서 4분이다. 물 → 면 → 파 올리기 → 담기는 하나씩 차례로 해야 하니 4분보다 빠를 수 없다. 단계마다 t(v)분째에 하면 4분에 끝난다.
물 → 면 → 파 올리기 → 물 고리가 생긴다. 줄을 세울 수 없다. 칸 알고리즘은 파 썰기만 꺼내고 나머지 다섯 단계를 남긴다. 기억하기 재귀로 t를 구하면 끝없이 돈다.

확인 문제

C1 구간 DP 표를 끝점 j가 작은 것부터, 같은 j 안에서는 시작점 i가 큰 것부터 채워도 되는가? j도 i도 작은 것부터 채우면 어떤가?

답: 앞의 것은 된다. dp[i][j]는 dp[i][m](m < j)과 dp[m+1][j](시작점 m + 1 > i)를 읽는다. 앞의 칸은 j가 더 작아 먼저 채워졌다. 뒤의 칸은 같은 j 안에서 시작점이 더 커서 먼저 채워졌다. 뒤의 것은 안 된다. 같은 j 안에서 i가 작은 것부터 가면 dp[m+1][j]가 아직 비어 있다. 예를 들어 dp[1][2]를 구할 때 dp[2][2]가 없다. 흔한 오답은 “길이 순서만 된다”이다. 읽는 칸이 모두 앞에 있으면 어느 순서든 된다.

C2 트리 DP처럼 “뿌리부터 방문한 순서를 거꾸로” 채우면 틀리는 예를, 나무가 아닌 의존 그래프로 들어라.

답: 목표 g가 a와 b를 읽고, a도 b를 읽는다. g에서 b를 먼저 방문하면 방문 순서는 g, b, a이고, 거꾸로 하면 a, b, g다. a를 구할 때 b가 아직 없다. g와 a가 b를 함께 읽어서 생긴 일이다. 나무에서는 칸마다 그 칸을 읽는 부모가 하나라 이런 일이 없다. 방문 순서 대신 재귀가 끝내는 순서(b, a, g)를 쓰면 맞는다.

C3 기억하기 재귀가 칸을 끝내는 순서는 그대로 써야 위상 정렬인가, 거꾸로 해야 하는가? DFS로 위상 정렬을 구할 때 “끝나는 순서를 거꾸로” 하는 것과 무엇이 다른가?

답: 그대로 쓴다. 기억하기 재귀는 화살표를 거슬러 그 칸이 읽는 칸 쪽으로 내려가고, 읽을 칸을 다 끝낸 뒤에 자기를 끝낸다. 그래서 먼저 와야 할 칸이 먼저 끝난다. DFS 위상 정렬은 화살표를 “먼저 → 나중” 방향으로 따라가서 나중 것이 먼저 끝나니 거꾸로 한다. 흔한 오답은 기억하기의 끝내는 순서도 뒤집는 것이다. 그러면 시작값이 맨 뒤로 간다.

검증: 동전 표와 dp[6]이 읽는 칸, 1원이 있으면 순서가 한 가지뿐인 것, 동전 3원·4원의 극소 원소와 기억하기가 계산하는 네 칸, 비교 표의 순서와 16가지·3가지를 맞췄다. 구간 DP의 다섯 가지 순서를 행렬 8개까지 판정하고, 무작위 1,500개에서 맞는 순서는 전수 탐색과 같은 답을, 틀린 순서는 빈 칸을 읽는 것을 확인했다. 무작위 DAG 2,000개에서 기억하기가 끝내는 순서는 그대로, 화살표 방향 DFS가 끝나는 순서는 거꾸로 해야 선형 확장이었다. 나무의 방문 순서 거꾸로, C2의 반례, 고리의 RecursionError, 배낭의 6과 3, 격자의 11과 7, 플로이드–워셜·벨만–포드 상태에 고리가 없음, 코딩 테스트 공부의 두 순서와 다익스트라가 무작위 600개에서 같음, 늘 커지는 값의 순서, 플로이드–워셜 상태를 k 순서로 채우면 선형 확장이고 k를 안쪽에 두면 아님, 트리 DP의 극소 원소가 잎, 칸 알고리즘 순서로 센 길의 수, 전이 문제의 11가지·4분·고리도 확인했다. 모두 실험으로 확인한 것이고, 순서 판정과 늘 커지는 값의 근거는 본문에 있다 — 41_toposort-dp-order_verify.py

Cormen 외, Introduction to Algorithms 3판, 15.1절의 “Subproblem graphs”: 부분 문제마다 점을 두고, 한 부분 문제를 풀 때 바로 쓰는 부분 문제 쪽으로 화살표를 긋는다. 아래에서부터 채우는 순서는 이 그래프의 거꾸로 된 위상 정렬이고, 위에서부터 기억하기는 이 그래프의 깊이 우선 탐색이다. 화살표 방향이 이 문서와 반대라서 “거꾸로”가 붙는다. 위상 정렬과 DFS의 끝나는 순서는 22.4절 “Topological sort”. ↩ ↩²
Lehman·Leighton·Meyer, Mathematics for Computer Science, 10장 “Directed graphs & Partial Orders”(DAG의 도달 관계가 엄격한 부분순서, 위상 정렬). ↩
구간 DP를 시작점이 큰 것부터 또는 끝점 순으로 채우는 순서, 행렬 3개 구간 DP의 순서 16가지, 기억하기 재귀가 끝내는 순서가 그대로 선형 확장이라는 것, 늘 커지는 값으로 순서를 정하는 방법은 위 출처의 정리를 볼트의 문서들에 맞춰 풀어 쓴 것이다. 41_toposort-dp-order_verify.py에서 전수와 무작위 입력으로 확인했다. ↩ ↩²
Laaksonen, Competitive Programmer’s Handbook (2018년 7월판), 16.1 “Topological sorting”(세 상태 DFS, 끝나는 순서를 거꾸로), 16.2 “Dynamic programming”(사이클 없는 그래프에서 위상 정렬 순서로 길의 수와 최단·최장 경로를 구한다. DP 문제를 상태를 점으로 하는 사이클 없는 그래프로 나타내는 예로 동전 {1, 3, 4}, 6원을 든다). ↩
‘먼저 비교해 보기’ 왼쪽 열의 칸 여섯 개와 ‘[A,B,C]를 구할 때 [A]와 [B,C], [A,B]와 [C]를 읽는다’는 의존 관계, 구간 DP의 점화식이 읽는 칸을 화살표로 그렸다. ↩
1차원 배낭의 덮어쓰기 조건, 벨만–포드를 “간선 t개 이하”로 둔 상태, 고리를 푸는 세 가지 길, 네 방향 격자의 예는 이 문서에서 보탠 설명이다. 같은 검증 코드에서 수를 맞췄다. ↩ ↩² ↩³
라면 단계와 의존 관계는 예로 지어낸 것이다. 순서의 개수, 최소 시간, 고리는 검증 코드로 셌다. ↩