그리디 알고리즘의 개념

그리디 알고리즘은 단순 무식하게 탐욕적으로 푸는 알고리즘이다.
탐욕적이란, '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다.

가장 공부하기 힘든 알고리즘

방법을 체화해서 다른 문제에도 적용할 수 있는 다른 알고리즘 기법과는 달리 그리디는 문제가 다양하기 때문에 암기한다고 해서 항상 잘 풀 수 없는 알고리즘이다.
따라서 많은 유형을 접해보고 익숙해지는 것이 중요하다.

문제에서 힌트 찾기

기준에 따라 좋은 것을 선택하는 그리디 알고리즘은 문제에서 '가장 큰 순서대로', 가장 작은 순서대로'와 같은 기준이 주어질 때 의심해볼 수 있다.
따라서 정렬 알고리즘과 함께 나오는 경우가 많다.
문제에서 주어지는 예제를 직접 차례차례 써내려가보며 그 안에서 규칙을 찾아내야한다.
코딩테스트에서 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고 규칙을 찾아보려 노력해봐야한다.

정당성을 찾아야한다

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

이 글은 나동빈 님의 '이것이 코딩테스트다' 책을 기반으로 해서 작성되었습니다.