[알고리즘] 욕심쟁이 알고리즘 | 그리디 알고리즘(Greedy Algorithm)동적 계획법을 공부하다가 궁금해진 알고리즘

그리디 알고리즘을 한 마디로 정의해 보자면,

 

눈 앞에 보이는 최적의 상황만을 보는 알고리즘이라고 할 수 있다.

 

이 알고리즘은 항상 최적해를 도출하는 것은 아니다. 그러나 어느정도는 최적해에 근사한 값을 빠른 속도로 구할 수 있다는 장점을 가진다.

또한 특정한 상황에서 최적해를 보장할 수 있다는 장점이 있다.

그리디 알고리즘의 대표적인 예제는 거스름돈 문제이다.

예를 들어 730원을 거슬러주어야할때 10원짜리 동전을 73개 거슬러 주기 보다, 500원짜리 1개와 30원짜리 3개를 주는 것이 편하다.

따라서 이 경우 '무조건 더 큰 화폐 단위부터 거슬러 준다'는 알고리즘만 지킨다면 최적의 해를 보장할 수 있다. 

 

그리디 알고리즘은 극단적으로 문제를 접근한다는 점에서 ( 무조건적으로 큰 경우대로, 작은 경우대로... ) 

정렬 기법이 함꼐 사용되는 경우가 많다.

 

한 마디로 정의하자면,

단순하게 큰 경우부터 찾는 알고리즘과 같이 간단하게 탐욕적으로 문제를 해결하는 기법을 그리디 알고리즘이라고 하는 것이가.

단순하게 한 가지 경우만을 보고 좇는다는 의미로 해석하면 될 것 같다!!