greedy algorithm1 [Algorithm] 탐욕 알고리즘 (Greedy Algorithm) 탐욕 알고리즘 (Greedy Algorithm) ■ 정의 다음 그림에서 최댓값을 구하려면 그림1과 같이 5 + 7 + 9 = 21로 구할 것이다. 하지만 탐욕 알고리즘은 그 순간마다 최적의 선택을 하기 때문에 그림2와 같이 5 + 10 + 4 = 19를 구할 것이다. 이처럼 탐욕 알고리즘은 지금 당장 좋은 것만을 고르며, 현재 선택이 나중에 미칠 영향은 고려하지 않는다. 따라서 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 따라서, 탐욕 알고리즘 해법은 그 정당성 분석이 중요하다. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다. 거스름 돈, 활동 선택, 최.. 2023. 4. 3. 이전 1 다음