탐욕 알고리즘(Greedy Algorithm)은 주어진 문제에 대해 최적의 해답을 얻기 위해 고안된 알고리즘 기법입니다. 이 방식에서는 해답 영역(solution domain) 내에서 매 순간 판단을 내리며, 이름 그대로 '탐욕스럽게' 당장 눈앞에 보이는 가장 좋아 보이는 선택지를 우선적으로 취합니다.
탐욕 알고리즘은 각 단계에서 지역적 최적해(local optimum)를 찾아 나가며, 이러한 선택들이 모여 결과적으로 전역적 최적해(global optimum)에 도달하기도 합니다. 하지만 모든 경우에 그런 것은 아니며, 일반적으로 탐욕 알고리즘이 항상 전역적으로 최적화된 해답을 보장하지는 않는다는 점을 유의해야 합니다.
탐욕 알고리즘이 잘 작동하는 조건
탐욕 알고리즘으로 최적해를 구하려면 문제가 다음 두 가지 성질을 만족해야 합니다.
- 탐욕 선택 속성(Greedy Choice Property): 각 단계에서의 지역적 최선의 선택이 전체 문제의 최적해로 이어질 수 있어야 합니다.
- 최적 부분 구조(Optimal Substructure): 문제의 최적해가 하위 문제들의 최적해로부터 구성될 수 있어야 합니다.
이 섹션에서 다룰 주제
아래는 탐욕 알고리즘을 활용하는 대표적인 문제와 알고리즘 목록입니다.
- 활동 선택 문제(Activity Selection Problem)
- 인접 리스트 표현 기반 다익스트라 알고리즘(Dijkstra's Algorithm for Adjacency List)
- 다익스트라 최단 경로 알고리즘(Dijkstra's Shortest Path Algorithm)
- 허프만 코딩 알고리즘(Huffman Coding Algorithm)
- 정렬된 입력을 위한 효율적 허프만 코딩(Efficient Huffman Coding for Sorted Input)
- 마감 기한이 있는 작업 스케줄링 문제(Job Sequencing Problem with Deadlines)
- 크루스칼 최소 신장 트리 알고리즘(Kruskal's Minimum Spanning Tree Algorithm)
- 최소 동전 교환 문제(Minimum Coin Change Problem)
- 최소 플랫폼 수 문제(Minimum Number of Platforms Problem)
- 프림 최소 신장 트리 알고리즘(Prim's Minimum Spanning Tree Algorithm)
- 인접 리스트 표현 기반 프림 MST(Prim's MST for Adjacency List Representation)
- 분할 배낭 문제(Fractional Knapsack Problem)