그리디 알고리즘

- 탐욕적으로 문제를 해결하는 방법(극단적으로?)

- 당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘

- 가장 단순한 형태의 알고리즘

- 최적의 값은 아니지만 최적의 값에 근사값을 빠르게 구할 수 있다

- 특정한 상황에서 최적의 해를 보장

- 극단적으로 문제에 접근하기 때문에 정렬 기법이 함께 사용되는 경우가 많음 (무조건 큰, 작은, 긴, 짧은...)

- 대표적 예시 : 크루스칼 알고리즘 (모든 간선 정렬하고 나서 짧은 간선 연결하는 최소 비용 신장 트리 알고리즘)

 

예시

- 거스름 돈을 줄 때 560원을 준다면

- 1원 555개보다 500원 1개 50원 한개 10원 1개가 낫다.

=> 무조건 더 큰 화폐 단위부터 거슬러 준다 (최적의 값을 보장)

 

참고

blog.naver.com/ndb796/221242106787

34. 그리디(Greedy) 알고리즘