Greedy Algorithm : 각 단계에서 최적이라고 생각하는 것을 선택해나가는 방식으로 전체의 최적해를 구하는 알고리즘

주요 속성

• 탐욕 선택 속성(Greedy Choice Property)
• 최적 부분 구조(Optimal Substructure)

자세한 설명은 해당 포스팅 참고

알고리즘 증명

그리디 알고리즘은 잘못된 논리로 인해 증명이 없다면 휴리스틱으로 빠질 가능성이 높다.

• Greedy stays ahead : 탐욕 알고리즘의 선택이 가상의 최적 알고리즘보다 항상 좋다를 증명
• Certificate argument : 해당 해가 최적해임을 증명
• Exchange argument : 최적해를 변경해도 상관없는 그리디의 해로 점점 바꿔가며 결국 동일하다를 증명

참고

https://gazelle-and-cs.tistory.com/59