탐욕법

• 문제를 여러 단계로 나누고 각 단계에서 가장 좋은 방법만을 선택하는 알고리즘

• 단순한만큼 제한이 존재함.

ex) 회의실 배정 문제

• 탐욕법에서 유명한 문제인 활동 선택 문제
  
  
• n개의 팀이 각각 회의하고 싶은 시간을 제시했을 때, 회의가 겹치지 않게 진행하는 최대 회의수를 구하는 문제
  
  
• solution: 가장 먼저 끝나는 회의부터 선택하고, 이 회의와 겹치는 거슬을 모두 지운 뒤 다시 이 중에서 가장 먼저 끝나는 회의를 선택하는 것을 반복.
  
  
• 정당성 증명
  • 탐욕적 선택 속성: 답의 모든 부분을 고려하지 않고도 탐욕적으로만 선택해도 최적해를 구할 수 있다.
  • 최적 부분 구조: 부분 문제의 최적해에서 전체 문제의 최적해를 도출 할 수 있다.

-Tip: 특정 조건으로 객체들을 정렬해두면 탐욕법의 구현이 쉬워지는 경우가 많다.

탐욕적 알고리즘 레시피

1. 문제의 답을 만드는 과정을 여러 조각으로 나눈다.
2. 각 조각마다 어떤 우선순위로 선택을 내려야 할지 결정하고 이에 대한 직관을 얻기 위해 예제 입력이나 그 외의 입력을 손으로 풀어보는 것이 도움이 된다.
3. 아래의 두가지 속성을 증명한다.
   • 탐욕적 선택 속성: 항상 각 단계에서 우리가 선택한 답을 포함하는 최적해가 있음을 보인다. 보통 앞서 상정한 최적해와 다른 최적 해가 존재함을 가정하고, 다른 최적 해로부터 우리가 상정한 최적해로 변환 할 수 있음을 보이는 형태로 증명가능하다.
   • 최적 부분 구조: 각 단계에서 최적의 선택이 전체의 최적 선택이 됨을 증명한다.