그리디(Greedy) 알고리즘

그리디 알고리즘 (Greedy)

그리디 알고리즘은 탐욕법으로서 당장 주어진 상황에서 가장 좋은 것만 고르는 알고리즘입니다.
순간마다 하는 선택은 그 순간에 대해 지역적으론 최적이지만, 그 선택들을 계속 수집 전역적인 해답을 만들었다고 해서 최적이라는 보장은 없다. 여러 경우 중 하나를 결정해야 할 때, 그 순간 최적적인 해답을 선택해 나가는 방식.

그리디 알고리즘이 문제를 해결하는 방식은 선택 절차(현재 최적의 해답을 선택) 이후 적절성 검사(선택된 해가 문제의 조건을 만족하는지 검사) 를 하고 마지막으로 해답 검사(문제 해결이 되었는지)

결론

• 그리디 알고리즘은 항상 최적의 결과를 도출하진 않지만, 어느 정도는 근사한 값에 빠르게 도출할 수 있다. 그리디 알고리즘을 적용해도 항상 최적해를 구할수 있는 문제가 있고, 이러한 문제에 그리디알고리즘을 사용한다면 빠르게 해결할 수 있다.

근사 알고리즘

어떤 최적화 문제에 근사값을 구하는 알고리즘, 가장 최적화되는 답을 구할 수는 없지만, 빠른 시간에 계산이 가능하며 어느 정도 근사해를 구할 수 있다.

직접 눈으로 본 일도 오히려 참인지 아닌지 염려스러운데 더구나 등뒤에서 남이 말하는 것이야 어찌 이것을 깊이 믿을 수 있으랴? -명심보감-