[알고리즘 시리즈] 탐욕 알고리즘 : Greedy Algorithm

---

탐욕 알고리즘 : Greedy Algorithm

목차

1. 그리디 알고리즘의 목적

2. 그리디 알고리즘의 적용 조건

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

---

1. 그리디 알고리즘의 목적

현재의 선택이 다음 단계에 끼치는 영향을 고려하지 않고 전체 문제의 최적의 해를 구한다.

 

2. 그리디 알고리즘의 적용 조건

1) Greedy-choice property

현재 최선의 선택이 미래에도 최선의 선택인가

이 속성을 만족하지 않는 그리디 알고리즘은 huristic한 해결책을 제시한다.

 

2) Optimal Substructure

부분 문제의 해결 방법으로 전체 문제도 해결할 수 있는가

 

3. 그리디를 적용한 대표적인 문제들

1) Activity Selection Problem

시작 시간과 끝 시간이 있는 활동이 여러개가 있을 때, 주어진 구간에서 겹치지 않는 활동을 가장 많이 선택하는 문제이다.

끝 시간을 기준으로 오름차순 정렬한 후, 활동이 겹치지 않도록 선택하면 된다.

 

2) Fraction Knapsack Problem

0-1 Knapsack 문제와는 다르게 부분적으로 물건을 배낭에 담을 수 있는 문제이다.

무게 당 가치가 높은 순으로 물건을 담으면 된다. 

---