그리디

Greedy라는 말을 직영하면 ‘탐욕적인’ 이며 국내에서는 탐욕법으로 소개된다. 이름에서도 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다.

현재 상황에서 지금 당장 좋은 것만 고르자

다시 말해 특정 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악해야 한다.

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준을 은근히 제시해준다. 대체로 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

그리디 알고리즘의 정당성

그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다. 해법을 적용해봤을 때 다른 case를 적용해도 최적의 해가 나오는 것은 아닌지 검토해보아야 한다.

문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토하자

어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보자. 만약 오랜 시간을 고민해도 그리디 알고리즘을 해결할 수 없다면, 다른 알고리즘으로 해결할 수 있는지를 고민해보자.

ref
이것이 취업을 위한 코딩 테스트다 with 파이썬