26.03_탐욕 알고리즘_22.09.27

탐욕 알고리즘, Greedy

>의미

: 선택의 시점일 때마다 해당 시점에서 최적인 선택만을 쫒아 답을 도출하는 알고리즘.

(예시) 최소 갯수의 돈으로 거스름돈 건내주기

: greedy는 특정 조건에서 원하는 답을 도출할 수 있지만, 원하는 답이 아니더라도 근사값을 도출하기 적절하며, 때문에 근

사 알고리즘으로도 사용한다.

>절차

• 선택 절차(Selection Procedure)

: 현재 시점에서의 최적의 해답을 선택하는 절차

• 적절성 검사(Feasibility Check)

: 선택된 해가 문제의 조건을 만족하는지 검사

• 해답 검사(Solution Check)

: 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복

>Greedy 사용하기 적합한 조건

• 탐욕적 선택 속성(Greedy Choice Property)

: 앞의 선택이 이후의 선택에 영향을 주지 않음

• 최적 부분 구조(Optimal Substructure)

: 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성

: 즉, 문제를 큰 문제를 해결 후 작은 문제로 쪼갤 수 있고 마지막 작은 문제 해결 시 원래 문제가 모두 해결돼야 한다.

>Greed 예시

1. 활동 시간 문제 (참고: https://hongjw1938.tistory.com/172)

2. 거스름돈 문제

3. 박스 포장 문제

//Greed 문제 공통점

=>정해진 바운더리에서 최대의 결과를 취할 때, 주로 사용