1. Greedy 알고리즘 (탐욕법)

개념

당장 눈 앞에 보이는 최적의 상황을 쫓기. 그래서 '그리디'라고 불리는 것

 

예시1) 거스름돈 주기

- 가장 큰 화폐 단위부터 거슬러 주기가 최고의 알고리즘

- 큰 단위가 항상 작은 단위의 배수이므로 작은 단위들의 종합으로 다른 해가 나올 수 없다는 게 보장되어야 탐욕법을 사용했을 때 최적의 해가 나오게 됨

- 만약 500, 400, 100원이 있는데 800원을 거슬러줘야 할때 400*2 가 최적의 해이지만 그리디에 따라 큰 단위인 500부터 주면 500*1 + 100*3 이 됨

 

무조건 큰 경우부터, 작은 경우부터, 긴 경우부터 등 극단적 접근 => sort 기법 자주 사용

예시2) 크루스칼

- 모든 간선 정렬 후 짧은 간선부터 연결하는 최소비용 신장트리 알고리즘

 

최적의 해를 못찾을 경우, 동적 프로그램 등 기타 알고리즘 방식을 사용해야