알고리즘/그리디 알고리즘1 그리디 알고리즘(Greedy Algorithm) : 욕심쟁이 알고리즘 📌 그리디 알고리즘이란? 매 선택에서 지금 이 순간 당장 최적인 답을 선택하는 알고리즘 그러나 그리디 알고리즘은 전체에서 최적의 값을 언제나 구할 수는 없다. 예를 하나 들어보자 그리디 알고리즘(Greedy Algorithm)에서 경로를 선택할 때는 선택하는 순간의 최적 값을 찾는다. 그러니까 B, C, D를 선택하는 순간에서는 C 경로인 A, C, E를 고르게 된다. 그러나 실제 최단 경로는 A, D, E다. 이처럼 선택의 순간 그리디 알고리즘에 의해 최적의 값을 선택했지만 전체 선택에 대해서는 최적이 아닌 경로를 선택하게 된 꼴이다. 그리디 알고리즘은 경우의 수를 검증하는 백 트랙킹(Backtracking)을 하지 않기 때문에 전체 문제에서 항상 최적의 값을 구하지는 못한다. 📌 그리디 알고리즘을 사.. 2022. 7. 10. 이전 1 다음