II-16 백트래킹(Backtracking)·메타휴리스틱(Metaheuristic)·언덕 오르기(Hill Climbing)·편집 거리(Edit Distance) — 완전 초보자 Masterclass
먼저 이 문제의 정체부터
이 문항은 네 용어의 정의를 구분하는 문제입니다. heuristic은 좋은 해를 빠르게 찾을 수 있지만 항상 최적이라는 보장은 아닙니다.
산에서 눈앞의 가장 가파른 오르막만 택하면 가까운 봉우리에 갇힐 수 있습니다.
이 문항의 풀이 목표는 정답 label 암기가 아니라 다음 절차를 재현하는 것입니다. durchschnittlich와 immer 같은 과도한 보장을 의심하고 B·D의 정의를 확인합니다.
복기 시험지는 공식 답안지가 아니므로 문언과 selection rule이 충돌하면 그 사실을 표시하고 현재 강의 자료로 각 보기를 독립 검증합니다.
0. 필요한 개념을 처음부터 배우기
개념 1 · 문제의 정체를 생활 언어로
이 문항은 네 용어의 정의를 구분하는 문제입니다. heuristic은 좋은 해를 빠르게 찾을 수 있지만 항상 최적이라는 보장은 아닙니다.
이 문항에서 가장 먼저 붙잡을 문장은 'Backtracking은 infeasible partial solution을 prune해 brute-force보다 적게 탐색할 수 있다.'입니다. 용어를 외우기 전에 이 문장이 어떤 상황을 말하는지 작은 예를 만들어 확인합니다.
이 절에서 꼭 기억할 것
- Backtracking은 infeasible partial solution을 prune해 brute-force보다 적게 탐색할 수 있다.
- durchschnittlich와 immer 같은 과도한 보장을 의심하고 B·D의 정의를 확인합니다.
개념 2 · 반드시 알아야 하는 네 개의 뼈대
첫째, Backtracking은 infeasible partial solution을 prune해 brute-force보다 적게 탐색할 수 있다. 둘째, Metaheuristic은 여러 최적화 문제에 적용하는 일반 탐색 절차다.
셋째, Hill climbing은 local optimum에 갇힐 수 있다. 넷째, Minimum Edit Distance는 삽입·삭제·치환 비용의 최소 합을 측정한다. 이 네 문장을 서로 섞지 않고 별도 체크박스로 기억해야 합니다.
이 절에서 꼭 기억할 것
- Backtracking은 infeasible partial solution을 prune해 brute-force보다 적게 탐색할 수 있다.
- Metaheuristic은 여러 최적화 문제에 적용하는 일반 탐색 절차다.
- Hill climbing은 local optimum에 갇힐 수 있다.
- Minimum Edit Distance는 삽입·삭제·치환 비용의 최소 합을 측정한다.
개념 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
이 절에서 꼭 기억할 것
- heuristic 또는 local search를 '항상 최적'으로 강화하지 않는다.
- durchschnittlich와 immer를 먼저 의심한다. B는 정의, D는 MED 정의라 바로 참이다.
1. 시험장에서 따라 할 풀이 순서
선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
백트래킹(Backtracking)·메타휴리스틱(Metaheuristic)·언덕 오르기(Hill Climbing)·편집 거리(Edit Distance)
Backtracking은 infeasible partial solution을 prune해 brute-force보다 적게 탐색할 수 있다. | Metaheuristic은 여러 최적화 문제에 적용하는 일반 탐색 절차다. | Hill climbing은 local optimum에 갇힐 수 있다.
선택지 \(A =\)A =거짓
선택 규칙을 먼저 적는다
이 문항의 규칙은 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))입니다. 마지막에 참 개수를 반드시 재검산합니다.핵심 규칙선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))문장을 쉬운 한국어로 다시 쓴다
알고리즘 설계 방법에 대한 설명 중 정확히 두 개를 고르시오.
핵심 규칙백트래킹(Backtracking)·메타휴리스틱(Metaheuristic)·언덕 오르기(Hill Climbing)·편집 거리(Edit Distance)
핵심 도구를 종이에 꺼낸다
durchschnittlich와 immer 같은 과도한 보장을 의심하고 B·D의 정의를 확인합니다.
핵심 규칙Backtracking은 infeasible partial solution을 prune해 brute-force보다 적게 탐색할 수 있다. | Metaheuristic은 여러 최적화 문제에 적용하는 일반 탐색 절차다. | Hill climbing은 local optimum에 갇힐 수 있다.
선택지 A를 독립 판정한다
거짓이다. Backtracking은 Brute Force처럼 후보를 탐색할 수 있지만, 불가능한 현재 경로를 발견하면 되돌아가며 가지치기한다. 그래서 탐색량은 문제, pruning 조건, 입력 분포에 따라 달라지고 '평균적으로 같다'고 일반화할 수 없다.
\[선택지 A = 거짓\]선택지 A = 거짓선택지 B를 독립 판정한다
참이다. 강의는 메타휴리스틱(Metaheuristik)을 임의의 최적화 문제(beliebige Optimierungsprobleme)의 탐색을 안내하는 문제 독립적 일반 절차로 설명한다.
\[선택지 B = 참\]선택지 B = 참선택지 C를 독립 판정한다
거짓이다. Hill Climbing은 주변에서 더 나은 해를 찾는 local search다. 강의는 local maximum과 global maximum을 구분하고, Hill Climbing이 local optimum에 멈출 수 있다고 명시한다.
\[선택지 C = 거짓\]선택지 C = 거짓선택지 D를 독립 판정한다
참이다. 강의와 공식 해설은 insert, delete, substitute, copy 비용을 이용해 한 문자열을 다른 문자열로 바꾸는 최소 비용 또는 최소 연산 수를 계산한다고 설명한다.
\[선택지 D = 참\]선택지 D = 참정답 수와 애매성을 재검산한다
참으로 판정된 선택지는 B, D입니다. 복기 섹션 규칙과 수가 다르면 원문 누락 가능성을 기록하고 거짓을 참으로 조작하지 않습니다.
\[검증된 정답 = B, D\]검증된 정답 = B, D
2. 이 문제를 실제로 끝까지 풀기
이 문항은 네 용어의 정의를 구분하는 문제입니다. heuristic은 좋은 해를 빠르게 찾을 수 있지만 항상 최적이라는 보장은 아닙니다.
풀이를 시작할 때 다음 네 사실을 먼저 적습니다. (1) Backtracking은 infeasible partial solution을 prune해 brute-force보다 적게 탐색할 수 있다. (2) Metaheuristic은 여러 최적화 문제에 적용하는 일반 탐색 절차다. (3) Hill climbing은 local optimum에 갇힐 수 있다. (4) Minimum Edit Distance는 삽입·삭제·치환 비용의 최소 합을 측정한다.
선택지 A는 거짓입니다. 거짓이다. Backtracking은 Brute Force처럼 후보를 탐색할 수 있지만, 불가능한 현재 경로를 발견하면 되돌아가며 가지치기한다. 그래서 탐색량은 문제, pruning 조건, 입력 분포에 따라 달라지고 '평균적으로 같다'고 일반화할 수 없다. 가장 작은 확인 예는 WordSearch에서 현재 칸이 목표 단어의 다음 글자와 다르면 그 branch를 즉시 버린다. 모든 가능한 경로를 끝까지 brute-force로 확장하지 않는다.
선택지 B는 참입니다. 참이다. 강의는 메타휴리스틱(Metaheuristik)을 임의의 최적화 문제(beliebige Optimierungsprobleme)의 탐색을 안내하는 문제 독립적 일반 절차로 설명한다.
선택지 C는 거짓입니다. 거짓이다. Hill Climbing은 주변에서 더 나은 해를 찾는 local search다. 강의는 local maximum과 global maximum을 구분하고, Hill Climbing이 local optimum에 멈출 수 있다고 명시한다. 가장 작은 확인 예는 강의의 TSP local-search 예시에서 Greedy solution 주변 swap neighborhood에는 더 나은 해가 없지만, 떨어진 곳에 global optimum이 존재한다.
선택지 D는 참입니다. 참이다. 강의와 공식 해설은 insert, delete, substitute, copy 비용을 이용해 한 문자열을 다른 문자열로 바꾸는 최소 비용 또는 최소 연산 수를 계산한다고 설명한다.
따라서 현재 문언에서 참으로 검증된 선택지는 B, D입니다. 선택지는 서로 상대평가하지 않고 각 문장을 정의·전제·반례로 독립 검증했습니다.
시험장에서 쓸 압축 절차는 다음과 같습니다. durchschnittlich와 immer 같은 과도한 보장을 의심하고 B·D의 정의를 확인합니다. 시간이 부족해도 '항상(always)', '오직(only)', '모든(every)' 같은 강한 단어와 전제조건, O와 Θ를 먼저 확인하면 대표 함정을 피할 수 있습니다.
3. 선택지 A–D를 한 줄도 건너뛰지 않고 판정하기
-
A거짓
거짓이다. Backtracking은 Brute Force처럼 후보를 탐색할 수 있지만, 불가능한 현재 경로를 발견하면 되돌아가며 가지치기한다. 그래서 탐색량은 문제, pruning 조건, 입력 분포에 따라 달라지고 '평균적으로 같다'고 일반화할 수 없다.
빠른 확인법: WordSearch에서 현재 칸이 목표 단어의 다음 글자와 다르면 그 branch를 즉시 버린다. 모든 가능한 경로를 끝까지 brute-force로 확장하지 않는다.
-
B참 — 정답 후보
참이다. 강의는 메타휴리스틱(Metaheuristik)을 임의의 최적화 문제(beliebige Optimierungsprobleme)의 탐색을 안내하는 문제 독립적 일반 절차로 설명한다.
빠른 확인법: Metaheuristics는 최적화 문제를 풀기 위한 일반적인 절차이다.
-
C거짓
거짓이다. Hill Climbing은 주변에서 더 나은 해를 찾는 local search다. 강의는 local maximum과 global maximum을 구분하고, Hill Climbing이 local optimum에 멈출 수 있다고 명시한다.
빠른 확인법: 강의의 TSP local-search 예시에서 Greedy solution 주변 swap neighborhood에는 더 나은 해가 없지만, 떨어진 곳에 global optimum이 존재한다.
-
D참 — 정답 후보
참이다. 강의와 공식 해설은 insert, delete, substitute, copy 비용을 이용해 한 문자열을 다른 문자열로 바꾸는 최소 비용 또는 최소 연산 수를 계산한다고 설명한다.
빠른 확인법: Minimum Edit Distance는 한 문자열을 다른 문자열로 바꾸는 데 필요한 연산 수를 측정한다.
4. 초보자가 가장 자주 틀리는 이유
- heuristic 또는 local search를 '항상 최적'으로 강화하지 않는다.
- exactly-two라는 이유만으로 근거 없이 두 선택지를 맞다고 만든다.
- 선택지의 절반만 맞는데 결합 문장 전체를 참으로 판정한다.
- always, only, every 같은 강한 단어를 놓친다.
- 정의와 구현, 전제조건과 결론, upper bound와 tight bound를 섞는다.
- 작은 예 하나로 거짓은 깰 수 있지만 참인 보편 명제를 증명했다고 착각한다.
- 복기 시험지가 공식 원문·공식 답안이라는 전제로 애매성을 숨긴다.
- 용어를 암기한 소리만 따라가고 실제 상태나 한 단계 실행을 그리지 않는다.
5. 시험 답안 템플릿
durchschnittlich와 immer 같은 과도한 보장을 의심하고 B·D의 정의를 확인합니다. 각 선택지를 정의와 전제에 따라 독립 판정하면 참인 label은 B, D이다. 핵심 근거: Backtracking은 infeasible partial solution을 prune해 brute-force보다 적게 탐색할 수 있다. Metaheuristic은 여러 최적화 문제에 적용하는 일반 탐색 절차다. Hill climbing은 local optimum에 갇힐 수 있다. Minimum Edit Distance는 삽입·삭제·치환 비용의 최소 합을 측정한다.
6. 스스로 이해했는지 확인
II-16의 주제를 한 문장으로 설명하면?
정답: 이 문항은 네 용어의 정의를 구분하는 문제입니다. heuristic은 좋은 해를 빠르게 찾을 수 있지만 항상 최적이라는 보장은 아닙니다.
이 문제에서 가장 먼저 꺼낼 판정법은?
정답: durchschnittlich와 immer 같은 과도한 보장을 의심하고 B·D의 정의를 확인합니다.
핵심 사실 네 가지 중 첫 번째는?
정답: Backtracking은 infeasible partial solution을 prune해 brute-force보다 적게 탐색할 수 있다.
핵심 사실 네 가지 중 두 번째는?
정답: Metaheuristic은 여러 최적화 문제에 적용하는 일반 탐색 절차다.
가장 위험한 함정은?
정답: heuristic 또는 local search를 '항상 최적'으로 강화하지 않는다.
정답 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-16
복기된 문언과 선택지; 공식 답안지가 아님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 반례를 설명한다.