그리디 알고리즘(탐욕법)이란?

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

그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구하며, 문제의 유형이 매우 다양하다. 그래서 사전 지식 없이도 풀이가 가능성이 높은 유형이지만, 정렬/최단 경로 탐색 등과 같이 알고리즘을 미리 알고 있어야 하는 문제에 적용되어 출제되기도 한다.
이 유형은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 가장 큰 순서대로, 가장 작은 순서대로와 같은 기준을 문제에서 알게 모르게 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 정렬 알고리즘과 자주 짝을 이뤄 출제된다.
다만 빠르게 떠올린 아이디어인만큼 그 정당성 분석이 중요하다. 아래와 같은 풀이 방법을 통해 항상 최적의 해를 구할 수 있는지 검토해야 한다.

풀이 방법

1. 당장 좋은 것만 고른다는 말처럼 당장 생각 나는 풀이 방법들 중 가장 적합하다고 판단되는 방식을 고른다.
2. 예제 케이스를 몇개 뽑아 검증한다.
   • 2-4개 정도의 아주 작은 크기로 일반화 할 수 있는 예제 케이스를 사용한다.
   • 필요하다면 엣지 케이스도 고려한다.
   • 검증에 실패하면 다시 1번 과정으로 돌아간다.
3. 필요한 자료구조 목록을 리스트업한 후 적합한 것을 선택한다.
4. 논리적 흐름을 완성한다.