II-15 Divide-and-Conquer·DP·Greedy의 필요조건 — 완전 초보자 Masterclass
먼저 이 문제의 정체부터
세 패러다임은 모두 문제를 작은 구조로 보지만 성공 조건은 다릅니다. 특히 DP가 된다고 Greedy도 된다는 결론은 나오지 않습니다.
전체 여행 계획을 모든 경우 비교해 표로 저장하는 것과 매 순간 가장 가까운 곳만 고르는 것은 다른 전략입니다.
이 문항의 풀이 목표는 정답 label 암기가 아니라 다음 절차를 재현하는 것입니다. A의 only와 C의 always를 반례로 제거하고 B·D의 정의 범위를 확인합니다.
복기 시험지는 공식 답안지가 아니므로 문언과 selection rule이 충돌하면 그 사실을 표시하고 현재 강의 자료로 각 보기를 독립 검증합니다.
0. 필요한 개념을 처음부터 배우기
개념 1 · 문제의 정체를 생활 언어로
세 패러다임은 모두 문제를 작은 구조로 보지만 성공 조건은 다릅니다. 특히 DP가 된다고 Greedy도 된다는 결론은 나오지 않습니다.
이 문항에서 가장 먼저 붙잡을 문장은 'D&C runtime은 recursive calls와 divide/combine 비용 전체 recurrence에 달려 있다.'입니다. 용어를 외우기 전에 이 문장이 어떤 상황을 말하는지 작은 예를 만들어 확인합니다.
이 절에서 꼭 기억할 것
- D&C runtime은 recursive calls와 divide/combine 비용 전체 recurrence에 달려 있다.
- A의 only와 C의 always를 반례로 제거하고 B·D의 정의 범위를 확인합니다.
개념 2 · 반드시 알아야 하는 네 개의 뼈대
첫째, D&C runtime은 recursive calls와 divide/combine 비용 전체 recurrence에 달려 있다. 둘째, DP는 overlapping subproblems를 저장해 중복 계산을 줄인다.
셋째, DP와 Greedy 모두 optimal substructure를 사용하지만 Greedy에는 greedy-choice property가 추가로 필요하다. 넷째, 동적 계획법(DP)으로 풀 수 있다고 해서 탐욕법(Greedy)도 최적해를 보장하는 것은 아니다. 이 네 문장을 서로 섞지 않고 별도 체크박스로 기억해야 합니다.
이 절에서 꼭 기억할 것
- D&C runtime은 recursive calls와 divide/combine 비용 전체 recurrence에 달려 있다.
- DP는 overlapping subproblems를 저장해 중복 계산을 줄인다.
- DP와 Greedy 모두 optimal substructure를 사용하지만 Greedy에는 greedy-choice property가 추가로 필요하다.
- 동적 계획법(DP)으로 풀 수 있다고 해서 탐욕법(Greedy)도 최적해를 보장하는 것은 아니다.
개념 3 · 강의 정의를 초보자 언어로 해체
이 단원의 핵심은 '문제를 어떻게 쪼개거나 탐색하거나 고를 것인가'이다. D&C는 나눠서 재귀로 풀고 합치는 구조, DP는 같은 작은 문제를 또 풀지 않도록 기억하는 구조, Greedy는 지금 좋아 보이는 선택을 확정하는 구조, Backtracking은 선택을 해 보고 막히면 되돌리는 구조, Metaheuristic은 최적화 문제의 탐색을 일반적으로 안내하는 구조다.
분할 정복(Divide & Conquer)은 입력을 부분문제로 나누고 재귀적으로 푼 뒤 결과를 결합하며, 실행시간은 분할·재귀 호출·결합 전체의 점화식으로 결정된다. 백트래킹(Backtracking)은 해 공간을 깊이 우선 탐색처럼 따라가다가 현재 경로가 완전한 해가 될 수 없으면 결정을 취소한다. 동적 계획법(Dynamic Programming)은 겹치는 부분문제의 중간 결과를 저장하고 재사용하며 최적 부분 구조(optimal substructure)가 중요하다. 탐욕법(Greedy)은 현재 가장 유리해 보이는 후보를 고르지만 전역 최적성을 위해 별도의 탐욕 선택 성질이 필요하다. 메타휴리스틱(Metaheuristik)은 다양한 최적화 문제의 탐색을 이끄는 문제 독립적 상위 전략으로, 좋은 해를 찾을 수 있어도 보통 최적 보장은 없다.
수식으로 정확히 쓰기
핵심 규칙동적 계획법(DP)의 실행시간은 상태 수 × 상태 전이 비용으로 계산한다. 탐욕법(Greedy)의 정확성은 지역 최선 선택(local choice)만으로 보장되지 않으며, 그 선택이 안전하다는 별도 증명이 필요하다.
이 절에서 꼭 기억할 것
- 재귀 트리(recursion tree)와 점화식(recurrence)
- 최적 부분 구조(optimal substructure)와 겹치는 부분문제(overlapping subproblems)의 구분
- 지역 최적해(local optimum)와 전역 최적해(global optimum)의 구분
- 결정문제(decision problem)와 최적화 문제(optimization problem)의 구분
개념 4 · 성립 조건·불변식·경계 사례
분할 정복의 정확성은 부분문제의 해를 결합했을 때 전체 해가 되는 구조에 의존한다. 동적 계획법은 상태의 의미, 경계값, 전이, 계산 순서, 최종 답 칸, 시간·공간 복잡도를 함께 설명해야 한다. 탐욕법은 현재의 선택이 안전하다는 증명이나 강한 전제가 필요하다. 백트래킹은 visited, used, path 같은 상태를 분기 실패 뒤 정확히 되돌리는 불변식이 중요하다. 메타휴리스틱과 언덕 오르기(Hill Climbing)는 지역 최적해(local optimum)에 멈출 수 있다.
분할 정복의 부분문제가 항상 같은 크기일 필요는 없으며 QuickSort는 피벗에 따라 불균형하게 나뉠 수 있다. 분수 배낭(fractional knapsack)에 맞는 밀도 기반 탐욕 규칙이 0/1 배낭에서는 깨질 수 있다. Dijkstra는 탐욕 알고리즘이지만 음수 간선에서는 최소 거리 정점을 확정하는 선택이 안전하지 않다. 언덕 오르기는 지역 최적해, 평탄 구간(plateau), 이웃 선택에 취약하다. 백트래킹은 결정문제뿐 아니라 모든 후보를 검사하며 최선값을 갱신하는 최적화 문제에도 사용할 수 있다.
이 절에서 꼭 기억할 것
- 전제조건을 생략하지 않는다.
- 존재 명제와 모든 경우 명제를 구분한다.
- 강한 단어는 작은 반례로 우선 검사한다.
개념 5 · 실행시간과 비용을 읽는 법
분할 정복은 \(T(n)=\)T(n)=부분문제 비용의 합+분할·결합 비용과 같은 점화식으로 분석한다. 백트래킹은 최악의 경우 지수 시간이 들 수 있으며 가지치기(pruning)가 실제 탐색량을 줄인다. 동적 계획법의 실행시간은 대개 상태 수와 상태당 전이 비용의 곱이다. 최소 편집 거리(Minimum Edit Distance)는 (m+1)(n+1)개 상태와 \(O(1)\)O(1) 전이를 사용해 \(\Theta(\text{mn})\)Θ(mn)이다. 탐욕법과 메타휴리스틱의 비용은 정렬, 반복 예산, 이웃 탐색 비용 같은 구현 전제에 따라 달라진다.
O는 upper bound이고 Θ는 tight bound입니다. 자료구조 연산 비용은 ADT 이름만이 아니라 구현과 유지하는 보조 정보에 따라 달라질 수 있습니다.
이 절에서 꼭 기억할 것
- O와 Θ를 같은 뜻으로 읽지 않는다.
- 구현 의존성을 확인한다.
- 필요 없는 runtime 주장도 억지로 만들지 않는다.
개념 6 · 정확히 두 개 선택(exactly two) 판정법
선택지를 서로 비교해 '가장 그럴듯한 두 개'를 고르지 않습니다. A부터 D까지 각각 독립적인 참·거짓 명제로 바꾸고 근거 또는 반례를 붙인 뒤 참의 개수를 셉니다.
현재 복기 데이터에서 판정된 정답 표시는 B, D입니다. 정답 수와 섹션 규칙이 충돌하는 문항은 억지로 두 개를 만들지 않고 복기 문언 누락 가능성을 명시합니다.
수식으로 정확히 쓰기
핵심 규칙선택 규칙: 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
핵심 규칙검증된 선택지: B, D
이 절에서 꼭 기억할 것
- DP 가능성, optimal substructure, Greedy optimality를 서로 같은 말로 만들지 않는다.
- A의 nur는 recurrence 반례로 제거, C의 immer는 knapsack/TSP 반례로 제거, B와 D를 전제 범위 안에서 선택한다.
1. 시험장에서 따라 할 풀이 순서
선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
Divide-and-Conquer·DP·Greedy의 필요조건
D&C runtime은 recursive calls와 divide/combine 비용 전체 recurrence에 달려 있다. | DP는 overlapping subproblems를 저장해 중복 계산을 줄인다. | DP와 Greedy 모두 optimal substructure를 사용하지만 Greedy에는 greedy-choice property가 추가로 필요하다.
선택지 \(A =\)A =거짓
선택 규칙을 먼저 적는다
이 문항의 규칙은 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))입니다. 마지막에 참 개수를 반드시 재검산합니다.핵심 규칙선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))문장을 쉬운 한국어로 다시 쓴다
알고리즘 설계 패러다임에 대한 설명 중 정확히 두 개를 고르시오.
핵심 규칙Divide-and-Conquer·DP·Greedy의 필요조건
핵심 도구를 종이에 꺼낸다
A의 only와 C의 always를 반례로 제거하고 B·D의 정의 범위를 확인합니다.
핵심 규칙D&C runtime은 recursive calls와 divide/combine 비용 전체 recurrence에 달려 있다. | DP는 overlapping subproblems를 저장해 중복 계산을 줄인다. | DP와 Greedy 모두 optimal substructure를 사용하지만 Greedy에는 greedy-choice property가 추가로 필요하다.
선택지 A를 독립 판정한다
거짓이다. D&C는 부분문제를 재귀적으로 푸는 비용과 divide/combine 비용이 함께 recurrence를 이룬다. MergeSort만 봐도 두 재귀 호출과 merge 비용이 모두 들어간다.
\[선택지 A = 거짓\]선택지 A = 거짓선택지 B를 독립 판정한다
참이다. 강의와 공식 해설 모두 DP가 이미 계산한 중간 결과를 저장하고 재사용하여 Mehrfachberechnungen를 피한다고 설명한다.
\[선택지 B = 참\]선택지 B = 참선택지 C를 독립 판정한다
거짓이다. DP가 가능한 것은 subproblem structure가 있다는 뜻이지, 현재 local choice가 safe하다는 뜻이 아니다. Greedy는 별도 greedy-choice proof가 필요하고, 강의의 Greedy-TSP 및 해설의 0/1 knapsack 반례가 이를 보여준다.
\[선택지 C = 거짓\]선택지 C = 거짓선택지 D를 독립 판정한다
참으로 판정한다. 최적화 문제에서 DP는 최적해가 부분문제의 최적해로 구성되는 recurrence가 필요하고, Greedy도 local choice를 고정한 뒤 남은 subproblem이 최적 구조를 유지해야 한다. 단, 일반 교과서적으로 DP가 counting 같은 비최적화 문제에도 쓰인다는 점은 course-version note로 남긴다.
\[선택지 D = 참\]선택지 D = 참정답 수와 애매성을 재검산한다
참으로 판정된 선택지는 B, D입니다. 복기 섹션 규칙과 수가 다르면 원문 누락 가능성을 기록하고 거짓을 참으로 조작하지 않습니다.
\[검증된 정답 = B, D\]검증된 정답 = B, D
2. 이 문제를 실제로 끝까지 풀기
세 패러다임은 모두 문제를 작은 구조로 보지만 성공 조건은 다릅니다. 특히 DP가 된다고 Greedy도 된다는 결론은 나오지 않습니다.
풀이를 시작할 때 다음 네 사실을 먼저 적습니다. (1) D&C runtime은 recursive calls와 divide/combine 비용 전체 recurrence에 달려 있다. (2) DP는 overlapping subproblems를 저장해 중복 계산을 줄인다. (3) DP와 Greedy 모두 optimal substructure를 사용하지만 Greedy에는 greedy-choice property가 추가로 필요하다. (4) 동적 계획법(DP)으로 풀 수 있다고 해서 탐욕법(Greedy)도 최적해를 보장하는 것은 아니다.
선택지 A는 거짓입니다. 거짓이다. D&C는 부분문제를 재귀적으로 푸는 비용과 divide/combine 비용이 함께 recurrence를 이룬다. MergeSort만 봐도 두 재귀 호출과 merge 비용이 모두 들어간다. 가장 작은 확인 예는 MergeSort: \(T(n)=2T(n/2)+\Theta(n). \text{combine}\)T(n)=2T(n/2)+Θ(n). combine만 보면 \(\Theta(n)\)Θ(n)이지만 전체는 \(\Theta(n \log n)\)Θ(n log n)이다.
선택지 B는 참입니다. 참이다. 강의와 공식 해설 모두 DP가 이미 계산한 중간 결과를 저장하고 재사용하여 Mehrfachberechnungen를 피한다고 설명한다.
선택지 C는 거짓입니다. 거짓이다. DP가 가능한 것은 subproblem structure가 있다는 뜻이지, 현재 local choice가 safe하다는 뜻이 아니다. Greedy는 별도 greedy-choice proof가 필요하고, 강의의 Greedy-TSP 및 해설의 0/1 knapsack 반례가 이를 보여준다. 가장 작은 확인 예는 용량이 50이고 (가치,무게)가 (60,10),(100,20),(120,30)인 0/1 배낭문제를 보자. 가치 밀도 탐욕법은 앞의 두 물건을 골라 가치 160을 얻지만, 두 번째와 세 번째 물건을 고르면 가치 220을 얻는다.
선택지 D는 참입니다. 참으로 판정한다. 최적화 문제에서 DP는 최적해가 부분문제의 최적해로 구성되는 recurrence가 필요하고, Greedy도 local choice를 고정한 뒤 남은 subproblem이 최적 구조를 유지해야 한다. 단, 일반 교과서적으로 DP가 counting 같은 비최적화 문제에도 쓰인다는 점은 course-version note로 남긴다.
따라서 현재 문언에서 참으로 검증된 선택지는 B, D입니다. 선택지는 서로 상대평가하지 않고 각 문장을 정의·전제·반례로 독립 검증했습니다.
시험장에서 쓸 압축 절차는 다음과 같습니다. A의 only와 C의 always를 반례로 제거하고 B·D의 정의 범위를 확인합니다. 시간이 부족해도 '항상(always)', '오직(only)', '모든(every)' 같은 강한 단어와 전제조건, O와 Θ를 먼저 확인하면 대표 함정을 피할 수 있습니다.
3. 선택지 A–D를 한 줄도 건너뛰지 않고 판정하기
-
A거짓
거짓이다. D&C는 부분문제를 재귀적으로 푸는 비용과 divide/combine 비용이 함께 recurrence를 이룬다. MergeSort만 봐도 두 재귀 호출과 merge 비용이 모두 들어간다.
빠른 확인법: MergeSort: \(T(n)=2T(n/2)+\Theta(n). \text{combine}\)
T(n)=2T(n/2)+Θ(n). combine만 보면 \(\Theta(n)\)Θ(n)이지만 전체는 \(\Theta(n \log n)\)Θ(n log n)이다. -
B참 — 정답 후보
참이다. 강의와 공식 해설 모두 DP가 이미 계산한 중간 결과를 저장하고 재사용하여 Mehrfachberechnungen를 피한다고 설명한다.
빠른 확인법: naive recursive algorithm이 같은 부분문제를 여러 번 풀게 되는 문제에서 Dynamic Programming은 효율적인 방법이다.
-
C거짓
거짓이다. DP가 가능한 것은 subproblem structure가 있다는 뜻이지, 현재 local choice가 safe하다는 뜻이 아니다. Greedy는 별도 greedy-choice proof가 필요하고, 강의의 Greedy-TSP 및 해설의 0/1 knapsack 반례가 이를 보여준다.
빠른 확인법: 용량이 50이고 (가치,무게)가 (60,10),(100,20),(120,30)인 0/1 배낭문제를 보자. 가치 밀도 탐욕법은 앞의 두 물건을 골라 가치 160을 얻지만, 두 번째와 세 번째 물건을 고르면 가치 220을 얻는다.
-
D참 — 정답 후보
참으로 판정한다. 최적화 문제에서 DP는 최적해가 부분문제의 최적해로 구성되는 recurrence가 필요하고, Greedy도 local choice를 고정한 뒤 남은 subproblem이 최적 구조를 유지해야 한다. 단, 일반 교과서적으로 DP가 counting 같은 비최적화 문제에도 쓰인다는 점은 course-version note로 남긴다.
빠른 확인법: Dynamic Programming과 Greedy 알고리즘은 둘 다 문제가 optimal substructure를 가진다는 전제를 둔다.
4. 초보자가 가장 자주 틀리는 이유
- DP 가능성, optimal substructure, Greedy optimality를 서로 같은 말로 만들지 않는다.
- exactly-two라는 이유만으로 근거 없이 두 선택지를 맞다고 만든다.
- 선택지의 절반만 맞는데 결합 문장 전체를 참으로 판정한다.
- always, only, every 같은 강한 단어를 놓친다.
- 정의와 구현, 전제조건과 결론, upper bound와 tight bound를 섞는다.
- 작은 예 하나로 거짓은 깰 수 있지만 참인 보편 명제를 증명했다고 착각한다.
- 복기 시험지가 공식 원문·공식 답안이라는 전제로 애매성을 숨긴다.
- 용어를 암기한 소리만 따라가고 실제 상태나 한 단계 실행을 그리지 않는다.
5. 시험 답안 템플릿
A의 only와 C의 always를 반례로 제거하고 B·D의 정의 범위를 확인합니다. 각 선택지를 정의와 전제에 따라 독립 판정하면 참인 label은 B, D이다. 핵심 근거: D&C runtime은 recursive calls와 divide/combine 비용 전체 recurrence에 달려 있다. DP는 overlapping subproblems를 저장해 중복 계산을 줄인다. DP와 Greedy 모두 optimal substructure를 사용하지만 Greedy에는 greedy-choice property가 추가로 필요하다. 동적 계획법(DP)으로 풀 수 있다고 해서 탐욕법(Greedy)도 최적해를 보장하는 것은 아니다.
6. 스스로 이해했는지 확인
II-15의 주제를 한 문장으로 설명하면?
정답: 세 패러다임은 모두 문제를 작은 구조로 보지만 성공 조건은 다릅니다. 특히 DP가 된다고 Greedy도 된다는 결론은 나오지 않습니다.
이 문제에서 가장 먼저 꺼낼 판정법은?
정답: A의 only와 C의 always를 반례로 제거하고 B·D의 정의 범위를 확인합니다.
핵심 사실 네 가지 중 첫 번째는?
정답: D&C runtime은 recursive calls와 divide/combine 비용 전체 recurrence에 달려 있다.
핵심 사실 네 가지 중 두 번째는?
정답: DP는 overlapping subproblems를 저장해 중복 계산을 줄인다.
가장 위험한 함정은?
정답: DP 가능성, optimal substructure, Greedy optimality를 서로 같은 말로 만들지 않는다.
정답 label은?
정답: B, D
D&C 실행시간이 combine 단계에만 의존하지 않는 이유를 recurrence 형태로 말해 보라.
정답: \(T(n)=\text{subproblem} \text{calls} + \text{divide}/\text{combine} \text{work}\)T(n)=subproblem calls + divide/combine work형태다. 예를 들어 MergeSort는 \(T(n)=2T(n/2)+\Theta(n)\)T(n)=2T(n/2)+Θ(n)이므로 combine만 보면 전체 \(\Theta(n \log n)\)Θ(n log n)을 놓친다.
DP를 exam answer로 설명할 때 반드시 말해야 하는 여섯 요소는 무엇인가?
정답: 상태의 의미(state meaning), 경계값·기저 사례(boundary/base case), 상태 전이(transition), 계산 순서, 최종 답이 있는 칸, 실행시간·공간복잡도다.
근거 자료
AuD Gedächtnisprotokoll SoSe 2025.md· Multiple Choice II-15
복기된 문언과 선택지; 공식 답안지가 아님AuD Gedächtnisprotokoll SoSe 2025.md· MC section II-15 to II-17
근거 내용: SoSe 2025 복기 자료의 세 문항 문언·선택지·배점과 정확히 두 개 선택 규칙을 확인한다.Vorlesung\07AdvancedDesigns.pdf· p. 3
근거 내용: 강의 개요는 분할 정복(Divide & Conquer)을 서로 겹치지 않는 부분문제의 재귀 풀이로, 백트래킹(Backtracking)을 해 공간 탐색으로, 동적 계획법(Dynamic Programming)을 겹치는 부분문제의 재사용으로 설명한다. 탐욕법(Greedy)은 국소적으로 최선인 선택을 쌓고, 메타휴리스틱(Metaheuristik)은 최적화 탐색을 안내하는 상위 전략이다.Vorlesung\07AdvancedDesigns.pdf· pp. 56-69
근거 내용: 최소 편집 거리(Minimum Edit Distance)를 접두사 상태 D[i][j]의 동적 계획법 표로 모델링하고 복사·치환·삭제·삽입 전이를 제시한다.Vorlesung\07AdvancedDesigns.pdf· pp. 73-81
근거 내용: 탐욕 원리(Greedy principle), 탐욕 알고리즘의 예인 Dijkstra·Kruskal, 국소 선택이 전역 최적해를 보장하지 않음을 보이는 Greedy-TSP 반례를 설명한다.