Brain06. 탐욕 알고리즘 (Greedy Algorithm)
핵심 인사이트 (3줄 요약)
- 본질: 탐욕 알고리즘(Greedy Algorithm)은 각 단계에서 그 순간에 가장 최적이라고 판단되는 선택(지역 최적해, Local Optimum)을 하는 알고리즘 설계 패러다임으로, 전체적인 최적해(Global Optimum)를 보장하지는 않는다.
- 가치: 동적 프로그래밍과 달리 하위 문제의 중복 계산이 없으므로 시간 복잡도가 크게 낮아지고, 실제로도 좋은 근사해를 빠르게 얻을 수 있어 실용성이 높다.
- 융합: 탐욕 알고리즘의 핵심 조건인 **탐욕적 선택 특성(Greedy Choice Property)**과 **최적 부분구조(Optimal Substructure)**는 네트워크 라우팅(다익스트라), 압축(Huffman Coding), 작업 스케줄링, 최소 신장 트리(Kruskal, Prim) 등 광범위한 영역에서 적용된다.
Ⅰ. 개요 및 필요성 (Context & Necessity)
탐욕 알고리즘(Greedy Algorithm)은 "이 순간에 가장 좋은 것을 선택하라(Do the best you can now)"는 인간의 직관적 의사결정 방식에서 유래했다. 1950년대 컴퓨터 과학자들이 조합 최적화 문제를 풀기 위해 고안한 이 알고리즘은, 각 단계에서 가장 최선을 보认为是는 선택을 함으로써 최종적으로全域 최적해(Global Optimum)에 도달할 수 있다는 희망에서 출발했다. 그러나 이러한 희망이 항상 충족되는 것은 아닌 것이 핵심적인 美中不足이다.
탐욕 알고리즘이全域 최적해를 보장하려면 두 가지 조건이 충족되어야 한다. 첫째, 탐욕적 선택 특성(Greedy Choice Property): 이전에 수행한 선택과 무관하게 매 단계에서 지역적으로 최적인 선택이全局적으로도 최적인 해로 이어질 수 있는 특성이다. 둘째, 최적 부분구조(Optimal Substructure): 문제의 최적해가 하위 문제의 최적해들로 구성되는 구조이다. 이 두 조건이 모두 만족되면 탐욕 알고리즘이全域 최적해를 보장한다.
이 도식은 탐욕 알고리즘의 원리와 한계를 보여준다.
[탐욕 알고리즘의 작동 원리와 한계]
┌──────────────────────────────────────────────────────┐
│ │
│ [탐욕 알고리즘의 결정 트리] │
│ ──────────────────── │
│ │
│ 문제 시작 │
│ │ │
│ ┌───────┴───────┐ │
│ ▼ ▼ │
│ 선택 A (가장 좋음) 선택 B │
│ │ │
│ ┌────┴────┐ │
│ ▼ ▼ │
│ 선택 A-1 선택 A-2 ← 이 순간 가장 좋은 것을 선택 │
│ │ │
│ ▼ │
│ 선택 A-1-a │
│ │ │
│ ▼ │
│ ... │
│ │ │
│ ▼ │
│ [지역 최적해 ×] ← 최종 해가全局 최적해라는 보장은 없음│
│ │
│ [탐욕이 실패하는 경우: 거스름돈 문제] │
│ ─────────────────────────────────────── │
│ 동전: 1원, 4원, 5원 | 목표: 10원 │
│ │
│ 탐욕: 5원 → 5원 → 1원+1원+1원+1원+1원 = 5개 동전 │
│ (5원 선택 → 5원 선택 → 남은 0원? No → 1원 반복)│
│ → 5 + 4 + 1 = 10원 = 3개 │
│ → 최적: 5 + 5 = 2개 (탐욕 = 5개 vs 최적 = 2개) │
│ │
│ 이유: 탐욕적 선택(가장 큰 동전)이全域 최적해로 │
│ 이어지지 않음 → 탐욕 선택 특성을 만족하지 않음 │
│ │
└──────────────────────────────────────────────────────┘
- 관찰: 탐욕 알고리즘이 실패하는 경우는 "지역 최적해에서全域 최적해로" 이어지지 않는 구조적 문제가 있는 경우이다.
- 원인: 거스름돈 문제에서 4원을 선택하지 않고 5원을 선택한 것은 지역적으로는 optimal하지만(가장 큰 값), 전체적으로는 5+5가 5+4+1보다 동전 수가 적다.
- 결과: 모든 문제에 탐욕 알고리즘을 적용할 수 있는 것이 아니라, 탐욕 선택 특성을 만족하는 문제만을 대상으로 해야 한다.
- 판단: 문제의 분석에서 "탐욕적 선택이全域 최적해로 이어지는가?"를 판단하는 것이 가장 중요하며, 이것이 기술사 시험의 핵심考点이다.
📢 섹션 요약 비유: 탐욕 알고리즘은 등산에서 산을 오를 때 "지금 갈 수 있는 길 중 가장 가파른 길을 선택하는 것"과 같습니다. 당장은 빠르게 올라가는 것 같지만, 표기되지 않은 고난도 루트를 만나거나 벌새에 갇혀全局적으로 정상(최적해)에 도달하지 못할 수 있습니다.
Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)
탐욕 알고리즘의 구조는 동적 프로그래밍(DP)과 비교하면 매우 단순하다. DP가 모든 하위 문제의 해를표로 저장하고bottom-up으로 결합するのに対し、탐욕은 매 단계에서 가장 좋은 선택을하고 더 이상 이전 선택을 고려하지 않는다. 이 차이는 시간 복잡도에서 극명한 차이로 나타난다. DP의 피보나치는 O(N) 시간과 O(N) 공간이지만, 최적 부분구조와 탐욕 선택 특성이 있는 경우 탐욕은 O(N) 시간과 O(1) 공간으로 동일한 결과를낸다.
탐욕 알고리즘이 적용 가능한 대표 문제를 살펴보면, 활동 선택 문제(Activity Selection Problem): 회의실 하나에 최대한 많은 활동을 배치하는 문제로, 가장 빨리 끝나는 활동을 선택하는 탐욕 전략이全域 최적해를 보장한다. 분수 배낭 문제(Fractional Knapsack): 배낭에物品을 넣을 때 무게 대비 가치 비율이 가장 높은物品부터 넣는 탐욕 전략이全域 최적해를 보장한다(다만 0/1 배낭 문제에서는 탐욕이失敗). 유클리드 호제법(GCD): 두 수의 최대공약수에서 나머지가 0이 될 때까지 큰 수를 작은수로 나누는 과정이 탐욕적 선택의 대표적 사례이다.
[탐욕 vs 동적 프로그래밍 비교]
┌──────────────────────────────────────────────────────┐
│ │
│ [피보나치로 비교] │
│ ──────────────────── │
│ │
│ DP (Bottom-up, 타뷸레이션): │
│ dp[0]=0, dp[1]=1 │
│ for i=2 to N: │
│ dp[i] = dp[i-1] + dp[i-2] │
│ → O(N) 시간, O(N) 공간 │
│ │
│ Greedy (활동 선택 등, 특화된 경우): │
│ : 피보나치에는 직접 적용 불가 │
│ : "가장 빠른 종료" 선택 → 활동 선택 문제에 적용 │
│ → O(N) 시간, O(1) 공간 (DP보다 적은 자원) │
│ │
│ [활동 선택 문제에 적용] │
│ ──────────────────── │
│ 활동: [(시작, 종료), ...] │
│ 입력: (1,4), (3,5), (0,6), (5,7), (3,9), (5,9), │
│ (6,10), (8,11), (8,12), (2,14), (12,16) │
│ │
│ 탐욕 적용: 종료 시간이 가장 빠른 순으로 정렬 │
│ → (1,4), (3,5), (5,7), (6,10), (8,11), (8,12), │
│ (12,16) │
│ │
│ 선택: (1,4) 선택 → 이후非重複 활동中选择 (3,5) 선택 │
│ → 최대 활동 수: 6개 (탐욕이全域 최적해 보장) │
│ │
└──────────────────────────────────────────────────────┘
- 관찰: 탐욕 알고리즘은 하위 문제의 해를 저장하지 않고 매 단계의 결정만 하므로, DP보다 시간과 공간을 절약할 수 있다.
- 원인: 탐욕 선택 특성이 있으면, 각 단계의 최적해가全域 최적해의 일부가 되므로, 이전 선택을記憶할 필요가 없기 때문이다.
- 결과: 이 속성을 가진 문제에서는 탐욕 알고리즘이 DP보다 훨씬 효율적으로 동일한 최적해를 찾는다.
- 판단: 탐욕으로 풀 수 있는 문제는 항상 DP로도 풀리지만, 그 반대는 성립하지 않는다. 따라서 문제를 분석할 때 "탐욕 선택 특성을 만족하는가?"를 먼저 확인해야 한다.
📢 섹션 요약 비유: 탐욕 알고리즘은 연쇄 反应으로 물건을 파는 상인과 같습니다. 오늘 가장 비싸게 팔 수 있는 가격에 책을 팔고, 내일의 상황은 나중에考え하는 것은、단기적으로는利益을最大化하지만, 전체적으로는後悔하는 선택을 할 수 있습니다.
Ⅲ. 구현 및 실무 응용 (Implementation & Practice)
실무에서 탐욕 알고리즘은 신뢰할 수 있는 빠른 해가 필요한 경우에 사용된다. 全域 최적해를 보장하지 않더라도, 거의 최적에 가까운 해를 매우 빠르게 얻을 수 있으므로, 실시간 시스템이나 대규모 데이터 처리에서 유용하다.
대표적 실무 사례로, 다익스트라(Dijkstra) 알고리즘: 각 단계에서 아직 방문하지 않은 정점 중 최단 거리가 가장 가까운 것을 선택하는 탐욕 알고리즘이다. 음수 가중치가 없는 그래프에서 단일 출발점 최단 경로를 보장한다. 프림(Prim) 알고리즘: 최소 신장 트리(Minimum Spanning Tree)를 구성할 때, 현재 트리에 연결 가능한 간선 중 최소 가중치 간선을 선택하는 탐욕 알고리즘이다. 크루스컬(Kruskal) 알고리즘: 모든 간선을 가중치 순으로 정렬하고, 사이클을 형성하지 않는 간선을依次 선택하는 탐욕 알고리즘이다. 허프만 코딩(Huffman Coding): 문자열 압축에서 출현 빈도가 높은 문자에게 짧은 코드를 부여하기 위해, 가장 빈도가 낮은 두 노드를合并하는 과정을 반복하는 탐욕 알고리즘이다.
[다익스트라 알고리즘: 탐욕의 대표 사례]
┌──────────────────────────────────────────────────────┐
│ │
│ [그래프] │
│ A ---4--- B │
│ | \ /| │
│ 2| \ 5 |1 │
│ | \ / | │
│ C ---3--- D ---2--- E │
│ │
│ 다익스트라 (출발점: A) │
│ ──────────────────── │
│ Step 0: A = {A}, distance[A] = 0 │
│ │
│ Step 1: A에서 갈 수 있는 정점 중 최단: │
│ A→B=4, A→C=2, A→D=∞ │
│ → C 선택 (가장 짧음: 2) │
│ A = {A, C} │
│ │
│ Step 2: C에서 새로 도달 가능한 정점 업데이트: │
│ A→B via C = 2+3=5 < 현재 4? No → 유지 │
│ A→D via C = 2+3=5 → D = 5 │
│ → B 선택 (가장 짧음: 4) │
│ A = {A, C, B} │
│ │
│ Step 3: B에서 업데이트, D via B = 4+1=5 = D 현재값 │
│ → D 선택 (4) │
│ A = {A, C, B, D} │
│ │
│ Step 4: E 선택 (5+2=7) │
│ 최종: A→B=4, A→C=2, A→D=5, A→E=7 │
│ │
│ → 각 단계에서 가장 짧은 정점을 선택하는 탐욕 │
│ → 全域 최단 경로 보장 (음이 아닌 가중치) │
│ │
└──────────────────────────────────────────────────────┘
📢 섹션 요약 비유: 다익스트라의 탐욕 선택은 교차로에서 가장 짧은 거리를 선택하는 내비게이션과 같습니다. "지금은 이 길이 가장 빠르니까"라는 판단만 하고, 다른 경로를 고려하지 않지만, 고속도로 부울럼이 없는 한（음이 아닌 가중치) 이 판단은 결국 全域적으로도 가장 빠른 경로로 이어집니다.
Ⅳ. 품질 관리 및 테스트 (Quality & Testing)
탐욕 알고리즘의 품질 관리에서 가장 중요한 것은 탐욕 선택 특성의 검증이다. 문제가 실제로 탐욕 선택 특성을 만족하는지 엄밀한 수학적证明 없이 적용하면, 예상외의 suboptimal 해가 도출될 수 있다.
품질 관리 체크리스트는 다음과 같다. 탐욕 알고리즘 적용 전 반드시 "탐욕 선택 특성이 존재하는가?"를 수학적/논리적으로 검증해야 한다. 최악의 경우(입력이 극단적으로 불균형)에도 해의 품질이 容認 가능한 수준인지 확인해야 한다. 근사 비율(Approximation Ratio)을 명시적으로計算하여 요구사항을 만족하는지 확인해야 한다.
📢 섹션 요약 비유: 탐욕 알고리즘의 품질 관리는 미식 축구에서 매 번 가장 가까운 터치다운을 求하는 것과 같습니다. 그 순간은 brilliant해 보이지만, 결국 경기에서 진급하려면 全般적인 전략이 필요하듯이, 검증 없는 탐욕 적용은 全域 최적에서 멀어지는 결과를 초래할 수 있습니다.
Ⅴ. 최신 트렌드 및 결론 (Trends & Conclusion)
탐욕 알고리즘의 최신 동향은 **앙상블 방법(Ensemble Methods)**과의 결합이다. 머신러닝에서 AdaBoost는 각 단계에서 가장 오류가 적은弱 분류기(Weak Classifier)를 탐욕적으로 선택하여 최종 강 분류기(Strong Classifier)를 구축한다. 또한 근사 알고리즘(Approximation Algorithm) 분야에서 탐욕이 이론적近似比率(Approximation Ratio)을 보장하는 연구가 활발히 진행되고 있다.
탐욕 알고리즘은 모든 문제에 적용할 수는 없지만, 적용 가능한 문제에서는 압도적인 효율성(시간 O(N), 공간 O(1))으로 동일한 최적해를 보장한다. 기술사 시험에서는 특정 문제가 탐욕으로 풀리는지 DP로 풀리는지를 구분하는 능력과, 그 근거를설명할 수 있는 능력을 검증한다.
📢 섹션 요약 비유: 탐욕 알고리즘은 요리와 같습니다. 레시피 대로 천천히 조리하면(DP) 확실히 맛있지만, 시간 없을 때"Just 맛볼最好的 재료를 먼저投어()"라는 탐욕적 접근은 完全하지는 않더라도 충분히 맛있는 요리가 될 수 있습니다.
핵심 인사이트 ASCII 다이어그램 (Concept Map)
[탐욕 알고리즘 (Greedy Algorithm) 핵심 개념 맵]
┌─────────────────────────────────┐
│ 탐욕 알고리즘 (Greedy Algorithm) │
└────────────────┬────────────────┘
│
┌───────────────────┼───────────────────┐
│ │ │
▼ ▼ ▼
┌──────────────┐ ┌──────────────┐ ┌──────────────┐
│ 핵심 조건 │ │ 알고리즘 구조 │ │ 대표 사례 │
│ Conditions │ │ Structure │ │ Examples │
├──────────────┤ ├──────────────┤ ├──────────────┤
│ 탐욕 선택 특성 │ │ 1. 후보들 중 │ │ 다익스트라 │
│ Greedy Choice│ │ 최적 선택 │ │ Prim MST │
│ 최적 부분구조 │ │ 2. 선택 후 │ │ Kruskal MST │
│ Optimal Sub │ │ 제한 검사 │ │ Huffman Coding│
│ │ │ 3. 종료/계속 │ │ 활동 선택 │
│ │ │ 4. 해 구성 │ │ 분수 배낭 │
└──────────────┘ └──────────────┘ └──────────────┘
│ │ │
└───────────────────┴────────────────────┘
│
▼
┌─────────────────────────────────┐
│ Greedy vs DP vs Brute Force │
├─────────────────────────────────┤
│ Greedy: O(N) ~ O(N log N), 최적해 보장 │
│ DP: O(N²) ~ O(2^N), 항상 최적해 보장 │
│ BF: O(2^N) ~ O(N!), 항상 최적해 보장 │
│ │
│ [적용 가능 판단 기준] │
│ 탐욕 선택 특성 + 최적 부분구조 → Greedy │
│ 중복 하위 문제 + 최적 부분구조 → DP │
│ 둘 다 안 되면 → 근사 or BF │
└─────────────────────────────────┘
참고
- 모든 약어는 반드시 전체 명칭과 함께 표기
- 일어/중국어 절대 사용 금지
- 각 섹션 끝에 📢 요약 비유 반드시 추가
- 최소 800자/파일
- 파일명: 01_, 02_... 형식