Greedy

1)의미

사전적의미:탐욕스러운 욕심많은
:순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법
:(모든 결과를 봤을때 최고의 효율은 아닐 수 있음)

2)절차

(1)선택절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택
(2)적절성 검사(Feasibility Check):선택된 해가 문제의 조건을 만족하는지 검사
(3)해답 검사(Solution check):원래의 문제가 해결되었는지 검사하고,해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복

3)예시

:편의점에서 거스름돈을 내주려고하는데 동전을 갯수를 최소한으로 거슬러 주는 방법

선택 절차 : 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택한다.
적절성 검사 : 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한다. 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택한다.
해답 검사 : 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다. 액수가 부족하면 1번 과정부터 다시 반복합니다.

4)특성

(1)탐욕적 선택 속성(Greedy Choice Property)::앞의 선택이 이후의 선택에 영향을 주지 않는다
(2)최적 부분 구조(Optimal Substructure):문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성

예를들어 도둑이 탐욕 알고리즘을 사용한다면 가방에 넣을 수 있는 물건중 가장 비싼 물건을 넣는다그다음으로 넣을 수 있는 물건중 가장 비싼 물건을 넣는다고 가정했을때 최고의 효율이 나오지 않을 수있다.그리드의 특징은 매순간 최적이라 생각하는 해답과 이를 토대로 최종 문제의 해답을 도달하는 방식이기 때문에 최적의 결과를 보장하지 못한다.하지만 어느정도 근사값은 빠르게 도출할 수 있는 장점이 있다.