= 매 순간의 선택에 가장 최선의 선택을 고르는 알고리즘
대표적인 문제로 동전 거스름돈 문제가 있다.
그리디 알고리즘으로 해결해야하는 문제는, 주로 기준을 제공해주는 경우가 많다.
→ 예: “가장 큰 순서대로”, “가장 긴 순서대로” 등등
그렇기에 정렬 문제와 자주 짝을 이룸
⚠️ 주의점 : 내가 고른 그 상황에서의 최선의 선택이 “정당한 선택인지” 확인해야 한다.
예를 들어 동전이 500원, 400원, 100원 동전이 있다고 했을때 800원을 거슬러 줘야 하는 상황이라면
나는 500원, 100원 3개 라고 4개를 답할 수 있지만 사실 400원 2개가 답이다.
→ 결론: 그리디 알고리즘을 구현할 시에는 알고리즘 자체의 “정당성”을 입증할 수 있어야 함에 주의!
전제를 잘 설정해야 한다.
🥈3