13-2 그리디 알고리즘

1. 그리디 알고리즘

① 그리디 알고리즘

 - 현재 시점에서 가장 이득이 되어 보이는 해를 선택하는 행위를 반복함.

 - 온전한 해가 만들어질 때까지 눈 앞에 가장 좋아 보이는 선택을 반복함.

 -  뛰어난 결과를 도출하지 못하지만 드물게 최적해를 보장하는 경우도 있음.

 - 동적 계획법과 마찬가지로 최적화 문제의 답을 얻기 위해 사용

 

② 그리디 알고리즘 잘 작동하는 문제

 

 

③ 동작 과정

 

1. 배낭 채우기 문제

① 문제

 - 한 사람이 가지고 가는 배낭에 담을 수 있는 무게의 최대값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제. 

 -  두가지 경우로 나누어짐

② 동적계획법과 그리디 알고리즘

③ 0-1 배낭 채우기 문제 -> 탐욕적 방법 사용불

 

3. 그리디 알고리즘 적용 예시

① 회의실 배정 문제

② 메트로이드

 - 그리디 알고리즘으로 최적해가 보장되는 공간 구조

 - 어떤 문제의 공간이 매트로이드 구조 가지면 그리디 알고리즘으로 최적해가 보장