1. 그리디 알고리즘 (Greedy Algorithm)

단순하지만 강력한 문제 해결 방법이다.

국내 알고리즘 교재에서 단어 그대로 번역하여 탐욕법으로 소개된다.

어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다.

탐욕적 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법

매 순간 가장 좋아 보이는 것을 선택한다.

 

그리디 알고리즘은 문제 출제의 폭이 매우 넓기 때문에

단순 암기를 통해 모든 문제를 대처하기 어렵다.

그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

무작위로 주어진 경우에는 그리디 알고리즘으로는 해결할 수 없다. (무작위인 경우는 다이나믹 프로그래밍으로 해결할 수 있다.)

 

대부분의 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

 

어떤 코딩테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해야 한다.

문제 유형 파악하기 어려울 때 : 그리디 알고리즘 -> 다이나믹 프로그래밍, 그래프 알고리즘 등으로 문제를 해결할 수 있는지 고민한다.