1. 탐욕 알고리즘, 욕심쟁이 알고리즘 (Greedy Algorithm, 그리디 알고리즘) 전략
ㅇ 용어 유래
- 그때그때 상황에 맞는 최상의 해결책을 찾는다는 의미로, `탐욕(Greedy)`이라는 말을 씀
ㅇ 기본 생각
- 매 상황 마다 가장 좋아 보이는 것 만 선택하는 방식
. 완벽한 해결책 보다는 차선책(Suboptimal) 추구
.. 과거나 미래는 생각 않고, 오직 현재 최대의 만족을 추구 (근시안적임)
ㅇ 접근 방식
- 그때그때 가장좋은 해결핵을 찾아가는 기법
. 해를 구하는 일련의 선택 과정 마다,
. 가장 좋아보이는 최선을 선택하면, 전체적으로 최적 해를 구할 수 있다는 방법론으로,
. 각 단계 마다 최상으로 보이는 해결책으로 구한 해들을 모아 제시하게 됨
ㅇ 주의 사항
- 최적 해를 구하는 보장이 없으므로,
- 최적 해를 얻는지 확인하는 절차 필요
2. 탐욕 알고리즘의 적용 요건
ㅇ 주어진 문제가, 최적 부분 구조 (Optimal Substructure)를 갖춰야 함
- 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있는 경우
. 한편, 이런 최적 부분 구조의 경우,
. 재귀호출로 쉽게 구현 가능하나,
. 재귀호출 방식이 항상 효율적이지는 않음
ㅇ 전체 최적 해가, 부 문제(subproblem)들의 최적 해로부터, 생성될 수 있어야 함
- 부 문제 : 원래 문제와 같은 성질을 갖으나, 그 크기 만 작은 경우
- 이를, 탐욕 선택 특성 (greedy choice) 또는 컷 특성 (cut) 이라고도 함
3. 탐욕 알고리즘의 특징 및 적용 例)
ㅇ 주요 특징
- 적당히 괜찮고 근사적이나,
- 매우 빠르게 최적 해를 구할 때 유용
ㅇ 적용 대상
- 종종 시간,공간적 제약 때문에 완벽한 해를 찾기 어려워서,
- 준 최적 해를 찾고자할 때 주로 적용됨
4. 탐욕 알고리즘의 例)
ㅇ 최소값/최대값 등을 구하는 최적화 문제를 다룰 때 적합
ㅇ 동전 거스름돈을 가장 적은 수의 동전으로 주는 문제 (일명, 거스름돈 문제)
ㅇ 배낭 내 합이 최대가 되도록 물체를 넣는 방법 (일명, 배낭 문제)
ㅇ 최소 비용 신장트리를 구하는 알고리즘 (쿠르스칼 알고리즘, 프림 알고리즘)
ㅇ 최단 경로 탐색 알고리즘 (다익스트라 알고리즘) 등
5. 주요 접근 단계
ㅇ 선택 과정 (selection procedure)
- 현 상태 하에서, 최적 해에 포함시킬 대안(해)들을 선택
ㅇ 적절성 검사 (feasibility check)
- 선택된 해가, 주어진 조건을 만족하는지 여부 검사
ㅇ 해답 점검 (solution check)
- 원래의 문제가 해결되었는지를 검사