도입

탐욕법은 가장 직관적인 알고리즘 설계 패러다임 중 하나입니다. 탐욕법을 이용한 알고리즘, 혹은 '탐욕적인 알고리즘'은 우리가 원하는 답을 재귀 호출과 똑같이 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 다를 것이 없습니다. 그러나 모든 선택지를 고려해 보고 그중 전체 답이 가장 좋은 것을 찾는 두 방법과는 달리, 탐욕법은 각 단계마다 지금 당장 가장 좋은 방법만을 선택합니다.
탐욕적 알고리즘은 많은 경우 최적해를 찾지 못합니다. 따라서 탐욕적 알고리즘이 사용되는 경우는 크게 두 가지로 제한됩니다.

1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우, 탐욕법은 동적 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용합니다.
2. 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 너무 어렵다면 최적해 대신 적당히 괜찮은 답(근사해)을 찾는 것으로 타협할 수 있습니다. 탐욕법은 이럴 때 최적은 아니지만 임의의 답보다는 좋은 답을 구하는 용도로 유용하게 쓰입니다.

탐욕법 문제는 꽤 어려울 수 있습니다. 한 문제를 탐욕적으로 해결하는 방법이 한 가지만 있는 것이 아닌 경우도 많은데, 이 중 어느 방법을 선택해야 최적해를 구할 수 있을지를 알아내기가 어렵기 때문입니다. 실제로 최적해를 얻을 수 있는 접근이 직관적이지 않은 경우도 많기 때문에 실수에 더 유의해야 합니다. 그러니 탐욕적 알고리즘 연습 문제를 풀 때는 알고리즘의 정당성을 증명하는 과정을 빼먹지 않고 연습하는 것이 좋습니다.

탐욕적 알고리즘 레시피

1. 문제의 답을 만드는 과정을 여러 조각으로 나눕니다.
2. 각 조각마다 어떤 우선순위로 선택을 내려야 할지 결정합니다. 이에 대한 직관을 얻기 위해서는 예제 입력이나 그 외의 작은 입력을 몇 개 손으로 풀어 보는 것이 효율적입니다.
3. 어떤 방식이 동작할 것 같으면 두 가지의 속성을 증명해 봅니다.
   a) 탐욕적 선택 속성: 항상 각 단계에서 우리가 선택한 답을 포함하는 최적해가 존재함을 보이면 됩니다. 이 증명은 대개 우리가 선택한 답과 다른 최적해가 존재함을 가정하고, 이것을 조작해서 우리가 선택한 답을 포함하는 최적해로 바꿀 수 있음을 보이는 형태로 이루어집니다(귀류법).
   b) 최적 부분 구조: 각 단계에서 항상 최적의 선택만을 했을 때 전체 최적해를 구할 수 있는지 여부를 증명합다. 다행히도 대개의 경우 이 속성이 성립하는지 아닌지는 자명하게 알 수 있습니다.

참고문헌: 구종만, 프로그래밍 대회에서 배우는 알고리즘 문제해결전략, 인사이트, (2012)