[알고리즘] 그리디 알고리즘의 원리와 예시

그리디 알고리즘의 개요

그리디 알고리즘(탐욕 알고리즘)은 최적해를 구하는 문제를 해결할 때 사용되는 알고리즘 기법 중 하나입니다. 그리디 알고리즘은 각 단계에서 최적의 선택을 하며 전체적인 해답을 구성하는 방식으로 작동합니다. 그리디 알고리즘은 지역적으로 최적인 선택을 연속적으로 수행하여 전체적으로도 최적해를 얻는 것을 목표로 합니다.

---

그리디 알고리즘의 원리

그리디 알고리즘은 각 단계에서 최적의 선택을 한다는 특징을 가지고 있습니다. 이 선택은 해당 단계에서 가장 유리한 선택이지만, 전체 문제 해결을 위한 최적해가 되지 않을 수도 있습니다. 따라서 그리디 알고리즘을 사용할 때에는 각 단계에서의 선택이 전체적인 해답에 미치는 영향을 신중하게 고려해야 합니다.

---

그리디 알고리즘의 예시

그리디 알고리즘을 이해하기 위해 두 가지 대표적인 예시를 살펴보겠습니다.

 

동전 거스름돈 문제

동전 거스름돈 문제는 주어진 금액을 동전으로 최소한의 개수로 거슬러주는 문제입니다. 이때 그리디 알고리즘은 가장 큰 금액의 동전부터 차례로 사용하면 최소한의 동전 개수로 거스름돈을 줄 수 있습니다.

주어진 동전: [500, 100, 50, 10]
금액: 780원

그리디 알고리즘:
- 500원 동전 1개, 거스름돈: 280원
- 100원 동전 2개, 거스름돈: 80원
- 50원 동전 1개, 거스름돈: 30원
- 10원 동전 3개, 거스름돈: 0원

총 동전 개수: 7개

 

활동 선택 문제

활동 선택 문제는 여러 개의 활동이 주어졌을 때, 겹치지 않고 최대한 많은 활동을 선택하는 문제입니다. 그리디 알고리즘은 종료 시간이 빠른 활동부터 선택하면 최대한 많은 활동을 선택할 수 있습니다.

활동 리스트: [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]

그리디 알고리즘:
- (1, 4), (5, 7), (8, 11), (12, 14) 선택

총 선택된 활동 개수: 4개

이와 같이 그리디 알고리즘은 각 단계에서 최적의 선택을 하여 문제를 해결합니다. 그러나 항상 최적해를 보장하지는 않으며, 문제의 특성에 따라 성능이 달라질 수 있습니다.