탐욕법(Greedy Algorithm)에 대해 알아보기

★ 탐욕법(Greedy Algorithm)

최적의 선택을 위한 알고리즘

탐욕법(Greedy Algorithm)은 현재 상황에서 가장 좋아 보이는 선택을 반복적으로 수행하여 문제를 해결하는 알고리즘 설계 기법이다.

탐욕법은 최적해를 보장하기 위해 문제 자체가 특정 조건(탐욕적 선택 속성, 최적 부분 구조)을 만족해야 한다.

---

탐욕법의 핵심 개념

1. 탐욕적 선택(Greedy Choice)
   • 각 단계에서 부분적인 최적 선택을 한다.
   • 과거의 선택은 고려하지 않고, 현재 상태에서 가장 최적인 결정을 내린다.
2. 최적 부분 구조(Optimal Substructure)
   • 문제의 최적해는 부분 문제의 최적해로 구성될 수 있어야 한다.

---

탐욕법의 장단점

장점

• 빠른 계산 속도: 다른 알고리즘(예: 동적 계획법)보다 간단하고 계산 속도가 빠르다.
• 직관적 구현: 규칙에 따라 바로 구현이 가능하다.

단점

• 글로벌 최적해를 보장하지 못함: 모든 문제에 적용할 수 있는 것은 아니다.(예: 탐욕법이 항상 최적해를 보장하려면 문제에 탐욕적 선택 속성과 최적 부분 구조가 존재해야 한다.)
• 탐욕적 선택이 항상 최적이 아닐 수 있음: 문제에 따라 동적 계획법, 완전 탐색 등 다른 접근법이 필요.

---

탐욕법의 적용 사례

탐욕법이 적용 가능한 대표적인 문제 유형은 다음과 같다:

1. 동전 거스름돈 문제

• 주어진 동전의 최소 개수로 특정 금액을 거슬러 주는 문제.
• 조건: 동전의 단위가 배수 관계여야 한다(예: 1원, 5원, 10원, 50원 등).

2. 활동 선택 문제

• 여러 활동 중 최대한 많은 활동을 수행하는 문제.
• 각 활동은 시작 시간과 종료 시간이 주어지며, 겹치지 않도록 선택.

3. 최소 신장 트리(MST)

• 그래프에서 모든 정점을 최소 비용으로 연결하는 문제.
• 대표적인 알고리즘: 크루스칼(Kruskal), 프림(Prim).

4. 허프만 코딩(Huffman Coding)

• 문자 데이터 압축 알고리즘으로, 탐욕적 방법으로 최적의 접두사 코드를 생성.

---

정리

탐욕법은 문제를 빠르고 간단하게 해결할 수 있는 유용한 도구다. 하지만 모든 문제에 적용할 수 있는 것은 아니며, 문제의 특성을 잘 파악하여 탐욕법이 적합한지 판단해야 한다.