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

• 그리디 알고리즘이란?

각각의 수행시점에서 가능한 해 중 가장 최적해를 찾아 나가는 알고리즘.

즉 근시안적인 최적해를 찾는다고 할 수 있으며 이러한 근시안적 최적해들을 모아서 최종적으로

문제의 최적해를 구한다.

 

그러나 경우에 따라 수행시점마다의 선택이 해당 시점에 대해서는 부분적으론 최적이지만,

그 선택들을 수집해 최종으로 도출한 해답이 전체적으로 최적이라는 보장은 없다.

 

그리디 알고리즘의 오류

위의 예시에서 해당 트리를 그리디로 접근 시 가장 큰 수는 6이라는 결과가 나오지만

실제로 가장 큰 수는 99이므로 그리디 알고리즘이 최적해를 구하지 못하게 된다.

 

• 그리디로 접근하여 최적해를 구하기 위해 2가지 조건

1) 탐욕적 선택 속성 (Greedy Choice Property) : 이전의 선택이 이후에 영향을 주지 않음.

2) 최적 부분 구조 (Optimal Substructure) : 부분문제의 최적해가 전체에도 그대로 적용 가능함.

 

하지만 이러한 조건이 성립하지 않는 경우에도 탐욕 알고리즘은 근사 알고리즘으로써 사용할 수 있다.

이는 정확한 알고리즘에 비해 계산 속도가 빠른 경우가 많기 때문에 실용적으로 사용이 가능하나

이것이 가용 가능한 값에 어느정도 근사한지에 대해선 정확한 증명이 수반될 수 있다. 

 

그리고 어떠한 특별한 조건을 만족해 그리디 알고리즘이 항상 최적해를 구할 수 있는 문제가 있으며

이를 매트로이드라고 한다.

 

이러한 조건이 만족하는 대표적인 문제로 거스름 돈 문제, 활동 선택 문제 등 이 있다.

 

[백준] 11047 동전 0 - Greedy / Java

해당 문제에서 동전 서로 Ai는 Ai-1의 배수관계가 있는 특수한 조건이 있으며

위의 2가지 조건을 만족하는 구조이므로 그리디 알고리즘으로 접근해 항상 최적해를 구할 수 있는 문제이다.