그리디 알고리즘이란?
최적의 값을 구해야하는 상황에서 사용되는 근시안적인 방법론
"각 단계에서 최적이라고 생각되는 것을 선택"후 나가는 방식으로 진행하며 "각 단계에서 최선의 선택을 한 것이 전체적으로 최선이길 바라는 알고리즘" 입니다.
다이나믹 프로그래밍(DP)과는 최적 부분 구조 문제를 푼다는 점에서 약간 다른데, DP가 하위 문제에 대한 최적의 솔루션을 찾은 다음, 이를 이용한 전역 최적 솔루션을 찾는 것이라면
그리디는 각 단계마다 지역 최적해를 찾는 문제로, 문제를 더 작게 줄여나가는 형태다.
1. 그리디 알고리즘의 절차
- 선택 절차 (Selection Procedure) : 현재 상태에서의 최적의 해답을 선택
- 적절성 검사 (Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사
- 해답 검사 (Solution Check) : 원래의 문제가 해결되었는지 검사 후, 해결되지 않았다면 선택 절차로 돌아가서 반복
2. 사용 조건
- 탐욕적 선택 속성 (Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
- 최적 부분 구조 (Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결방법으로 구성
예시
- AI에 있어서 결정 트리 학습법(Decision Tree Learning)
- 최소 신장 트리(Minimum spanning tree)
- 다익스트라 알고리즘
- 허프만 코드
- UNION&FIND 알고리즘
- 프림/크루스칼 알고리즘
문제 유형
- 활동 선택 문제(Activity selection problem)
- 거스름돈 문제
- 제약조건이 많은 대부분의 문제
- 회의실 배정
- 배낭 문제 (일부 경우)
주의 할 점
그리디 알고리즘은 항상 정답을 보장하지 않기 때문에, 문제마다 다음을 확인해야 합니다.
"그리디로 풀면 항상 최적인가?" >> 증명하거나 반례가 없음을 확인해야 함
대부분은 탐색/DP보다 빠르지만 검증이 필요합니다.
늒네입니다.