II-17 D&C 분할 크기·Dijkstra·Backtracking·DP overlap — 완전 초보자 Masterclass
먼저 이 문제의 정체부터
correctness를 위해 균등 분할이 필수인 것은 아닙니다. 불균등 분할은 효율을 나쁘게 할 수 있지만 QuickSort처럼 알고리즘 자체는 올바를 수 있습니다.
피자를 똑같이 자르지 않아도 모든 조각을 처리하면 일은 끝나지만 작업 분배 효율은 달라집니다.
이 문항의 풀이 목표는 정답 label 암기가 아니라 다음 절차를 재현하는 것입니다. must/equal-size는 QuickSort, non-overlapping은 DP 정의의 반대로 제거합니다.
복기 시험지는 공식 답안지가 아니므로 문언과 selection rule이 충돌하면 그 사실을 표시하고 현재 강의 자료로 각 보기를 독립 검증합니다.
0. 필요한 개념을 처음부터 배우기
개념 1 · 문제의 정체를 생활 언어로
correctness를 위해 균등 분할이 필수인 것은 아닙니다. 불균등 분할은 효율을 나쁘게 할 수 있지만 QuickSort처럼 알고리즘 자체는 올바를 수 있습니다.
이 문항에서 가장 먼저 붙잡을 문장은 '분할 정복(D&C)의 부분 문제 크기가 같아야만 정확한 것은 아니다.'입니다. 용어를 외우기 전에 이 문장이 어떤 상황을 말하는지 작은 예를 만들어 확인합니다.
이 절에서 꼭 기억할 것
- 분할 정복(D&C)의 부분 문제 크기가 같아야만 정확한 것은 아니다.
- must/equal-size는 QuickSort, non-overlapping은 DP 정의의 반대로 제거합니다.
개념 2 · 반드시 알아야 하는 네 개의 뼈대
첫째, 분할 정복(D&C)의 부분 문제 크기가 같아야만 정확한 것은 아니다. 둘째, 다익스트라(Dijkstra)는 탐욕 알고리즘이다.
셋째, 백트래킹(Backtracking)은 결정 문제와 최적화 문제를 모두 다룰 수 있다. 넷째, 동적 계획법(DP)은 서로 겹치지 않는 문제가 아니라 겹치는 부분 문제를 전제로 한다. 이 네 문장을 서로 섞지 않고 별도 체크박스로 기억해야 합니다.
이 절에서 꼭 기억할 것
- 분할 정복(D&C)의 부분 문제 크기가 같아야만 정확한 것은 아니다.
- 다익스트라(Dijkstra)는 탐욕 알고리즘이다.
- 백트래킹(Backtracking)은 결정 문제와 최적화 문제를 모두 다룰 수 있다.
- 동적 계획법(DP)은 서로 겹치지 않는 문제가 아니라 겹치는 부분 문제를 전제로 한다.
개념 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, C입니다. 정답 수와 섹션 규칙이 충돌하는 문항은 억지로 두 개를 만들지 않고 복기 문언 누락 가능성을 명시합니다.
수식으로 정확히 쓰기
핵심 규칙선택 규칙: 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
핵심 규칙검증된 선택지: B, C
이 절에서 꼭 기억할 것
- D&C의 'balanced split'과 correctness, DP의 'overlapping'과 D&C의 'disjoint'를 섞지 않는다.
- A의 muss/gleich groß는 QuickSort로 제거, D의 nicht überlappend는 DP 정의의 반대라 제거, B와 C를 선택한다.
1. 시험장에서 따라 할 풀이 순서
선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
D&C 분할 크기·Dijkstra·Backtracking·DP overlap
분할 정복(D&C)의 부분 문제 크기가 같아야만 정확한 것은 아니다. | 다익스트라(Dijkstra)는 탐욕 알고리즘이다. | 백트래킹(Backtracking)은 결정 문제와 최적화 문제를 모두 다룰 수 있다.
선택지 \(A =\)A =거짓
선택 규칙을 먼저 적는다
이 문항의 규칙은 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))입니다. 마지막에 참 개수를 반드시 재검산합니다.핵심 규칙선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))문장을 쉬운 한국어로 다시 쓴다
알고리즘 설계 방법에 대한 설명 중 정확히 두 개를 고르시오.
핵심 규칙D&C 분할 크기·Dijkstra·Backtracking·DP overlap
핵심 도구를 종이에 꺼낸다
must/equal-size는 QuickSort, non-overlapping은 DP 정의의 반대로 제거합니다.
핵심 규칙분할 정복(D&C)의 부분 문제 크기가 같아야만 정확한 것은 아니다. | 다익스트라(Dijkstra)는 탐욕 알고리즘이다. | 백트래킹(Backtracking)은 결정 문제와 최적화 문제를 모두 다룰 수 있다.
선택지 A를 독립 판정한다
거짓이다. 같은 크기 분할은 runtime 분석에 유리할 수 있지만 correctness 조건은 아니다. QuickSort는 pivot에 따라 불균형한 부분문제를 만들 수 있어도 partition과 재귀 정렬 구조로 올바르게 정렬한다.
\[선택지 A = 거짓\]선택지 A = 거짓선택지 B를 독립 판정한다
참이다. 강의의 Greedy section에서 Dijkstra-SSSP를 'Unsere Greedy-Algorithmen' 예시로 제시하고, 아직 확정되지 않은 정점 중 dist가 가장 작은 정점을 선택한다고 설명한다.
\[선택지 B = 참\]선택지 B = 참선택지 C를 독립 판정한다
참이다. Backtracking은 해 공간을 탐색하는 방법이다. 해 존재 여부만 묻는 WordSearch 같은 search/decision 형태에도 쓰이고, 모든 후보를 탐색하면서 best-so-far를 갱신하면 최적화 문제에도 사용할 수 있다.
\[선택지 C = 참\]선택지 C = 참선택지 D를 독립 판정한다
거짓이다. 정확히 반대다. 강의 개요와 Sheet 12 해설은 동적 계획법(DP)이 겹치는 부분문제(überlappende Teilprobleme)와 저장된 중간 결과(Zwischenergebnisse)를 이용한다고 설명한다. 겹치지 않음(nicht überlappend)은 오히려 분할 정복(D&C)의 설명에 가깝다.
\[선택지 D = 거짓\]선택지 D = 거짓정답 수와 애매성을 재검산한다
참으로 판정된 선택지는 B, C입니다. 복기 섹션 규칙과 수가 다르면 원문 누락 가능성을 기록하고 거짓을 참으로 조작하지 않습니다.
\[검증된 정답 = B, C\]검증된 정답 = B, C
2. 이 문제를 실제로 끝까지 풀기
correctness를 위해 균등 분할이 필수인 것은 아닙니다. 불균등 분할은 효율을 나쁘게 할 수 있지만 QuickSort처럼 알고리즘 자체는 올바를 수 있습니다.
풀이를 시작할 때 다음 네 사실을 먼저 적습니다. (1) 분할 정복(D&C)의 부분 문제 크기가 같아야만 정확한 것은 아니다. (2) 다익스트라(Dijkstra)는 탐욕 알고리즘이다. (3) 백트래킹(Backtracking)은 결정 문제와 최적화 문제를 모두 다룰 수 있다. (4) 동적 계획법(DP)은 서로 겹치지 않는 문제가 아니라 겹치는 부분 문제를 전제로 한다.
선택지 A는 거짓입니다. 거짓이다. 같은 크기 분할은 runtime 분석에 유리할 수 있지만 correctness 조건은 아니다. QuickSort는 pivot에 따라 불균형한 부분문제를 만들 수 있어도 partition과 재귀 정렬 구조로 올바르게 정렬한다. 가장 작은 확인 예는 QuickSort에서 pivot이 한쪽 끝 원소이면 분할 크기가 0과 n-1처럼 불균형해질 수 있지만 알고리즘 자체는 정렬 문제를 올바르게 푼다.
선택지 B는 참입니다. 참이다. 강의의 Greedy section에서 Dijkstra-SSSP를 'Unsere Greedy-Algorithmen' 예시로 제시하고, 아직 확정되지 않은 정점 중 dist가 가장 작은 정점을 선택한다고 설명한다.
선택지 C는 참입니다. 참이다. Backtracking은 해 공간을 탐색하는 방법이다. 해 존재 여부만 묻는 WordSearch 같은 search/decision 형태에도 쓰이고, 모든 후보를 탐색하면서 best-so-far를 갱신하면 최적화 문제에도 사용할 수 있다.
선택지 D는 거짓입니다. 거짓이다. 정확히 반대다. 강의 개요와 Sheet 12 해설은 동적 계획법(DP)이 겹치는 부분문제(überlappende Teilprobleme)와 저장된 중간 결과(Zwischenergebnisse)를 이용한다고 설명한다. 겹치지 않음(nicht überlappend)은 오히려 분할 정복(D&C)의 설명에 가깝다. 가장 작은 확인 예는 Minimum Edit Distance에서 D[i][j] 주변 subproblem들이 D[i-1][j-1] 같은 같은 prefix state를 반복 참조한다.
따라서 현재 문언에서 참으로 검증된 선택지는 B, C입니다. 선택지는 서로 상대평가하지 않고 각 문장을 정의·전제·반례로 독립 검증했습니다.
시험장에서 쓸 압축 절차는 다음과 같습니다. must/equal-size는 QuickSort, non-overlapping은 DP 정의의 반대로 제거합니다. 시간이 부족해도 '항상(always)', '오직(only)', '모든(every)' 같은 강한 단어와 전제조건, O와 Θ를 먼저 확인하면 대표 함정을 피할 수 있습니다.
3. 선택지 A–D를 한 줄도 건너뛰지 않고 판정하기
-
A거짓
거짓이다. 같은 크기 분할은 runtime 분석에 유리할 수 있지만 correctness 조건은 아니다. QuickSort는 pivot에 따라 불균형한 부분문제를 만들 수 있어도 partition과 재귀 정렬 구조로 올바르게 정렬한다.
빠른 확인법: QuickSort에서 pivot이 한쪽 끝 원소이면 분할 크기가 0과 n-1처럼 불균형해질 수 있지만 알고리즘 자체는 정렬 문제를 올바르게 푼다.
-
B참 — 정답 후보
참이다. 강의의 Greedy section에서 Dijkstra-SSSP를 'Unsere Greedy-Algorithmen' 예시로 제시하고, 아직 확정되지 않은 정점 중 dist가 가장 작은 정점을 선택한다고 설명한다.
빠른 확인법: Dijkstra 알고리즘은 Greedy 알고리즘의 예이다.
-
C참 — 정답 후보
참이다. Backtracking은 해 공간을 탐색하는 방법이다. 해 존재 여부만 묻는 WordSearch 같은 search/decision 형태에도 쓰이고, 모든 후보를 탐색하면서 best-so-far를 갱신하면 최적화 문제에도 사용할 수 있다.
빠른 확인법: Backtracking은 결정문제와 최적화 문제 모두에 적용될 수 있다.
-
D거짓
거짓이다. 정확히 반대다. 강의 개요와 Sheet 12 해설은 동적 계획법(DP)이 겹치는 부분문제(überlappende Teilprobleme)와 저장된 중간 결과(Zwischenergebnisse)를 이용한다고 설명한다. 겹치지 않음(nicht überlappend)은 오히려 분할 정복(D&C)의 설명에 가깝다.
빠른 확인법: Minimum Edit Distance에서 D[i][j] 주변 subproblem들이 D[i-1][j-1] 같은 같은 prefix state를 반복 참조한다.
4. 초보자가 가장 자주 틀리는 이유
- D&C의 'balanced split'과 correctness, DP의 'overlapping'과 D&C의 'disjoint'를 섞지 않는다.
- exactly-two라는 이유만으로 근거 없이 두 선택지를 맞다고 만든다.
- 선택지의 절반만 맞는데 결합 문장 전체를 참으로 판정한다.
- always, only, every 같은 강한 단어를 놓친다.
- 정의와 구현, 전제조건과 결론, upper bound와 tight bound를 섞는다.
- 작은 예 하나로 거짓은 깰 수 있지만 참인 보편 명제를 증명했다고 착각한다.
- 복기 시험지가 공식 원문·공식 답안이라는 전제로 애매성을 숨긴다.
- 용어를 암기한 소리만 따라가고 실제 상태나 한 단계 실행을 그리지 않는다.
5. 시험 답안 템플릿
must/equal-size는 QuickSort, non-overlapping은 DP 정의의 반대로 제거합니다. 각 선택지를 정의와 전제에 따라 독립 판정하면 참인 label은 B, C이다. 핵심 근거: 분할 정복(D&C)의 부분 문제 크기가 같아야만 정확한 것은 아니다. 다익스트라(Dijkstra)는 탐욕 알고리즘이다. 백트래킹(Backtracking)은 결정 문제와 최적화 문제를 모두 다룰 수 있다. 동적 계획법(DP)은 서로 겹치지 않는 문제가 아니라 겹치는 부분 문제를 전제로 한다.
6. 스스로 이해했는지 확인
II-17의 주제를 한 문장으로 설명하면?
정답: correctness를 위해 균등 분할이 필수인 것은 아닙니다. 불균등 분할은 효율을 나쁘게 할 수 있지만 QuickSort처럼 알고리즘 자체는 올바를 수 있습니다.
이 문제에서 가장 먼저 꺼낼 판정법은?
정답: must/equal-size는 QuickSort, non-overlapping은 DP 정의의 반대로 제거합니다.
핵심 사실 네 가지 중 첫 번째는?
정답: 분할 정복(D&C)의 부분 문제 크기가 같아야만 정확한 것은 아니다.
핵심 사실 네 가지 중 두 번째는?
정답: 다익스트라(Dijkstra)는 탐욕 알고리즘이다.
가장 위험한 함정은?
정답: D&C의 'balanced split'과 correctness, DP의 'overlapping'과 D&C의 'disjoint'를 섞지 않는다.
정답 label은?
정답: B, C
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-17
복기된 문언과 선택지; 공식 답안지가 아님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 반례를 설명한다.