🤔 그리디 알고리즘?
미래의 선택의 결과를 고려하지 않는 현재 상태에서 판단할 수 있는 최적의 선택을 하는 알고리즘입니다. 최적화 문제를 해결하기 위한 간단하고 직관적인 방법입니다. 과정은 다음과 같습니다.
📖 동작 방식
- 값 선택 : 현재 상태에서 가장 최선이라 생각되는 값을 선택
- 현재 선택한 값이 문제 조건에 합당한지 검사
- 선택된 값의 집합이 문제를 해결할 수 있는지 검사
- 문제 해결이 안될 시 1~3까지 과정을 반복하여 결과 도출
❌ 단점
하지만 그리디 알고리즘은 모든 문제에 적용되는 것은 아닙니다. 현 상태에서의 최적의 상황만 선택하기 때문에 잘못된 결과로 이어질 수 있습니다.
📖 그리디 유도
그리디 알고리즘은 잘못된 결과를 도출할 수 있는 알고리즘입니다. 해당 알고리즘을 사용해도 되는지 확인할 수 있는 귀납법을 세워야 합니다.
귀납법은 어떤 것이 모든 경우에 사실임을 증명하는 방법으로, 기본 사례에 대한 사실임을 보여준 다음 이전 사례에 대한 사실을 감안할 때 어떠한 경우에도 사실임을 보여줍니다. ex) A -> B , B -> C , A -> C
귀납법을 활용하여 최적화 문제에 대한 풀이방법으로 그리디를 선택해도 되는지 잘 확인하여 사용해야 합니다.
👨💻 예제
왜? 라는 질문이 사라질 때까지