[코테 공부] 그리디 알고리즘(Greedy Algorithm, 탐욕법)

코딩 테스트를 공부할 때

여러 알고리즘이 사용되지만 

그 중에 가장 기초가 되는 알고리즘이 

오늘의 주제인 탐욕법이다. 

 

하지만 막연하게만 알고

자세한 정의는 하지 못하는 것 같아

이번 기회에 제대로 알아보고자 한다. 

 

---

※ 그리디 알고리즘(탐욕법)의 정의

▶ 그리디 알고리즘은 현재 상황에서 가장 좋은 것(최선의 선택)을 고르는 방법을 의미

▶ 그리디 알고리즘은 동적 프로그래밍을 간단한 문제 해결에 사용하면

지나치게 많은 일을 한다는 것을 착안하여 고안됨

 

---

※ 그리디 알고리즘(탐욕법)의 조건

 

▶ 선택 조건이 탐욕스러워야 함

- 탐욕적인 선택은 항상 안전하다는 것이 보장되어야 함

- 여기서 '안전하다'라는 것은 이 선택으로 인해 전체 문제의

최적해를 반드시 도출할 수 있어야 한다는 것을 의미

=> 문제를 풀 때 그리디 알고리즘을 이용하여

최적해를 도출할 수 있는가를 생각해 충족하면 사용해야 함을 의미

 

▶ 최적 부분 구조 조건

- 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 최적의 해결 방법이어야 한다는 조건

=> 문제의 여러 단계 내 각 단계에 대해 최적해가 도출되어야 한다는 의미