Greedy Algorithm   탐욕 알고리즘

1. 탐욕 알고리즘, 욕심쟁이 알고리즘 (Greedy Algorithm, 그리디 알고리즘) 전략 

  ㅇ 용어 유래
     - 그때그때 상황에 맞는 최상의 해결책을 찾는다는 의미로, `탐욕(Greedy)`이라는 말을 씀

  ㅇ 기본 생각
     - 매 상황 마다 가장 좋아 보이는 것 만 선택하는 방식
        . 완벽한 해결책 보다는 차선책(Suboptimal) 추구
           .. 과거나 미래는 생각 않고, 오직 현재 최대의 만족을 추구 (근시안적임)

  ㅇ 접근 방식
     - 그때그때 가장좋은 해결핵을 찾아가는 기법
        . 해를 구하는 일련의 선택 과정 마다,
        . 가장 좋아보이는 최선을 선택하면, 전체적으로 최적 해를 구할 수 있다는 방법론으로,
        . 각 단계 마다 최상으로 보이는 해결책으로 구한 해들을 모아 제시하게 됨

  ㅇ 주의 사항
     - 최적 해를 구하는 보장이 없으므로, 
     - 최적 해를 얻는지 확인하는 절차 필요


2. 탐욕 알고리즘의 적용 요건

  ㅇ 주어진 문제가, 최적 부분 구조 (Optimal Substructure)를 갖춰야 함
     - 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있는 경우
        . 한편, 이런 최적 부분 구조의 경우,
        . 재귀호출로 쉽게 구현 가능하나, 
        . 재귀호출 방식이 항상 효율적이지는 않음

  ㅇ 전체 최적 해가, 부 문제(subproblem)들의 최적 해로부터, 생성될 수 있어야 함
     - 부 문제 : 원래 문제와 같은 성질을 갖으나, 그 크기 만 작은 경우
     - 이를, 탐욕 선택 특성 (greedy choice) 또는 컷 특성 (cut) 이라고도 함


3. 탐욕 알고리즘의 특징 및 적용 例)

  ㅇ 주요 특징
     - 적당히 괜찮고 근사적이나, 
     - 매우 빠르게 최적 해를 구할 때 유용

  ㅇ 적용 대상
     - 종종 시간,공간적 제약 때문에 완벽한 해를 찾기 어려워서,
     - 준 최적 해를 찾고자할 때 주로 적용됨 


4. 탐욕 알고리즘의 例)

  ㅇ 최소값/최대값 등을 구하는 최적화 문제를 다룰 때 적합
  ㅇ 동전 거스름돈을 가장 적은 수의 동전으로 주는 문제 (일명, 거스름돈 문제)
  ㅇ 배낭 내 합이 최대가 되도록 물체를 넣는 방법 (일명, 배낭 문제)
  ㅇ 최소 비용 신장트리를 구하는 알고리즘 (쿠르스칼 알고리즘, 프림 알고리즘) 
  ㅇ 최단 경로 탐색 알고리즘 (다익스트라 알고리즘) 등


5. 주요 접근 단계

  ㅇ 선택 과정 (selection procedure)
     - 현 상태 하에서, 최적 해에 포함시킬 대안(해)들을 선택

  ㅇ 적절성 검사 (feasibility check)
     - 선택된 해가, 주어진 조건을 만족하는지 여부 검사

  ㅇ 해답 점검 (solution check)
     - 원래의 문제가 해결되었는지를 검사