CHAPTER 3. Greedy

그리디 알고리즘: 탐욕법, 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘

 

시간상으로 매우 효율적이지만, 순간마다 최선의 선택을 하는 방법으로 항상 최적화되지 않음으로 최종 답이 최적이 아닐 가능성이 있다. 그 때문에 순간의 최적해가 전체 문제의 최적해가 되어야 사용할 수 있다.

 

사전에 외우고 있지 않아도 풀 가능성이 높은 문제 유형이지만, 많은 유형을 접해보고 훈련해야 한다.

 

창의력, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력이 필요!

 

그 대상이 무엇인지 고민해보고 푸는 것이 중요하다.

ex) 가장 큰 순서대로, 가장 작은 순서대로 등,,,

정렬 알고리즘과 짝을 이루어 자주 출제된다.

 

---