그리디 알고리즘

매 순간 현재 기준으로 최선의 답을 선택해 나가는 방법

- 빠르게 근사치를 계산할 수 있다.

- 결과적으로는 최적해가 아닐 수 있다. 

 

 

그리디 알고리즘 예시

 

1) Actiity Selection Problem

-N 개의 활동과 각 활동의 시작/종료 시간이 주어졌을 때

-한 사람이 최대한 많이 할 수 있는 활동의 수 구하기

 

-> 이것을 종료 시간 기준으로 정렬

-> 먼저 종료되는 활동순, 겹치지 않는 순으로 선택

 

-종료 시간이 빠른 순으로 선택 처음은 종료시간이 3인 C가 옴

- A는 5에 종료를 하지만 시작이 1에서 함으로 선택x

- B는 조건에 맞음으로 선택 C > B

- D는 B와 시작 시간이 같음으로 선택x

- E는 조건에 맞음으로 선택 C > B > E

 

 

2) 거스름돈(동전의 개수가 가장 적게)

잔돈 : 890

동전 종류 : 10 50 100 500일때

-> 큰동전부터 계산

 

만약 여기에 400원짜리 동전이 추가된다면 

 

 

최적해를 보장하지 못함-> 언제 사용해야 할까?

 

1. 탐욕적 선택 특성

 현재 선택이 다음 선택에 영향을 주지 않음

 

2. 최적 부분 구조

 전체 문제의 최적해는 부분 문제의 최적해로 이루어짐