Algorithm
-
그리디 알고리즘(Greedy Algorithm)Algorithm/Algorithm Categories 2022. 1. 1. 19:35
기본 개념 그리디 알고리즘(greedy algorigthm, 탐욕 알고리즘)이란 선택의 상황에서 현재 가장 최선이라고 생각되는 것을 선택해 나가 결과를 도출하는 알고리즘이다. 현재 최적인 값만 탐색하면 되기 때문에 계산 속도가 빨라 실용적이라는 장점이 있으나, 최종 값이 최적 값이라는 보장이 없다는 단점이 존재한다. 그리디 알고리즘을 사용할 때에는 두 가지 조건이 만족되어야 한다. 탐욕 선택 속성(greedy choice property) 최적 부분 구조(optimal substructure) '탐욕 선택 속성'은 현재 선택이 다음 선택과 무관해야 한다는 조건이고, '최적 부분 구조'는 현재 최적 선택이 전체 최적 선택이 되어야 한다는 조건이다. 두 조건을 만족하지 않다면 그리디 알고리즘을 사용했을 때 ..