[Aragorithm]그리디 알고리즘

📝그리디 알고리즘

그리디 알고리즘은 미래를 보지 않고 현재에서 가장 최적의 상황만을 선택하는 알고리즘이다.

현재 상황에서 가장 좋은 것을 선택해 문제를 해결하는 방법이다. 

특징

• 늘 최적의 해를 도출하는 것은 아니다
• 특정 상황에서는 최적의 해를 보장
• 한번 선택된 것은 반복하지 않는다. 

 

 

🚩문제 공략법

일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.

그리디 해법은 그 정당성 분석이 중요하다

• 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다. 

중요한 것은 탐욕법으로 얻는 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 한다! 

 

 

🧷문제 예시 

거스름 돈 문제 

당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이

있습니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야할 동전의 최소 개수를 구하세요!!!!!

 

• 해당 문제는 가장 쉬운 그리디 문제로 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다.

정당성 분석

만약 화폐 단위가 500원, 400원, 100원이면 어떨까?

• 800원을 거슬러 준다 했을때, 그리디로 풀면 4개가 나오고 400원 만으로 거슬러주면 2개가 나온다.
• 그리디 알고리즘이 최적해를 주지 못하기 때문에 그리디 문제로 풀면 안된다는 것
  • 항상 최적의 해를 가지는지 고민해야 한다.!