그리디 알고리즘이란? 욕심쟁이라는 이름에 걸맞게 항상 눈 앞에 있는 가장 큰 이익을 구하는 방법으로 각 단계에서 가장 최선의 선택을 하는 기법이다. 완전 탐색으로 풀기 어려운 문제를 그리디 알고리즘으로 풀면 매우 쉽게 풀 수 있는 매우 강력하면서도 어려운 알고리즘이다. 완전 탐색으론 풀기 어려운 시간 복잡도를 그리디 알고리즘으로 접근하면 보통 $O(N)$ 정도의 시간복잡도로 해결이 가능하게 된다. 하지만 각 단계의 최선의 선택이 최적의 해가 아닐 수 있으므로 그리디 알고리즘을 통해 해결 가능한 문제에만 그리디 알고리즘을 사용하여 풀 수 있다. 예를 들어 동전 문제를 보면 1) 1, 2, 5, 10원, 50원, 100원짜리 동전으로 370원을 만들려면 동전을 몇 개를 사용해야 할까?(단 동전의 개수는 매우..