탐욕 알고리즘(Greedy Algorithm)이란?

탐욕 알고리즘은 문제를 해결하는 과정에서 각 단계에서 최선으로 보이는 선택을 하는 알고리즘입니다.

• 지역 최적화(Local Optimization): 각 단계에서 최선의 선택을 함으로써 지역적으로 최적화된 결과를 얻습니다.

• 전역 최적화(Global Optimization): 지역 최적화를 통해 전체 문제에 대한 최적의 해결책을 도출합니다.

• 결정 속도: 탐욕 알고리즘은 빠른 결정을 내릴 수 있어 계산 효율성이 높습니다.

• 단순성과 효율성: 구현이 간단하며, 많은 경우에 효율적인 해결책을 제공합니다.

1. 선택 단계: 현재 상태에서 최선의 선택을 합니다.

2. 타당성 검사: 선택이 문제의 조건을 만족하는지 검사합니다.

3. 해결책 업데이트: 선택을 반영하여 해결책을 업데이트합니다.

4. 최종 해결책 도출: 모든 단계를 거쳐 최종 해결책을 도출합니다.

• 단기적 최적화: 각 단계에서 최선의 선택을 하여 단기적으로 최적화된 결과를 얻습니다.

• 탐욕적 선택 속성: 한 번 선택된 해결책은 번복되지 않습니다.

• 최적 부분 구조: 문제의 최적해가 그 부분 문제의 최적해로부터 구성됩니다.

• 적용 사례: 동전 교환 문제, 분할 가능 배낭 문제, 최소 신장 트리 등

• 장점: 구현이 간단하고, 빠른 속도로 해결책을 도출할 수 있습니다.

• 단점: 항상 최적의 해를 보장하지는 않습니다. 문제에 따라 탐욕적 접근이 적합하지 않을 수도 있습니다. 일부 경우에는 탐욕적 선택이 최적해로 이어지지 않아, 보다 복잡한 알고리즘이 필요할 수 있습니다.