[알고리즘] 욕심쟁이 알고리즘(Greedy Algorithm)

해당 게시글은 비전공자이자 초보 개발자 지망생이 작성한 글로 정확하지 않을 수 있으니 참고해주시길 바랍니다! 

피드백과 정보 정정 댓글은 환영입니다 :)

 

1) 그리디 알고리즘이란?

직역하면 욕심쟁이 알고리즘이라는 뜻을 가진 해당 알고리즘은 선택의 순간이 올 때마다 당장 최적인 답을 선택하는 풀이 방법을 의미한다. 물론, 해당 풀이 방법을 사용한다고 해서 종합적으로 보았을 때 최적의 해가 도출된다는 것이 항상 보장되지는다. 하지만 부분 문제들의 최적해들의 집합이 전체 문제의 최적해가 되는 문제의 경우 그리디 알고리즘을 활용하여 해결할 수 있다. 

 

2) Optimal Substructure Property?

전체 문제의 최적해가 부분 문제들의 최적해의 집합으로 이루어져있을 때를 의미한다. 

 

3) Greedy Choice property?

최적해가 매 선택마다 최적의 해를 선택했을 때 얻어질 수 있을 때를 의미한다.

 

-> Optimal Substructure Property + Greedy Choice property 를 동시에 가지고 있는 문제의 경우, Greedy Algorithm을 활용하여 문제를 해결할 수 있다. 또한, Greedy Algorithm을 활용하여 풀 수 있는 문제들은 Dynamic Programming으로 해결이 가능하며, 이 경우에는 Greedy가 DP보다 더 효율적이다.