[그리디 알고리즘] 당장 좋은 것만 선택하는 그리디

그리디 알고리즘 (탐욕법)

- 어떠한 문제가 있을 때 단순 무식하게, 현재 상황에서 지금 당장 좋은 것만 고르는 방법으로 문제를 푸는 알고리즘

- 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음

- 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형

- 유형이 다양하기 때문에 암기가 아닌 많은 유형을 접해보고 문제를 풀어보며 훈련을 해야 함

- 보통 코딩 테스트에서는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구

- 문제에서 '가장 큰 순서대로'와 같은 기준을 알게 모르게 제시

- 대체로 위 기준은 정렬 알고리즘을 사용하여 만족시킬 수 있으므로 자주 정렬 알고리즘과 짝을 이뤄 출제

- '가장 큰 화폐 단위부터'와 같이 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 효과적

- 문제 풀이를 위한 최소한의 아이디어를 떠올리고 정당한지 검토할 수 있어야 답을 도출 가능

- 코딩 테스트에서 바로 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고 탐욕적인 해결법이 존재하는지 고민

 

※ 다익스트라 알고리즘은 그리디 알고리즘이면서도 '암기'가 필요한 알고리즘