알고리즘 설계 패러다임 - 06 탐욕법

06  탐욕법 (Greedy Method)

• 완전 탐색이나 동적 계획법과 마찬가지로, 문제를 여러 개의 조각으로 나누고 각 단계마다 한 조각씩 해결

• 완전 탐색이나 동적 계획법은 각 단계에서 모든 선택지를 고려해보고 그 중 전체에 대한 답이 가장 좋은 것을 선택한다면, 그리디 메소드는 각 단계마다 그 때 가장 좋아보이는 것을 선택하고 넘어감

• 그리디 메소드가 항상 최적해를 내는 것은 아님

  • 빠르게 근사해를 찾는 데 사용되기도 함
    
    
    
    

• 최적화 문제 동적 계획법 레시피

  1. 그리디 알고리즘 구상
     ← 간단한 입력 몇 개를 손으로 풀어보면서 패턴을 찾는 것 추천
  2. 해당 그리디 알고리즘이 최적해를 내는지 증명

  • Greedy Choice Property

    • 내가 생각한 방식대로 구성되어 있지 않은 최적해가 있다고 가정
    • 이 최적해의 구조를 변형하여 내가 생각한 방식(탐욕적)으로 선택해도 그대로 최적해임을 증명
    • 결론: 특정 단계에서 다른 게 아니라 탐욕적인 선택을 한 최적해가 존재함을 알 수 있게 된 것

  • Optimal Substructure Property

    • 모든 단계에서 최적의 선택을 하면 그것이 결국 전체에 대한 최적해로 이어진다는 것을 증명
    • (하나의 선택을 했을 때 나머지 부분 문제도 최적의 값을 내도록 해야 함을 증명하면 됨)

  • Integration
    - 첫번째 선택을 탐욕적으로 하기 (이것이 어쨌든 전체에 대한 최적해로 이어질 수 있음이 증명됨)
    - 남은 한덩이의 큰 부분 문제도 최적으로 풀어야 함을 알고 있기 때문에 동일한 과정 반복
    
    
    
    

• 그리디 메소드를 구현하는 데 유용한 STL들

  • vector<pair<int,int>>: 정렬의 기준이 되는 값을 pair의 first에 담고 sort()를 하면 손쉽게 정렬 가능
  • multiset<int>: lower_bound(val)로 lower bound 이상의 최솟값 손쉽게 찾을 수 있음
  • priority_queue<int, vector<int>, greater<int>>