탐욕법

탐욕법 (= Greedy)

매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출할 때 쓰는 알고리즘

현재 상황에서 최적의 해를 구하는 것이기에, 적절한 값으로 인식하여 문제를 해결하는 기법.

⇒ 각 상황에서의 최적의 값이 무조건 종합적인 최적의 값을 보장하지는 않기 때문에 문제의 성격을 잘 파악하여 대입하는 것이 중요.

탐욕법의 조건: 각 부분에서의 선택이 다른 부분에게 영향을 주지 않아야한다 ⇒ 매 순간마다 각 부분에서 최적의 해결이 최종 해결 방법이 될 수 있어야 한다.

탐욕법 예)

• 교환 가능한 동전의 최소 갯수
  • 1970원이 있을 때, 500원 x3, 100원 x4, 50 x1, 10 x2, 금액을 줄여나가기 위해 큰 동전부터 선택하는 최적의 선택을 이어나간 결과로 총 10개의 동전이 필요함을 확인 가능.
  • 동전들이 서로간 배수가 되어 미치는 영향이 없어야 함
    • 500원, 300원, 200원, 50원, 10원이 있을 때, 탐욕법으로는 500원 x3 뒤에 300원 하나를 선택하겠지만, 실제로는 300원을 사용하지 않고 200원 두개를 사용하는 것이 최소 필요 동전 8개를 만들어 준다.
    • 200원과 300원의 배수가 500원이 될 수 없어 선택에 따라 영향을 주기 때문에 발생하는 문제로 탐욕법의 조건에 어긋난다.
• 가능한 많은 수의 회의시간
  • 여러 회의 예약이 있을 때 앞시간부터 순서대로 확인하며 먼저 끝나는 회의가 있는지 확인, 그리고 그 다음에 먼저 끝나는 회의가 있는지를 반복해서 확인하며 매 순간 최적의 조건을 확인하고 배치하면 가능한 많은 수의 회의시간 배정 가능.
• 카드 게임
  • A와 B가 가지고 있는 카드를 비교하여 한 명이 얻을 수 있는 최대 점수를 계산
  • A와 B의 카드를 높은 카드부터 내림차순으로 정렬, 순서대로 비교하면 자연스럽게 얻을 수 있는 최대점수가 나온다.

⇒ 최대한 여러 문제들을 풀고 유형을 보면서 탐욕법 적용이 가능한지 패턴을 파악하는 것이 중요하다.