[Algorithm] Greedy

• 한번 선택된 것 번복안함, 이런 특성 때문에 대부분의 탐욕 알고리즘들은 단순 and 제한적인 문제들에만 적용 가능
• 최적화 문제

  가능한 해들 중 가장 좋은(최대 혹은 최소) 해를 찾는 문제

동작과정

1. 해 선택 : 현재의 부분문제의 최적 해 구한 뒤, 이를 부분해집합에 추가

2. 실행 가능성 검사 : 실행 가능성이나 문제의 제약 조건 위반을 확인

3. 해 검사 : 부분해집합이 문제의 최종 해가 되는지 확인

Ex. 거스름돈 문제

• 탐욕 기법으로 큰 동전순으로 나누는 알고리즘은 case2처럼 모든 동전이 금액이 큰 동전의 인수가 아니라면 최소 동전 개수를 구할 수 없음

• 위처럼 탐욕법은 최적해를 반드시 구한다는 보장이 없다
  -> 따라서 탐욕 알고리즘이 최적해를 구하는지 항상 확인해야함

탐욕 기법 알고리즘들