[알고리즘] Greedy Algorithm (탐욕 알고리즘)
Greedy Algorithme이란? - 미리 정한 기준에 따라 가장 좋은 답을 선택하는 알고리즘 - 최적화 문제를 푸는데 사용 - 근시안적으로 판단하고 해를 구하기 때문에 가장 최적의 해를 구하는 보장이 되지 않는다 - 탐욕 알고리즘은 근사 알고리즘으로 사용하거나, 항시 최적의 해는 아니지만 계산 속도가 빠르다 Greedy 알고리즘 사용처 (탐욕 알고리즘이 잘 작동하기 위해) - 탐욕스런 선택 조건(Greedy choice property)과 최적 부분 구조 조건 (Optimal substructure) 이라는 두 가지 조건이 만족되야한다. - 탐욕스런 선택 조건 : 선택들이 이후의 선택에 영향을 주지 않는다는 뜻 예시 ) 잔돈 800원을 만들기 위해 500원을 집어 들었다. // 최초의 선택 300원..
Algorithm
2020. 10. 2. 14:13