Greedy Algorithms & Heuristics

1. Overview

탐욕 알고리즘 및 휴리스틱(Greedy Algorithms & Heuristics, GAH)은 전 세계적인 복잡성 속에서 '직관'과 '순간의 선택'을 통해 가장 빠르고 효율적인 길을 찾아내는 시스템의 '전략적 결단 엔진'입니다.

모든 경우의 수를 따지기에 세상은 너무 큽니다. 학습자는 당장 앞의 이익이 전역 최적해(Global Optimal)로 이어질 것임을 수학적으로 증명하는 **탐욕적 선택성(Greedy Choice Property)**을 배웁니다. 또한, 완벽한 정답이 물리적으로 불가능할 때 '그럴싸한' 정답을 빛의 속도로 찾아내는 휴리스틱(Heuristics) 기법과 A* 탐색의 수리적 원리를 익힙니다. 이를 통해 최소 신장 트리나 최단 경로 탐색 등 실시간 판단이 필요한 시스템 물리에서 최적의 퍼포먼스를 내는 법을 확보합니다.

2. Scope & Boundaries

In-Scope

• Greedy Conditions: 탐욕적 선택 조건과 최적 부분 구조(Optimal Substructure)의 수리적 결합
• Graph Greediness: 프림(Prim), 크루스칼(Kruskal), 다익스트라(Dijkstra) 알고리즘의 선택 물리
• Heuristic Search: 정체 불명의 비용을 예측하는 허들(Heuristic) 함수와 A* 알고리즘
• Approximation: NP-하드 문제에 대해 일정 비율 안의 해답을 보장하는 근사치 연산

Out-of-Scope

• 모든 경로를 다 뒤지는 완전 탐색 (04-03-04 노드로 위임)
• 과거의 결과를 테이블에 저장하는 동적 계획법 (04-03-02 노드로 위임)

Boundaries

• GAH vs. DP: DP가 '과거를 기억하며 신중히' 결정한다면, GAH는 '뒤도 안 돌아보고 눈앞의 이득'만 챙김으로써 연산 속도를 극대화하여 구분합니다.

3. Counterexample

• 단순히 "빠른 선택"이라 말하는 것은 GAH 학습이 아닙니다. 왜 거스름돈 문제에서 동전의 단위가 배수 관계(500, 100, 50)가 아닐 때 탐욕 기법이 실패하는지 반례를 수리적으로 증명할 수 있어야 하며, A* 탐색에서 휴리스틱 함수 $h(x)$가 실제 비용보다 크면 왜 최단 경로를 보장하지 못하는지(Admissible 조건 파괴) 분석하지 못한다면 GAH의 설계 결함을 이해하지 못한 것입니다.

4. Prerequisites

• Complexity Analysis & Big-O (Basic): 알고리즘 효율 측정이 필수입니다. (04-01-04 CAB)
• Heaps & Priority Queues (Recommended): 탐욕적 선택을 가속하는 힙 구조 이해가 권장됩니다. (04-02-02 HPQ)

5. Learning Map

1. The Instant Choice: 눈앞의 먹잇감을 놓치지 않는 탐욕의 물리를 배웁니다.
2. Global Integration: 순간의 먹잇감이 결국 최고의 만찬(Optimal solution)이 됨을 수리적으로 증명합니다.
3. The Guiding Star: 안개 속에서 목표까지의 남은 거리를 '짐작'하는 휴리스틱 기법을 익힙니다.
4. Near-Perfect Success: 완벽하진 않지만 충분히 훌륭한 답으로 빠르게 타협하는 기술을 완성합니다.

6. Learning Topics

Basic

Core: 탐욕 기법의 설계와 증명 (Greedy Foundations)

• Why to Learn: 복잡한 계산 없이도 최적의 해를 얻을 수 있는 '공짜 점심'의 기회를 잡기 위해서입니다.
• What to Learn:
  • Greedy Choice Property: 현재의 선택이 이후의 선택에 나쁜 영향을 주지 않는 논리
  • Induction Proof: 탐욕적 선택이 최적해의 일부가 됨을 보이는 수학적 귀납법
  • Scheduling Problem: 가장 빨리 끝나는 일을 먼저 선택하는 시간표 짜기 물리
• How to Learn:
  • 다양한 동전 단위(예: 500, 400, 100)를 가진 거스름돈 상황에서 탐욕 기법이 언제 무너지는지 수동 계산 실습
  • 회의실 배정 문제를 통해 '종료 시간' 기준 정렬이 왜 물리적으로 최적인지 논리 전개
• Implement: 데이터 세트에서 가장 큰 값이나 가장 효율적인 값을 순차적으로 뽑아내는 기초 탐욕 코드

Recommended

Core: 그래프 탐욕 알고리즘 (Greedy Graphs)

• Why to Learn: 통신망 구축이나 길 찾기 등 현실 인프라의 물리적 효율성을 극대화하기 위함입니다.
• What to Learn:
  • Kruskal's Algorithm: 가장 가벼운 간선부터 잇는 최소 신장 트리(MST) 조립물리
  • Prim's Algorithm: 하나의 정점에서 시작해 가장 가까운 이웃을 포섭하는 물리 시퀀스
  • Dijkstra's Shortcut: 미방문 노드 중 최소 거리를 끊임없이 갱신하는 물리 경로 발굴
• How to Learn:
  • 지도를 놓고 프림과 크루스칼 알고리즘을 각각 수행해 보며, 최종 결과 그래프가 왜 동일한지 비교 실습
  • 우선순위 큐(Heap)를 사용하여 그래프 탐욕 연산을 $O(V^2)$에서 $O(E \log V)$로 가속하는 과정 분석
• Implement: 다익스트라 알고리즘을 이용한 최단 거리 탐색 엔진

Practical

Core: 정보 기반 탐색과 휴리스틱 (Heuristic Search)

• Why to Learn: 정답을 물리적으로 알 수 없는 망막한 상태에서 최선의 방향타를 잡기 위해서입니다.
• What to Learn:
  • Heuristic Function $h(n)$: 목표까지 남은 거리를 예측하는 지능형 수리 모델
  • A* Algorithm: 실제 비용 $g(n)$과 예측 비용 $h(n)$을 합산하여 길을 트는 물리 구조
  • Manhattan vs Euclidean Distance: 공간의 성격에 따른 거리 휴리스틱의 물리적 사상
• How to Learn:
  • 8-퍼즐 문제를 풀며, '제자리에 있지 않은 타일 수'를 휴리스틱으로 썼을 때의 탐색 노드 수 변화 측정 실습
  • $h(n)=0$일 때 A* 알고리즘이 결국 다익스트라와 물리적으로 같아지는 현상 증명
• Implement: 격자 지도 위에서 목표점을 찾아가는 A* 탐색 시뮬레이션

Advanced

Core: 근사 알고리즘과 메타 휴리스틱 (Meta-Heuristics)

• Why to Learn: 우주의 수명보다 긴 연산 시간이 필요한 난제(NP-Hard)를 현실의 물리 시간 내에 해결하기 위함입니다.
• What to Learn:
  • TSP Approximation: 외판원 문제를 2배 이내의 오차로 해결하는 MST 기반 물리 기법
  • Simulated Annealing: 가끔 나쁜 선택을 허용하며 전역 최적점을 찾아가는 '금속 어닐링' 비유 물리
  • Ant Colony Optimization: 개미의 페로몬 정보를 이용해 집단 지성으로 최적해를 수렴시키는 방식
• How to Learn:
  • 외판원 문제(TSP)에 대해 완전 탐색과 탐욕 기법, 메타 휴리스틱의 소요 시간 및 정답 정확도 비교 분석 실습
  • 산의 정상을 찾는 'Hills Climbing' 기법이 지역 최적점(Local Optimal)에 갇히는 물리 현상 재현
• Implement: 무작위 노이즈를 섞어 더 좋은 해를 찾아 떠나는 시뮬레이티드 어닐링 프로토타입

7. Terminology

8. References

Primary

• [P2] SWEBOK v4.0 - Software Construction / Runtime Efficiency (Greedy) — Efficiency patterns.
• [P1] CS2023 - AL/Algorithms and Complexity (Greedy Algorithms) — Core requirements.

Secondary

• [Artificial Intelligence: A Modern Approach] Russell — Heuristic search depth.
• [The Algorithm Design Manual] Steven Skiena — Greedy and heuristic cases.

Industry

• [Google Maps: Route Planning Heuristics] — Real-world A* application.
• [NVIDIA: Parallel Pruning for Pathfinding] — Hardware-accelerated search.

9. Final Checklist

Primary

• '탐욕적 선택'을 한 결과가 왜 미래의 선택 가능성을 물리적으로 해치지 않아야 하는지 그 '독립성'을 설명 가능한가? (P1)
• 프림이나 크루스칼 알고리즘을 사용해 네트워크의 '최소 건설 비용'을 수리적으로 도출할 수 있는 가? (P1)

Secondary

• 탐욕 기법이 '전역 최적해'를 보장하지 못하는 케이스를 '0/1 배낭 문제' 등의 사례를 들어 물리적 근거로 소통 가능한가?
• A* 알고리즘에서 $f(n) = g(n) + h(n)$ 수식이 왜 '경험'과 '현실'의 결합인지 도출할 수 있는 가?

Industry

• 게임 엔진 내비게이션 메쉬(NavMesh) 설계 시, 매 순간의 연산량을 줄이기 위한 '계층적 휴리스틱'을 제안할 수 있는 가? (SFIA)
• 물류 배송 시나리오에서 TSP 난제를 해결하기 위해 근사 알고리즘이 내놓은 '비용 상한선'의 물리적 신뢰도를 기술할 수 있는 가?