오늘은 욕심쟁이 알고리즘에 대해 알아보자~ Greedy Algorithm 복잡한 문제를 쪼개서 해결한다. 쪼개진 조각들이 다 최선의 답을 가지면 전체도 최적의 해를 가지지 않을까? 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 눈앞의 이익만 우선 추구하는 알고리즘의 설계 패러다임 매 단계마다 최선의 방법만 선택하면 되기 때문에 탐색 범위가 줄어든다! 주의점 그리디 알고리즘은 각 단계에서 가장 좋은 방법만 선택하면 전체에 대한 최적해를 가진다 전제하에 정당성을 가지는 것이다. 그렇기 때문에 그리디 알고리즘을 떠올렸을 땐, 정당성을 증명하는 것이 필수!!!! 만약 최적해가 보장되지 않는 경우 그리디 알고리즘을 사용하면 망한다. 그리고 그리디 알고리즘이 최적해를 보장하는 경우는 많지 않다. 함부로 ..