[자료구조] 탐욕법 (그리디 알고리즘 - Greedy algorithm)

💛 탐욕법이란?

현재 상황에서 가장 좋은 선택을 고르는 알고리즘

이전에 살펴본 동적 프로그래밍을 간단한 문제 해결에 사용하면 지나치게 일을 많이 한다는 문제점을 해결하기 위해 등장했다.

지나치게 일을 많이 하는 경우를 방지해주긴 하지만, 항상 최적해를 보장하는 동적 프로그래밍에 비해 탐욕법은 항상 최적의 해를 보장하지는 않는다.

 

위의 간단한 트리를 보면서 탐욕법으로 구한 해와 동적 프로그래밍으로 구한 해가 어떻게 다른지 알아보자

 

루트 노드에서 시작해서 지나친 모든 노드의 수를 더했을 때 가장 결과 값이 큰 경로를 구한다고 하면

 

노란색의 노드를 지나가는 경로가 탐욕법으로 구한 결과이고

연두색의 노드를 지나가는 경로가 동적 계획법으로 구한 결과 이다.

 

이처럼 탐욕법은 현재 시점에서 하는 선택만을 고려하기 때문에 항상 최적해가 나온다는 보장은 없다.

---

💙 탐욕법의 조건?

이런 탐욕법을 사용하기 위해서는 2가지 조건이 필요하다(옳은 해를 구하기 위해)

 

✔ 탐욕스러운 선택 조건

  - 탐욕스러운 선택이 항상 최적해를 반드시 도출한다는 것이 보장되어야 한다. (탐욕법으로 문제를 풀어도 최적해를 구할 수 있을 것 같을 때 탐욕법으로 문제를 해결한다.)

 

✔ 최적 부분 구조 조건

  - 여러 단계를 통해 최종 해를 도출할 때, 이 단계마다 최적해가 도출되고, 이것들이 모여 최종의 최적해를 구할 수 있어야 한다.

---

💜 대표적인 문제?

그냥 쉽게 생각해볼 수 있는 것은 거스름돈 문제이다.

 

돈을 거슬러 줄때, 최대한 큰 단위를 우선해서 주어야 한다는 요구조건이 붙는다면 탐욕법을 쓰기 최적의 문제가 된다. 남은 금액을 제일 큰 단위 부터 나눠가며 카운트하면 되기 때문이다.

 

아래에는 탐욕법을 연습해 볼 수 있는 몇 가지 문제의 링크들이다.

https://programmers.co.kr/learn/courses/30/lessons/42862

코딩테스트 연습 - 체육복

https://programmers.co.kr/learn/courses/30/lessons/42885

코딩테스트 연습 - 구명보트