당장 좋은 것만 선택하는 그리디

그리디 알고리즘

그리디라는 이름에서 알 수 있듯이 탐욕적으로 현재 상황에서 지금 당장 좋은 것만 고르는 방법.

즉 매 단계(순회)마다 그 순간에 이용할 수 있는 정보를 바탕으로 문제를 풀 수 있는 실마리가 보이는 방법(최선의 방법)을 "고르려고" 한다. 사전 지식이 없어도 풀 수 있지만, 단순히 현재 가장 좋아보이는 것만을 선택해도 문제를 풀 수 있는지에 대한 고민이 필요하다.

 

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 '가장 큰 순서대로', '가장 작은 순서대로'와 같이 기준을 제시해주거나 어느 정도 유추할 수 있다. 따라서 자주 정렬 문제와 짝을 이룬다.

 

그리디 알고리즘의 가장 중요한 점은 ①최소한의 아이디어를 떠올리고, ②이것이 정당한 지 검토할 수 있어야 한다. 처음에는 다양한 접근을 해보면서 아이디어를 생각해보고 이를 검토하면서 가능한 여러 방법을 생각해보는 것이 중요하다!