탐욕 알고리즘
-
[알고리즘 개념] 탐욕 알고리즘알고리즘 공부/알고리즘 개념 2020. 8. 16. 18:52
탐욕 알고리즘 탐욕 알고리즘은 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다. 즉, 동적 프로그래밍을 보완하는 알고리즘인 것이다. 탐욕 알고리즘은 각 단계에서 조건에 맞는 최선의 선택을 하는 기법이다. 그렇기 때문에 모든 문제에 대해서 탐욕 알고리즘이 통하지 않는다. 예를 들면, 지금 선택하면 1개의 마시멜로우를 받고, 1분을 기다리면 2개의 마시멜로우를 준다고 했을 때 탐욕 알고리즘은 1개의 마시멜로우를 받는 선택을 내린다. 따라서 어떤 문제가 탐욕 알고리즘이 통하는지 잘 판단하여야 한다. 탐욕 알고리즘은 다음과 같은 과정을 거친다. 1. 해 선택 : 현재 가장 최적인 해를 구하여, 이를 부분해 집합에 추가한다. 2. 적절성 검사 : 새로운 부분해 집합이 적절한..