[코딩테스트 / 알고리즘] 그리디(greedy)
그리디 알고리즘
Greedy
- 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘.
- 관찰을 통해 탐색 범위를 줄이는 알고리즘.
- 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘.
그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다. 탐욕법이라고도 불린다. 이름에서 알 수 있듯이 어떠한 문제가 있을때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
그리디 알고리즘 문제는 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이라는 특징이 있다.
그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준을 알게 모르게 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.
그리디 알고리즘 이상적인 풀이 흐름
- 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다.
- 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명.
- 구현해서 문제를 통과한다.
그리디 알고리즘 현실적인 풀이 흐름
- 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다.
- 탐색 범위를 줄여도 올바른 결과를 낸다는 강한 믿음을 가진다.
- 믿음을 가지고 구현해서 문제를 통과한다.
그리디 알고리즘 절망적인 풀이 흐름
- 관찰을 통해 탐색 범위를 줄이는 잘못된 방법을 고안.
- 탐색 범위를 줄여도 올바른 결과를 낸다는 강한 믿음을 가진다.
- 믿음을 가지고 구현했는데 계속 틀린다.