[그리디] 그리디 알고리즘

📌 그리디(Greedy)

⭐ 개념

• 탐욕법이라고도 불림
• 현재상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘
• 최적의 해를 보장

⭐ 대표문제

• 거스름돈 문제 - 무조건 큰 숫자부터 거슬러 주면됨(큰 단위가 항상 작은 단위의 배수이기 때문)

⭐ 수행과정

1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택
2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약조건에 벗어나지 않는 지 검사
3. 해 검사 : 현재까지 선택한 해집합이 전체문제를 해결할 수 있는지 검사
   => 해결하지 못한다면, 1로 돌아가 같은 과정을 반복