[Algorithm] 탐욕 알고리즘 (Greedy Algorithm)

탐욕(Greedy) 알고리즘

• 최적해를 구하는 데 사용되는 근시안적 방법
• 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택하여 최종 해답에 도달
  ex) 거스름 돈의 지폐/동전 개수 최소화
• 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만,
  그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여 그것이 최적이라는 보장은 없음
• 탐욕 알고리즘 동작 과정
  1. 해 선택 : 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해 집합(Solution Set)에 추가
  2. 실행 가능성 검사 : 새로운 부분해 집합이 실행 가능한지 확인, 문제의 제약 조건을 위반하지 않는지 검사
  3. 해 검사 : 새로운 부분해 집합이 문제의 해가 되는지 확인
     해 검사 : 아직 전체 문제의 해가 완성되지 않았다면 1의 해 선택부터 다시 시작

👉