Greedy Algorithm
-
알고리즘 ch8 Greedy algotithm학교 수업/알고리즘 2020. 6. 15. 18:50
Optimization Problem- 여러개의 가능한 답 중에 가장 최적의 답 또는 최적의 답과 가까운 답을 고르는 문제- 비용을 최소화 한다거나 이익을 최대화 하는 답을 고르는 문제 Greedy Algorithm- 최적해를 구하는 데에 사용되는 근사적인 방법. - 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. (미래를 생각하지 않고 각 단계에서 최선의 선택을 함) Optimization problem 중 greedy 방법을 사용하는 문제1. Minimum Spanning Tree (MST) - Spanning tree 중 사용된 간선들의 가중치 합이 최소인 트리 즉, 그래프 내에 있는 모든 정점들을 가장 적은 수..
-
Greedy Algorithm알고리즘 2020. 3. 17. 16:04
Greedy Algorithm 탐욕 알고리즘개념 : 최적해를 구하는 데에 사용되는 근사적인 방법. 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. (미래를 생각하지 않고 각 단계에서 최선의 선택을 함)그리디 알고리즘으로 최적의 해를 구할 수 있는 문제가 많지는 않다.그리디 알고리즘이 사용되는 경우 -> 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우 (DP보다 수행시간 훨씬 빠르므로 유용) 예시 문제 ① : 동전 개수 10원, 50원, 100원, 500원짜리 동전들을 이용하여 어떤 금액을 표현하자. 이때 각 동전은 무수히 많은 대신 동전 개수를 최소로 사용해야 한다. 풀이>> 무조건 사용할 수 있는 한..