그리디(탐욕법)

그리디란?

• 현재 상황에서 당장 좋은 것만 고르는 방법
• 매순간 좋아보이는 것을 선택
• 기준 제시 가장 큰 순서, 가장 작은 순서

예시

• 거스름돈 - 가장 큰 화폐부터
• 1이 될때 까지

그리디 알고리즘 정당성

• 모든 문제에 적용 가능 X
• 정당성 검토 필수

종류

• 다익스트라 최단 경로 알고리즘
• 크루스칼 알고리즘