그리디 알고리즘이란?
선택의 순간마다 선택한 최적해가 결국 전체의 최적해
순간순간의 선택은 그 순간에 대해서는 최적이지만, 전체의 최적이라는 보장이 없기 때문에 한정된 사용
과정
1. 선택 절차 (Selection Procedure)
현재 상태에서의 최적해를 선택
2. 적절성 검사 (Feasibility Check)
선택된 해가 문제의 조건을 만족하는지 검사
3. 해답 검사 (Solution Check)
문제가 해결되었는지 검사, 해결되지 않았다면 선택 절차로 돌아가 반복
조건
탐욕적 선택 속성 (Greedy Choice Property)
이전의 선택이 이후의 선택에 영향을 주지 않음
최적 부분 구조 (Optimal Substructure)
문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성
위 두가지 조건이 만족하지 못한다면, 그리디 알고리즘은 최적해를 구하지 못함
특별한 구조가 있는 문제에 대해서는 그리디 알고리즘이 언제나 최적해 탐색 가능
(ex. 매트로이드)
예시
매트로이드
가장 널리 드는 예시
특정 가격의 물건을 구입하는데 가장 적은 동전을 사용하고, 각 동전의 사용 개수를 구하는 문제
4650원 짜리 물건을 구매하는 상황에서
500원 9개
100원 1개
50원 1개
이렇게 사용하는 것이 가장 적은 양의 동전을 사용하는 방법
그리디 알고리즘을 위 문제의 해결에 적용
1. 선택절차
동전 개수를 줄이기 위해 가장 가치가 높은 동전의 선택을 우선
2. 적절성 검사
1번 과정을 통해 선택된 동전 합이 물건의 가격을 초과하는지 검사
초과한다면, 마지막에 선택한 동전을 삭제하고 1번으로 돌아가 한 단계 작은 동전을 선택
3. 해답 검사
선택된 동전들의 합이 물건의 가격과 일치하는지 검사
부족하면 1번 과정부터 반복
위 순서대로 500원짜리 동전을 9개(4500원) 선택 후, 한 단계 낮은 100원짜리 동전을 1개 (4600원), 50원짜리 동전을 1개( 4650) 선택
결국 각 순간에 최선의 선택이 전체에서의 최선의 선택이 됨