Greedy Algorithm

[Algorithm] 그리디 알고리즘 (Greedy Algorithm)

1. 그리디 알고리즘 (Greedy Algorithm) ? 현재 상황에서 지금 당장 좋은 것만 고르자 그리디 알고리즘은 이름 그대로 다양한 알고리즘 교재나 문서에서 "탐욕법"으로 소개되고 있는 알고리즘입니다. 탐욕적으로 매 순간 가장 좋은 것을 선택하고, 선택이 미래에 미칠 영향은 고려하지 않습니다. 그렇기 때문에 그리디 알고리즘은 최종적인 결과 도출에 대한 최적해를 보장하지 않습니다. 하지만 그리디 알고리즘은 간단하고 빠르기 때문에 해결할 문제가 그리디 알고리즘을 사용할 조건을 갖출 때 사용합니다. 즉, 그리디 알고리즘을 사용했을 때 최적의 해를 구할 수 있는 문제일 때 입니다. 2. 그리디 알고리즘의 정당성 판단 그리디 알고리즘이 최적의 해를 구할 수 있는 조건은 아래의 두 가지입니다. 탐욕 선택 속..