[알고리즘] Greedy Algorithm (탐욕 알고리즘) 1. Greedy Algorithm이란? - Greedy: 탐욕스러운, 욕심 많은 - 탐욕 알고리즘: 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법 - 최적 해를 구하는 데에 사용하는 근사적인 방법 - 여러 경우 중 하나를 결정할 때마다 그 순간 최적이라고 생각되는 것을 선택하는 방식 > 최종적 해답에 도달 (지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지 고려 X) - 그 순간에는 지역적으로 최적이라도, 지역적인 최적을 수집한 최종적(전역적)인 답이 최적이라는 보장은 없다. - 탐욕 알고리즘에 적용할 수 있는 문제: 지역적, 전역적 모두 최적! * 간단한 예시 - 문제: 노드에서 가장 합이 높은 방법을 선택하는 방법 - 그리디 알고리즘: 상황에 맞게 가.. 이전 1 다음