[Greedy Algorithm] 그리디 알고리즘 - 정당성 증명은 필수

오늘은 욕심쟁이 알고리즘에 대해 알아보자~

 

Greedy Algorithm

• 복잡한 문제를 쪼개서 해결한다. 쪼개진 조각들이 다 최선의 답을 가지면 전체도 최적의 해를 가지지 않을까? 
• 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 
• 눈앞의 이익만 우선 추구하는 알고리즘의 설계 패러다임
• 매 단계마다 최선의 방법만 선택하면 되기 때문에 탐색 범위가 줄어든다!

 

주의점

그리디 알고리즘은 각 단계에서 가장 좋은 방법만 선택하면 전체에 대한 최적해를 가진다 전제하에 정당성을 가지는 것이다.

그렇기 때문에 그리디 알고리즘을 떠올렸을 땐, 정당성을 증명하는 것이 필수!!!!

만약 최적해가 보장되지 않는 경우 그리디 알고리즘을 사용하면 망한다. 

그리고 그리디 알고리즘이 최적해를 보장하는 경우는 많지 않다. 

함부로 사용하지 말고, 맞을 것 같아도 항상 의심해보자. 

 

장점

최적해가 보장되면 나이스다. 

탐색 범위가 줄어들기 때문에 효율적

 

현실적으로.. 그냥 믿음을 가지고 풀자~ 

---

한 줄 정리

그리디 알고리즘 : 항상 제일 좋은 것을 선택하면 최적해가 될거야. 진짜 그럴까? 증명하고 사용하자!!

 

틀린 내용이 있다면 댓글 부탁드립니다  :)