그리디 알고리즘
그리디 알고리즘
- 각 단계에서 최적의 선택을 해서 얻어진 결론이 최종적인 해답인 경우
- 예
- 거스름돈 1250원을 동전 500, 100, 50, 10원을 사용하여 제공해준다
- 큰 액수의 동전부터 사용한다.
- 1250 / 500 = 2개, 250원이 500원보다 작으므로 100원으로 넘어감.
- 250 / 100 = 2개, 50원이 100원보다 작으므로 50원으로 넘어감.
- 50 / 50 = 1개, 0원이 되었으므로 종료
- 근시안적 방법론
- 단기적인 목표를 중심으로 한 전략적인 접근 방법
- 주로 현재의 문제를 해결하는 데 초점을 맞추고, 장기적인 전망보다는 단기적인 성과를 중요시
- 근사 알고리즘
- 최적의 해를 구할 수 없는 문제에서 해를 구하는 알고리즘
- 항상 최적해를 보장하지는 않지만, 많은 경우에는 최적해에 근접한 값을 구할 수 있다.
- 그리디 알고리즘 주요 속성
- 탐욕 선택 속성
- 각 단계에서 ‘최선의 선택’을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우
- 즉, 각 단계에서 가장 이상적인 선택을 하는 것이 전체 문제의 최적의 답
- 최적 부분 구조
- 전체 문제의 최적해가 ‘부분 문제의 최적해로 구성’
- 즉, 전체 문제를 작은 부분 문제로 나누어서 각각의 부분 문제에서 최적의 해를 구한 후 이를 조합하면 그게 전체 문제의 최적해가 됨
- 그리디 알고리즘 단계
- 문제의 최적해 구하기
- 문제의 구조에 맞게 선택 절차를 정의 : 선택 절차(Selection Procedure)
- 선택 절차에 따라 선택을 수행
- 선택된 해가 문제의 조건을 만족하는지 검사 : 적절성 검사(Feasibility Check)
- 조건을 만족하지 않으면 해당 해를 제외
- 모든 선택이 완료되면 해답을 검사 : 해답 검사(Solution Check)
- 조건을 만족하지 않으면 해답으로 인정하지 않는다
- 선택 절차(Selection Procedure)
- 이 단계에서는 ‘현재 상태’에서 ‘최적의 선택’을 한다. 이 선택은 이후 바뀌지 않는다
- 적절성 검사(Feasibility Check)
- 이 단계에서는 선택한 항목이 ‘문제의 조건’을 만족시키는지 확인
- 조건을 만족시키지 않으면 해당 항목은 제외
- 해답 검사(Solution Check)
- 이 단계에서는 모든 선택이 완료되면 ‘최종 선택’이 ‘문제의 조건을 만족’시키는지 확인
- 조건을 만족시키면 해답으로 인정