그리디·동적 계획법·환원 (Greedy, dynamic programming, reductions)

Opening Hook: 세 단어로 시작하기

오늘 단원의 핵심은 세 동사입니다. Greedy는 choose now, dynamic programming(Dynamisches Programmieren, DP)은 remember subanswers, reduction(Reduktion)은 translate problem입니다. 초보자가 가장 많이 하는 실수는 이 세 방법을 모두 '빠른 알고리즘 이름'으로 외우는 것입니다. 하지만 시험 답안에서 중요한 것은 이름이 아니라 의무입니다. Greedy를 썼다면 왜 지금 고른 선택이 안전한지(safe) 보여야 합니다. DP를 썼다면 table entry 하나가 무슨 뜻인지, 어떤 순서로 채우는지, 왜 Laufzeit가 그렇게 되는지 보여야 합니다. Reduction을 썼다면 어느 문제 A의 입력을 어느 문제 B의 입력으로 바꾸는지, 그 방향이 어떤 결론을 주는지 보여야 합니다.

이 단원을 하나의 지도처럼 보면 쉽습니다. 문제를 보고 '매 단계에서 하나의 선택을 확정해도 될 것 같은가?'라고 느끼면 Greedy 후보입니다. 그러나 후보일 뿐입니다. 바로 증명 gate가 열립니다. '작은 부분문제들이 반복되어 같은 값을 여러 번 계산하는가?'라고 느끼면 DP 후보입니다. 이때는 state gate가 열립니다. '내가 직접 풀기 어렵지만 이미 아는 문제 solver를 빌릴 수 있는가?'라고 느끼면 reduction 후보입니다. 이때는 arrow gate, 즉 \(A \le_{p} B\)A ≤p B의 방향 gate가 열립니다.

구두시험 첫 문장: Greedy는 안전한 local choice, DP는 저장되는 subproblem answer, reduction은 \(A \text{입력} \rightarrow B \text{입력}\)A input → B input방향을 먼저 말하겠습니다.

선수 개념과 필수 용어 지도(Prerequisites and Vocabulary Map)

필수 배경은 네 묶음입니다. 첫째, asymptotic notation입니다. DP의 Laufzeit를 말할 때 #states와 transition cost를 곱하고, Greedy graph algorithms의 Laufzeit를 말할 때 |V|, |E|, log |V| 같은 기호를 씁니다. 둘째, graph vocabulary입니다. Dijkstra, Prim, Kruskal은 모두 \(\text{graph} G=(V,E), \text{edge} \text{weight} w(e), \text{priority} \text{queue}\)graph G=(V,E), edge weight w(e), priority queue또는 sorted edge list를 사용합니다. 셋째, recurrence와 table 사고입니다. DP는 recurrence를 table로 바꾼다고 보면 되지만, 모든 recurrence가 DP 답안이 되는 것은 아닙니다. 넷째, correctness proof vocabulary입니다. safe edge, greedy-choice property, exchange argument, invariant, optimal substructure 같은 말이 답안의 뼈대입니다.

용어 지도는 이렇게 잡으세요. Greedy-Algorithmus는 \(\text{solution} x=(x1,...,\text{xn})\)solution x=(x1,...,xn)을 만들 때 이미 만든 prefix x1,...,x(i-1)에 locally best candidate xi를 붙입니다. greedy-choice property는 그런 선택을 포함하는 optimal solution이 존재한다는 성질입니다. exchange argument는 어떤 optimal solution O에 greedy choice g가 없을 때 O에서 e를 빼고 g를 넣어 O'=O-e+g를 만들어도 feasible이고 cost가 나빠지지 않음을 보이는 증명 틀입니다. DP에서 state는 D[i][j] 같은 table cell의 의미입니다. transition은 predecessor states에서 current state로 오는 규칙입니다. \(\text{Reduction} A \le_{p} B\)Reduction A ≤p B는 A instance x를 polynomial time transformation f로 B instance f(x)로 바꾸고 B solver의 답을 A answer로 해석한다는 뜻입니다.

• 탐욕법 용어(Greedy terms): 지역 선택(local choice), 안전한 선택(safe choice), 탐욕 선택 속성, 교환 논증, 절단·가벼운 간선
• 동적 계획법 용어(DP terms): 상태, 경계값, 전이, 계산 순서, 정답 칸, 복원, 메모이제이션
• 환원 용어(Reduction terms): 문제 사례(instance), 변환 f, B 풀이기, \(A \le_{p} B, B\)A ≤p B, B가 쉬우면 A도 쉬움, A가 어려우면 B도 어려움
• 강의 출처: Lecture 07의 52~72쪽은 DP, 73~81쪽은 탐욕법과 반례, Lecture 06 그래프 구간은 MST·Dijkstra의 근거입니다.

Part I: Greedy는 선택보다 증명이다

Lecture 07은 Greedy의 원리를 'Teillösung에 locally cheapest-looking candidate를 붙여 \(\text{solution} x=(x1,...,\text{xn})\)solution x=(x1,...,xn)을 만든다'고 설명합니다. 이 문장만 보면 Greedy는 쉬워 보입니다. 하지만 시험에서 Greedy는 항상 두 층으로 답해야 합니다. 첫 층은 rule입니다. 예를 들어 Kruskal은 edge를 weight 오름차순으로 보고 cycle을 만들지 않는 edge를 넣습니다. Prim은 현재 자란 tree frontier에서 가장 가벼운 edge를 통해 새 vertex를 붙입니다. Dijkstra는 아직 확정하지 않은 vertex 중 dist가 가장 작은 vertex를 extract-min합니다. 두 번째 층은 proof obligation입니다. 왜 이 선택을 지금 확정해도 뒤에서 후회하지 않는가?

Greedy correctness의 직관은 '나중에 고칠 필요가 없는 선택'입니다. MST에서는 cut을 가로지르는 가장 가벼운 edge(light edge)가 safe하다는 cut property가 이 역할을 합니다. 어떤 MST가 그 light edge를 포함하지 않아도, 그 MST에 light edge를 추가하면 cycle이 생기고, 그 cycle 안에서 cut을 가로지르는 다른 edge 하나를 제거할 수 있습니다. light edge가 가장 가볍기 때문에 총 weight는 증가하지 않습니다. 그래서 greedy choice를 포함하는 MST가 존재합니다. 이것이 exchange argument의 감각입니다.

Dijkstra는 조금 다릅니다. extract-min vertex u의 dist가 진짜 shortest distance로 확정된다는 논리가 nonnegative edge weights에 의존합니다. Lecture 06의 correctness proof는 shortest path에서 S 밖으로 처음 나가는 vertex y를 잡고, nonnegative weights 때문에 \(y.\text{dist} \le \text{shortest}(s,u) \le u.\text{dist}\)y.dist ≤ shortest(s,u) ≤ u.dist가 되어 extract-min 순서와 모순을 만드는 방식입니다. Lecture 07과 Lecture 06은 negative edge counterexample도 줍니다. 그러므로 'Dijkstra는 Greedy니까 항상 맞다'가 아니라 'nonnegative weights라는 전제 아래 extract-min이 safe하다'가 정확한 답안입니다.

Greedy 답안 템플릿: rule을 말하고, safe choice를 말하고, exchange 또는 cut/invariant로 왜 후회하지 않는지 말한다.

Part II: Greedy가 실패하는 순간을 일부러 보자

Greedy를 제대로 이해하려면 성공 예시보다 실패 예시가 더 중요할 때가 많습니다. Lecture 07의 Greedy-TSP 예시는 이 단원의 보석입니다. TSP는 모든 vertex를 정확히 한 번 방문하고 시작점으로 돌아오는 minimum-weight tour를 찾는 문제입니다. nearest-neighbor greedy는 현재 vertex에서 아직 방문하지 않은 vertex로 가는 가장 작은 weight edge를 고릅니다. 이 rule은 매우 자연스럽지만 optimality proof가 없습니다.

Lecture 07의 counterexample family에서는 vertex가 1,2,...,n이고, consecutive edge는 weight 1, edge {1,n}은 매우 큰 N, 나머지는 weight 2로 둡니다. 시작점이 1이면 greedy는 \(1\rightarrow 2\rightarrow ...\rightarrow n\)1→2→...→n으로 계속 weight 1 edge를 따라갑니다. 마지막에는 n에서 1로 돌아가야 하므로 비싼 N edge를 써서 total N+n-1이 됩니다. 반면 optimal tour는 큰 edge를 피하고 weight 2 edge 몇 개를 섞어 n+2 정도로 만들 수 있습니다. N을 마음대로 크게 잡을 수 있으므로 greedy는 arbitrarily bad가 됩니다.

이 예시는 MC 함정에서 자주 쓰입니다. 'locally best choice가 global optimum을 보장한다'는 말은 false입니다. 'Greedy는 빠르기 때문에 근사적으로라도 항상 좋다'도 course-specific claim으로 말하면 위험합니다. Lecture 07은 Greedy-TSP가 너무 greedy하다고 보여 주고, 이어서 Hill-Climbing과 Simulated Annealing 같은 metaheuristics를 Greedy와 구분합니다. Greedy는 exact correctness proof가 있으면 exact algorithm이고, proof가 없으면 단지 heuristic candidate입니다.

반례 문장: nearest-neighbor TSP는 매번 가장 싼 edge를 골라도 마지막 return edge 때문에 N+n-1이 되어 optimum n+2보다 훨씬 나빠질 수 있다.

Part III: DP는 table을 그리는 기술이 아니라 state를 정의하는 기술이다

Lecture 07은 DP 원리를 'overlapping subproblems를 재귀적으로 풀고 Zwischenergebnisse를 다시 사용한다(Memoization)'고 설명합니다. 처음에는 Fibonacci 예시가 나옵니다. naive Fib-Rek(n)은 Fib(n-1)과 Fib(n-2)를 계속 호출하고, 같은 Fib(k)를 여러 번 계산해서 대략 exponential tree가 생깁니다. Memoization을 쓰면 한 번 계산한 F[i]를 저장하고 다시 호출될 때 바로 반환합니다. 그래서 \(\Theta(n)\)Θ(n)이 됩니다. 이 예시는 DP의 감각을 잡기 좋지만, 시험 답안은 Fibonacci보다 더 엄격해야 합니다.

DP 답안의 첫 문장은 거의 항상 'D[...]는 무엇을 의미한다'입니다. 이 문장이 흐리면 transition이 아무리 그럴듯해도 점수가 흔들립니다. Minimum Edit Distance에서 D[i][j]는 X[1..i]를 Y[1..j]로 바꾸는 minimum edit cost입니다. Matrix-chain multiplication에서 D[i,j]는 \(\text{matrix} A_{i}...A_{j}\)matrix Aᵢ...Aⱼ를 곱하는 minimum scalar multiplication cost입니다. 둘 다 2D table이지만 의미가 완전히 다릅니다. 그러므로 table의 차원이 같다고 같은 runtime이라고 말하면 안 됩니다.

DP는 여섯 가지 항목으로 답합니다. state meaning, boundary/base case, transition, evaluation order, answer cell, Laufzeit/space입니다. Minimum Edit Distance는 \(D[0][j]=j, D[i][0]=i\)D[0][j]=j, D[i][0]=i라는 boundary가 있고, D[i][j]는 diagonal/up/left 셋 중 minimum입니다. order는 \(i=1..m, j=1..n\)i=1..m, j=1..n으로 위와 왼쪽과 대각선이 이미 계산된 상태를 보장합니다. answer cell은 D[m][n]입니다. states는 (m+1)(n+1), transition은 \(O(1)\)O(1)이므로 \(\Theta(\text{mn})\)Θ(mn)입니다.

DP 답안 템플릿: state, base, recurrence, fill order, answer, runtime/space를 빠짐없이 말한다.

4부: 최소 편집 거리(Minimum Edit Distance) 풀이

Minimum Edit Distance(Levenshtein-Distanz)는 한 string X를 다른 string Y로 바꾸기 위해 필요한 insert, delete, substitute의 최소 개수를 묻습니다. Lecture 07은 X='ein Test', Y='zwei Feste' 예시와 함께 table을 보여 줍니다. 수업의 핵심은 final number만 외우는 것이 아니라 cell 하나가 어떻게 만들어지는지 이해하는 것입니다.

D[i][j]를 X[1..i]를 Y[1..j]로 바꾸는 최소 cost라고 합시다. 마지막 operation을 생각하면 세 경우가 있습니다. 마지막에 X[i]와 Y[j]를 맞춘다면 이전에는 X[1..i-1]을 Y[1..j-1]로 바꿨어야 하고, cost는 D[i-1][j-1]+s입니다. 여기서 \(s=0 \text{if} X[i]=Y[j], \text{else} 1\)s=0 if X[i]=Y[j], else 1입니다. 마지막에 X[i]를 delete했다면 이전에는 X[1..i-1]을 Y[1..j]로 바꿨고 cost는 D[i-1][j]+1입니다. 마지막에 Y[j]를 insert했다면 이전에는 X[1..i]를 Y[1..j-1]로 바꿨고 cost는 D[i][j-1]+1입니다. 따라서 \(D[i][j]=\min\{D[i-1][j-1]+s, D[i-1][j]+1, D[i][j-1]+1\}\)D[i][j]=min{D[i-1][j-1]+s, D[i-1][j]+1, D[i][j-1]+1}입니다.

작은 예시로 X='ab', Y='ac'를 보겠습니다. boundary는 \(D[0][0]=0, D[1][0]=1, D[2][0]=2, D[0][1]=1, D[0][2]=2\)D[0][0]=0, D[1][0]=1, D[2][0]=2, D[0][1]=1, D[0][2]=2입니다. D[1][1]은 a와 a가 같아서 \(\min\{0+0,1+1,1+1\}=0\)min{0+0,1+1,1+1}=0입니다. D[1][2]는 a와 c가 다르므로 \(\min\{1+1,2+1,0+1\}=1\)min{1+1,2+1,0+1}=1입니다. D[2][1]은 b와 a가 다르므로 \(\min\{1+1,0+1,2+1\}=1\)min{1+1,0+1,2+1}=1입니다. D[2][2]는 b와 c가 다르므로 \(\min\{0+1,1+1,1+1\}=1\)min{0+1,1+1,1+1}=1입니다. 답은 \(\text{substitute} b\rightarrow c\)substitute b→c하나, 즉 1입니다.

Part V: Matrix-chain multiplication이 왜 2D인데 \(\Theta(n^{3})\)Θ(n³)인가

Matrix-chain multiplication은 DP runtime 함정을 잡기에 좋습니다. 여러 matrix A1...An을 같은 순서로 곱되 괄호를 어떻게 치느냐에 따라 scalar multiplication 수가 달라집니다. Lecture 07 pages 28-37은 이 DP를 다룹니다. 여기서 state D[i,j]는 A(i)...A(j)를 곱하는 최소 cost입니다. base는 \(D[i,i]=0\)D[i,i]=0입니다. matrix 하나는 이미 있으므로 곱셈 cost가 없습니다.

Transition은 마지막 split을 고르는 방식입니다. 구간 A(i)...A(j)를 마지막에 (A(i)...A(k))와 (A(k+1)...A(j))로 나누어 곱한다고 합시다. 왼쪽 최소 cost는 D[i,k], 오른쪽 최소 cost는 D[k+1,j]입니다. 두 결과 matrix를 마지막으로 곱하는 cost는 dimensions p(i-1)·p(k)·p(j)입니다. 그래서 모든 k in [i, j-1]에 대해 D[i,k]+D[k+1,j]+p(i-1)·p(k)·p(j)를 계산하고 minimum을 취합니다.

여기서 중요한 시험 포인트가 나옵니다. table cell은 \(O(n^{2})\)O(n²)개입니다. 하지만 cell 하나를 채울 때 split k를 \(O(n)\)O(n)개 시도합니다. 따라서 total Laufzeit는 \(\Theta(n^{3})\)Θ(n³)입니다. Minimum Edit Distance도 2D table이지만 cell 하나에서 후보가 diagonal/up/left 세 개뿐이어서 \(O(1)\)O(1)입니다. 그러므로 '2D DP table이면 \(\Theta(n^{2})\)Θ(n²)'라는 MC 문장은 false입니다. 정확한 계산은 #states * transition cost입니다.

Part VI: Reduction은 문제를 푸는 방향 화살표다

Reduction(Reduktion)은 이 페이지에서 가장 source gap이 있는 부분입니다. 현재 indexed Lecture 07 chunks는 DP와 Greedy를 자세히 다루고, TSP가 어렵다는 말 뒤에 NP chapter로 넘어간다고 안내하지만, reduction lecture 전체는 이 자료 조각 안에 충분히 들어 있지 않습니다. 그래서 여기서는 course-specific reduction theorem을 새로 꾸며 내지 않고, AUD 시험에서 일반적으로 필요한 방향 논리만 명확히 둡니다.

\(A \le_{p} B\)A ≤p B는 A가 B로 polynomial-time reducible하다는 뜻입니다. 읽는 법은 'A를 풀기 위해 B solver를 빌린다'입니다. 입력 x는 A의 instance입니다. 우리는 x를 빠르게 f(x)로 바꿉니다. f(x)는 B의 instance여야 합니다. 그 다음 B solver를 호출합니다. 마지막으로 B의 yes/no 또는 solution을 A의 answer로 해석합니다. 그림으로는 \(A \text{입력} \rightarrow \text{transform} f \rightarrow B \text{입력} \rightarrow \text{solve}_{B} \rightarrow A \text{answer}\)A input → transform f → B input → solve(B) → A answer입니다.

결론 방향도 이 화살표에서 나옵니다. 만약 B가 쉽다면(B in P), A도 쉽습니다. 왜냐하면 A를 풀 때 transformation f와 B solver를 차례로 쓰면 되기 때문입니다. 반대로 A가 어렵다는 사실이 이미 알려져 있고 \(A \le_{p} B\)A ≤p B를 보였다면, B도 적어도 A만큼 어렵습니다. 만약 B가 쉬웠다면 A도 쉬워져야 하므로 모순이 됩니다. 하지만 B가 어렵다고 해서 A가 어렵다는 결론은 일반적으로 나오지 않습니다. 또한 \(A \le_{p} B\)A ≤p B를 \(B \le_{p} A\)B ≤p A로 뒤집으면 완전히 다른 주장입니다.

Reduction 답안 첫 줄: A instance x를 polynomial time에 B instance f(x)로 바꾸고, B solver의 답을 A의 답으로 해석한다.

Worked Example 1: design paradigm 분류하기

문제 상황을 세 개 보겠습니다. 상황 A: connected undirected graph에서 MST를 만들고 싶고, 매 단계에서 cut을 가로지르는 가장 가벼운 edge를 고릅니다. 이것은 Greedy 후보입니다. 답안은 'Prim/Kruskal style greedy'라고만 쓰면 부족합니다. light edge가 safe하다는 근거, 즉 cut/exchange intuition을 붙여야 합니다. 상황 B: 두 string X와 Y가 있고, X[1..i]를 Y[1..j]로 바꾸는 minimum cost를 D[i][j]에 저장합니다. 이것은 DP입니다. 답안은 \(\text{state}, \text{boundary} D[0][j]=j\)state, boundary D[0][j]=j와 \(D[i][0]=i, \text{diagonal}/\text{up}/\text{left} \text{transition}, \text{answer} D[m][n], \Theta(\text{mn})\)D[i][0]=i, diagonal/up/left transition, answer D[m][n], Θ(mn)을 말해야 합니다. 상황 C: 문제 A를 직접 풀기 어렵지만 A의 입력 x를 문제 B 입력 f(x)로 바꾼 뒤 B solver를 쓰려 합니다. 이것은 reduction입니다. 답안은 \(A \le_{p} B\)A ≤p B방향입니다.

이 worked example의 목적은 이름 맞히기가 아닙니다. 각 방법의 '검사 질문'을 붙이는 연습입니다. Greedy 검사 질문은 '지금 선택을 포함하는 optimal solution이 있음을 어떻게 보이나?'입니다. DP 검사 질문은 'table cell 하나가 무슨 뜻이고, predecessor states가 이미 계산되어 있나?'입니다. Reduction 검사 질문은 '어느 입력에서 어느 입력으로 가고, easy/hard conclusion을 어느 방향으로 읽나?'입니다.

분류 문제에서는 paradigm 이름 + 답안 의무를 같이 적어야 부분점수가 안정적입니다.

Worked Example 2: Edit Distance table 일부 채우기

X='cat', Y='cut'로 손계산을 해 봅시다. goal은 cat을 cut으로 바꾸는 최소 edit cost입니다. boundary는 빈 string에서 prefix를 만드는 cost입니다. \(D[0][0]=0, D[0][1]=1, D[0][2]=2, D[0][3]=3\)D[0][0]=0, D[0][1]=1, D[0][2]=2, D[0][3]=3이고 \(D[1][0]=1, D[2][0]=2, D[3][0]=3\)D[1][0]=1, D[2][0]=2, D[3][0]=3입니다. 이제 D[1][1]은 c와 c가 같으므로 0입니다. D[1][2]는 c와 u가 다르므로 \(\min\{D[0][1]+1=2, D[0][2]+1=3, D[1][1]+1=1\}=1\)min{D[0][1]+1=2, D[0][2]+1=3, D[1][1]+1=1}=1입니다. D[1][3]도 \(\min\{3,4,2\}=2\)min{3,4,2}=2입니다.

두 번째 row에서 D[2][1]은 a와 c가 다르므로 \(\min\{2,1,3\}=1\)min{2,1,3}=1입니다. D[2][2]는 a와 u가 다르므로 \(\min\{D[1][1]+1=1, D[1][2]+1=2, D[2][1]+1=2\}=1\)min{D[1][1]+1=1, D[1][2]+1=2, D[2][1]+1=2}=1입니다. D[2][3]은 a와 t가 다르므로 \(\min\{2,3,2\}=2\)min{2,3,2}=2입니다. 세 번째 row에서 D[3][1]은 t와 c가 달라 2, D[3][2]는 t와 u가 달라 2, D[3][3]은 t와 t가 같아서 \(\min\{D[2][2]+0=1, D[2][3]+1=3, D[3][2]+1=3\}=1\)min{D[2][2]+0=1, D[2][3]+1=3, D[3][2]+1=3}=1입니다. 답은 1, 즉 a를 u로 substitute하는 것입니다.

시험에서 table 전체를 그리라고 하지 않아도, 한 cell을 왜 그렇게 채우는지 말할 수 있어야 합니다. 특히 copy/substitution은 diagonal, deletion은 up, insertion은 left라는 predecessor 의미를 말하면 계산 실수도 줄어듭니다.

Proof Intuition: Greedy proof와 DP proof를 구분하기

Greedy proof와 DP proof는 둘 다 optimality를 다루지만 모양이 다릅니다. Greedy proof는 '첫 선택을 greedy choice로 고정해도 optimal solution을 잃지 않는다'를 보입니다. 그래서 exchange argument가 자주 등장합니다. 이미 optimal인 O가 greedy choice g를 포함하지 않는다고 가정하고, O 안의 어떤 element e를 g로 바꾸어도 feasibility가 유지되고 objective가 악화되지 않음을 보입니다. 이 증명이 끝나면 첫 선택을 고정하고 남은 subproblem으로 넘어갈 수 있습니다.

DP proof는 보통 optimal substructure와 recurrence correctness입니다. 예를 들어 Edit Distance에서 optimal sequence의 마지막 operation을 보아 copy/substitution, deletion, insertion 중 하나라고 분해합니다. 각 경우의 이전 상태가 정확히 D[i-1][j-1], D[i-1][j], D[i][j-1]이므로 minimum을 취하면 optimal cost가 됩니다. Matrix-chain에서는 optimal parenthesization의 마지막 split k가 반드시 하나 존재하고, 그 왼쪽과 오른쪽도 각각 optimal이어야 합니다. 그렇지 않으면 더 싼 부분해로 바꾸어 전체 cost를 줄일 수 있기 때문입니다.

Reduction proof는 또 다릅니다. algorithm의 step-by-step correctness보다 transformation correctness입니다. x가 A의 yes-instance iff f(x)가 B의 yes-instance라는 식의 iff를 보이거나, B solution을 A solution으로 복원하는 해석을 보입니다. 현재 source에서는 reduction 세부 예제가 부족하므로, 이 페이지에서는 방향과 결론을 중심으로만 학습합니다.

Greedy proof는 첫 선택의 안전성, DP proof는 recurrence의 완전성, reduction proof는 변환의 iff/해석을 보인다.

Misconceptions: 초보자가 꼭 지워야 할 오해

첫째, Greedy는 '빠르고 간단한 알고리즘'이 아닙니다. 빠른 구현일 수는 있지만, 정확한 Greedy algorithm으로 인정받으려면 local choice가 safe하다는 증명이 있어야 합니다. 둘째, DP는 'recurrence가 있으면 다 DP'가 아닙니다. DP는 overlapping subproblems와 저장되는 state가 있어야 하며, table을 어떤 순서로 채울지도 말해야 합니다. 셋째, reduction은 '비슷한 문제로 비유하기'가 아닙니다. A instance를 B instance로 실제로 변환하고, B solver의 답을 A answer로 해석해야 합니다.

넷째, Dijkstra가 Greedy라는 사실은 negative edge에서도 작동한다는 뜻이 아닙니다. Lecture 07과 Lecture 06은 negative edge counterexample를 명시적으로 보여 줍니다. 다섯째, Greedy와 DP 모두 optimal substructure를 이야기할 수 있지만 결론은 다릅니다. DP로 optimal하게 풀 수 있다고 해서 Greedy도 항상 optimal한 것은 아닙니다. exam memory protocol에도 'DP로 optimal하게 풀 수 있으면 Greedy도 항상 optimal' 같은 trap이 등장합니다. 여섯째, 2D DP table은 자동으로 \(\Theta(n^{2})\)Θ(n²)이 아닙니다. Matrix-chain처럼 cell마다 split을 \(O(n)\)O(n)개 보면 \(\Theta(n^{3})\)Θ(n³)입니다. 일곱째, \(A \le_{p} B\)A ≤p B에서 'B가 어렵다'만 보고 A가 어렵다고 말하면 방향 오류입니다.

오해 제거 문장: paradigm 이름은 결론이 아니라 시작점이며, 각 paradigm마다 별도 증명 또는 구조 의무가 있다.

반례로 바로잡는 객관식 함정(MC Trap Clinic)

MC 문제는 보통 정확한 설명을 살짝 뒤집습니다. 'Dynamisches Programmieren은 naive recursive algorithm이 같은 Teilproblem을 여러 번 풀 때 효율적이다'는 맞는 방향입니다. 하지만 'Dynamisches Programmieren은 non-overlapping subproblems를 전제로 한다'는 false입니다. non-overlapping은 Divide and Conquer 쪽 설명에 더 가깝고, DP는 overlapping subproblems를 재사용합니다. 'Sowohl DP als auch Greedy setzen optimale Teilstruktur voraus'는 조심스럽지만 대체로 맞는 형태로 나올 수 있습니다. 그러나 'DP로 optimal하게 풀 수 있으면 Greedy도 항상 optimal'은 false입니다.

Counterexample를 붙여 외우면 안전합니다. Greedy-TSP nearest neighbor는 locally cheapest edge를 계속 골라도 N+n-1이 되어 optimum n+2보다 나쁩니다. Dijkstra negative-edge graph는 \(\text{direct} \text{path} 1\rightarrow 5 \text{weight} 5\)direct path 1→5 weight 5를 확정하지만 실제 \(\text{shortest} \text{path} 1\rightarrow 2\rightarrow 4\rightarrow 3\rightarrow 5 \text{weight} 3\)shortest path 1→2→4→3→5 weight 3이 존재합니다. Matrix-chain은 2D table이지만 \(\Theta(n^{3})\)Θ(n³)입니다. Reduction은 \(A \le_{p} B\)A ≤p B와 \(B \le_{p} A\)B ≤p A를 바꾸면 다른 주장입니다. 시험장에서 option을 읽을 때는 'always', 'only', 'implies', 'must' 같은 단어를 특히 천천히 보세요.

MC option을 볼 때마다 '전제 조건, 방향, 항상/존재, runtime 계산식' 네 가지를 체크합니다.

Oral Exam Strategy: 답안을 시간별로 압축하기

60초 답안에서는 세 paradigm을 한 문장씩 말하고, 대표 trap 하나만 붙이면 됩니다. Greedy는 locally best choice를 고르되 safe proof가 필요합니다. DP는 overlapping subproblems의 answer를 state table에 저장하고 recurrence로 채웁니다. Reduction은 A input을 B input으로 바꾸어 B solver로 A를 풉니다. Trap으로는 \(\text{Dijkstra} \text{negative} \text{edge}, 2D \text{DP} \text{runtime}, A \le_{p} B \text{direction}\)Dijkstra negative edge, 2D DP runtime, A ≤p B direction중 하나를 말합니다.

3분 답안에서는 예시를 붙입니다. Greedy 예시는 Kruskal/Prim의 MST 또는 Dijkstra입니다. 단, Dijkstra는 \(w(e)\ge 0\)w(e)≥0전제를 말해야 합니다. DP 예시는 Minimum Edit Distance입니다. D[i][j]의 의미, boundary, transition, \(\Theta(\text{mn})\)Θ(mn)을 말합니다. Reduction은 source caveat를 붙여 일반 방향 논리만 설명합니다. Deep-dive 답안에서는 exchange argument, DP recurrence proof, reduction consequence를 모두 말합니다. 이때 'source-grounded caveat'를 정확히 말하는 것도 좋은 답안입니다: 현재 Lecture 07 chunks는 DP와 Greedy를 자세히 지원하지만 reduction lecture detail은 충분하지 않아서 일반 exam logic으로 다룬다고 밝힙니다.

구두 답안은 \(\text{definition} \rightarrow \text{example} \rightarrow \text{proof} \text{obligation} \rightarrow \text{trap}\)definition → example → proof obligation → trap순서로 말하면 흔들리지 않습니다.

Closing: 한 장 cheat-sheet로 압축

이 단원을 cheat-sheet 한 칸으로 줄이면 다음과 같습니다. Greedy: choose locally best candidate; must prove safe via greedy-choice property/exchange/cut; examples Dijkstra with \(w(e)\ge 0,\)w(e)≥0, Kruskal, Prim; traps negative edges and Greedy-TSP. DP: define state; fill base, transition, order, answer; runtime = #states * transition cost; examples Fibonacci memoization \(\Theta(n)\)Θ(n), Edit Distance \(\Theta(\text{mn})\)Θ(mn), Matrix-chain \(\Theta(n^{3})\)Θ(n³); traps recurrence-only answer and 2\(D=\text{quadratic}.\)D=quadratic. Reduction: \(A \le_{p} \)A ≤p B means x in A -> f(x) in B -> solve_B -> answer_A; consequences B easy => A easy and A hard => B hard; \(\text{traps} \text{reversing} \text{arrow}\quad\text{and}\quad \text{claiming} B \text{hard} \Rightarrow A \text{hard}.\)traps reversing arrow and claiming B hard => A hard.

마지막으로 스스로에게 세 질문을 던지세요. '이 Greedy 선택을 나중에 바꾸지 않아도 되는 이유는 무엇인가?' '이 DP cell은 정확히 어떤 subproblem의 answer인가?' '이 reduction arrow는 어느 입력에서 어느 입력으로 가는가?' 이 세 질문에 답할 수 있으면, 이 페이지의 초급 강의 목표는 달성된 것입니다.

마지막 기억법: 안전하게 선택하고, 상태를 기억하며, 환원 방향을 정확히 그립니다.