10. 탐욕법

10.1 도입

  • 탐욕적인 알고리즘: 우리가 원하는 답을 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어간다는 점에서 완전 탐색, 동적 계획법과 다를 게 없다

    • 그러나 모든 선택지를 고려해 보고, 그 중 전체 답이 가장 좋은 것을 찾는 두 방법과 달리
    • 탐욕법은 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다.

  • 탐욕법은 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않는다.

  • 탐욕법이 사용되는 경우

    1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 경우, 탐욕법은 동적 계획법보다 휠씬 빠르다
    2. 시공간 제약으로 최적해를 찾기 너무 어려우면, 최적해 대신 적당히 괜찮은 답(근사 해) 을 찾는 것으로 타협할 수 있다. 이 때 사용

  • 프로그래밍 대회에서는 주로 1번만 이용된다.

10.1.1 예제, 회의실 예약

  • 이 문제를 해결하는 탐욕적인 방법은 길이와 상관없이, 가장 먼저 끝나는 회의부터 선택하는 것

10.1.2 탐욕적 선택 속성(Greedy Choice Property)

  • 탐욕적 선택 속성(Greedy Choice Property): 답의 모든 부분을 고려하지 않고, 탐욕적으로만 선택하더라도 최적해를 구할 수 있다.
    • 이 속성이 성립할 경우, 우리가 각 단계에서 탐욕적으로 내리는 선택은 항상 최적해로 가는 길 중 하나 이다.
  • 최적 부분 구조: 최적의 선택만을 내려서 전체 문제의 최적해를 얻을 수 있다.
    • 동적 계획법의 속성 중 하나와 같음
  • 탐욕법으로 최적해를 찾을 수 있는 많은 문제들은 동적 계획법으로도 풀 수 도 있다.
  • 탐욕법을 설계하는 좋은 방법은 간단한 입력을 몇 개 손으로 풀어 보면서 패턴을 찾는 것

10.1.3 탐욕적 알고리즘 레시피

  1. 문제의 답을 만드는 과정을 여러 조각으로 나눈다.
  2. 각 조각마다 어떤 우선순위로 선택을 내려야 할지 결정한다.
    • 좋은 방법: 간단한 입력을 몇 개 손으로 풀어 보면서 패턴을 찾는 것
  3. 탐욕적 선택 속성 증명: 다른 최적해가 존재함을 가정하고, 이것을 조작해서 우리가 선택한 답을 포함하는 최적해로 바꿀 수 있음을 보이는 형태로 이루어진다.
  4. 최적 부분 구조 증명

Reference