그리디(Greedy) 알고리즘이란?
그리디 알고리즘이란 어떠한 문제가 있을 때 단순 무식하게, 탐욕적(greedy)으로 문제를 푸는 알고리즘을 말한다. 여기서 탐욕적이라는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다.
하나의 문제를 여러 작은 문제(단계)로 나누고 작은 문제(단계)에서의 답을 통합해서 하나의 문제의 대한 답을 내놓는다는 근본적인 개념은 브루털포스나 DP와 비슷하지만, 그리디 알고리즘이 갖는 차이점은 모든 선택지를 고려하지 않는다는 것이다. 그리디 알고리즘은 각 단계에서 가장 좋은것만 고르게 된다.
그리디 알고리즘은 정렬, 최단경로 등의 다른 알고리즘과 비교했을 때 사전에 외우고 있는 지식 없이도 풀 가능성이 높은 유형이다. 따라서 코딩테스트에서 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
그리디 알고리즘의 출제 경향
그리디는 보통 쉬운 문제유형으로 앞쪽에 출제되곤 한다. 코딩테스트는 어려운 문제를 잘 푸는 것도 중요하지만 쉬운 문제를 확실하고 빠르게 잘 푸는 것도 중요하기 때문에, 그리디 유형의 문제를 많이 풀어보고 '이 문제는 그리디로 풀 수 있겠구나' 하고 바로 떠올릴 수 있는 감을 익히는 것이 중요하다.
그리디 알고리즘은 (가장 큰/작은 순서대로와 같이) 기준에 따라 좋은 것을 선택하는 알고리즘이므로 대체로 문제를 푸는 과정 중 정렬 알고리즘을 사용해야 하는 경우가 많다. 문제를 많이 풀어본 경험이 없다면, 대부분 언어에서 정렬하는 함수를 기본 라이브러리로 제공해 주니 사용법을 익혀 놓자!
그리디 문제 해결 과정
- 문제 해결 과정을 여러 작은 문제(단계)로 나눈다.
- 나눠진 작은 문제에 대해서 내린 최적의 선택이 무조건 최적해로 이어지는지 판단한다.
(최적해를 구하기 위해 모든 경우의 수를 다 봐야 하는지, 바로 선택할 수 있는지 판단) - 굳이 모든 경우를 보지 않아도 된다면, 즉 그리디로 풀 수 있다는 판단을 했다면 빠르게 구현!