[알고리즘] 탐욕법(Greedy Algorithm)

✔ 목차

1. 탐욕법(Greedy Algorithm)이란?
2. 탐욕법 적용 조건
3. 탐욕법 예시

---

🔎 탐욕법(Greedy Algorithm)이란?

Greedy는 탐욕스러운, 욕심 많은이라는 뜻이다. 뜻에서 알 수 있듯이 이 알고리즘은 탐욕스럽게 가장 좋은 것만 선택하여 해결해나간다.

탐욕법(Greedy Algorithm)

• 각 단계마다 가장 좋은 것만 선택하여 해답을 구함
• 지금 선택이 앞으로 남은 선택에 어떤 영향을 끼칠지 고려하지 않음
• 단계마다 하는 선택은 지역적으로 최선이지만, 모든 단계를 거쳐 최종적(전역적)으로 나온 해답은 최적이란 보장은 없음
• 탐욕법을 적용하기 위해서 지역적으로 최적이면서 전역적으로 최적이어야함

---

🔎 탐욕법 적용 조건

1) 탐욕스런 선택 조건(greedy choice property)

• 앞의 선택이 이후 선택에 영향을 주지 않음
• 각 단계에서 가장 좋은 것을 선택하는 행위가 최적해로 가는 길

2) 최적 부분 구조 조건(optimal substructure)

• 문제의 최적해가 부분 문제에서도 최적해
• 전체 문제 안에 여러 단계가 있고, 모든 여러 단계에서 최적해가 도출되어야 함

---

📌 탐욕법 예시

탐욕법을 사용한 대표적인 알고리즘: 최소 신장 트리 구하기

📝 최소 신장 트리

• 그래프의 모든 정점을 포함하는 트리
• 정점 사이 간선은 최소로 이루어져 있음
  • 즉, 간선의 개수는 정점의 개수 - 1
• 사이클 없음
• 최소 신장 트리 더 알아보기(블로그 링크)

📝 최소 신장 트리 구하는 알고리즘

크루스칼 알고리즘

• 간선을 하나씩 늘려 최소 신장 트리를 만듦
• 남은 간선 중 가중치가 가장 작은 것을 선택했을 때 사이클 생성 여부를 판단하며 선택하는 방식
• 크루스칼 알고리즘 더 알아보기(블로그 링크)

프림 알고리즘

• 정점을 하나씩 늘려 최소 신장 트리를 만듦
• 방문하지 않은 정점과 이어진 간선 중 가장 작은 가중치만 선택하는 방식
• 프림 알고리즘 더 알아보기(블로그 링크)