[알고리즘] 그리디/탐욕 알고리즘 Greedy Algorithm

그리디/탐욕 알고리즘 Greedy Algorithm

• 최적해를 구하는 데에 사용되는 근사적인 방법
• 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방법

 

조건

• 탐욕스런 선택 조건(greedy choice property)
  • 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이
• 최적 부분 구조 조건(optimal substructure)
  • 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것

 

예시

Good Case

가장 단 기간에 서울에서 부산까지 도착하는 거리를 구하려면 그 순간 순간 가장 빠른 최단 경로를 구하면 된다.
즉, 서울에서 대구까지의 최적의 거리, 대구에서 부산까지의 최적의 거리를 구하는 것이 그리디 알고리즘이라고 할 수 있다. 또한, 각각의 선택이 다음의 선택에 영향을 미치지 않는다.

 

Bad Case

그리디한 선택을 하게 되면 이전의 선택이 다음에 선택에 영향을 미치게 되고,
또한 그리디한 선택이 최적의 선택이 아니다.

 

---

5585번: 거스름돈

1931번: 회의실 배정