탐욕 알고리즘(Greedy Algorithm)

욕심가득 탐욕 알고리즘

탐욕 알고리즘 aka 그리디의 핵심은 선택의 순간 때 가장 최선의 상황만을 선택한다는 것이다

그 상황의 최적해를 구해 최종 해답에 도달하는 것이기 때문에 이 해답이 최적의 답이라는 보장은 할 수가 없다.

단, 어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있다.

이러한 구조를 매트로이드라고 한다.

 

탐욕 알고리즘 문제를 해결하는 방법

1. 선택 절차 : 현재 상태에서의 최적의 해답을 선택한다.

2. 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사한다.

3. 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차(1단계)로 돌아가 위의 과정을 반복

 

탐욕 알고리즘로 최적해를 구할 수 있는 문제는 두 가지 조건을 만족해야 한다.

1. 탐욕스런 선택 조건(greedy choice property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.

2. 최적 부분 구조 조건(optimal substructure) : 문제에 대한 최종 해결 방법이 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

=> 위의 조건이 성립하지 않는 경우 그리디로 반드시 최적해를 구한다는 보장이 없다.

 

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다.

=> 근사 알고리즘 : 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘

---

탐욕 알고리즘 예시  1 - 매트로이드

물건의 가격이 4040원이고 5천원을 냈을 때, 거스름돈을 최소로 받는 경우 탐욕알고리즘을 이용해 최적해를 구할 수 있다.

 

1단계 선택 절차 : 거스름돈을 최소로 주기 위해 가장 큰 돈을 선택한다. 

2단계 적절성 검사 : 1단계에서 선택한 동전의 합이 거스름돈(960원)을 초과하는지 검사한다. 만약 초과한다면 가장 마지막에 선택한 동전을 삭제한다.

3단계 해답검사 : 선택된 동전들의 합이 거스러 줄 금액과 일치하는지 검사. 초과한다면 1단계부터 다시 반복

 

이러한 문제 구조를 매트로이드라고 하며, 탐욕 알고리즘을 이용해 최적해를 구할 수 있다!

 

탐욕 알고리즘 예시 2

도둑이 물건을 훔칠 때 탐욕 알고리즘을 사용한다면 최적해를 구할 수 있을까?

가방에 35kg까지 담을 수 있다했을 때 도둑이 탐욕 알고리즘을 사용한다면 가장 비싼 물건부터 담을 것이다.

물건이 100달러-30kg, 50달러-20kg, 60달러-15kg, 20달러-10kg라 했을 때 

도둑이 100달러짜리 물건을 넣으면 가방에는 더이상 다른 물건을 담을 수가 없다.

그런데 만약, 도둑이 탐욕 알고리즘으로 도둑질을 하지 않는다면, 50달러짜리와 60달러짜리를 훔쳐 총 110달러어치를 훔칠 수 있다.

이러한 경우 탐욕 알고리즘으로 최적해를 구할 수가 없다.

 

 

 

출처

[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬