탐욕 알고리즘(Greedy Algorithm)
탐욕 알고리즘이란? 탐욕 알고리즘은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법니다. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법니다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다. 탐욕 알고리즘 문제를 해결하는 방법 선택 절차 : 현재 상태에서의 최적의 해담을 선택한다. 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사한다. 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한..
Data Structure & Algorithm
2023. 5. 22. 22:45
