그리디 알고리즘
현재 상황에서 지금 당장 좋은 것만 고르는 방법
-
탐욕법이라고도 한다.
-
매 순간 가장 좋아보이는 것을 선택한다(최적해를 찾는 방법).
-
현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
문제 해결
-
특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 한다.
-
그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이기 때문에 기준을 제시해준다.
정당성
-
그리디 알고리즘은 모든 알고리즘 문제에 적용할 수 있는 것은 아니다.
-
탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때 매우 효과적이고 직관적
-
그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다.
-
대부분의 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 정당한지 검토할 수 있어야 답을 도출할 수 있다.
