[알고리즘] Greedy algorithms

(2021.10.27)

알고리즘 수업들으면서 정리하기 14탄

greedy algorithms 개념 (생각보다 내용이 없다)

 

 

---

 

Greedy algorithms : 탐욕 알고리즘

 

greedy algorithm은 dynamic algorithms과 마찬가지로 optimization에 쓰인다.

greedy algorithm은 the activity selection problem에도 쓰인다.

 

 

 

dynamic algorithms  vs  greedy algorithms

- dynamic algorithms은 problem을 sub-problem으로 나누어서 sub-problem을 overlapping 하며 larger sub-problem으로 build up 해간다.

- greedy algorithms은 problem을 sub-problem으로 나누지 않는다. 그때 그때의 상황에서의 최선의 선택을 한다.  그 상황에서의 choice는 전이나 후의 choice에 영향을 주지 않는다. set of camdidates로 구성되는데, empty set에 solution을 하나씩 넣는다.

 

greedy algorithms은 100%의 최적솔류션을 도출하지는 않는다.

greedy algorithms으로 최적의 해를 도출하는 문제들이 있다.

 

 

greedy algorithms의 과정

• Selection procedure: solution set에 넣을 next item 선택한다. (the locally optimal consideration을 만족함) 
• Feasibility Check: new set가 feasible 한지 판단한다.
• Solution Check: new set가 problem의 solution이 되는지 판단한다.

(사실 feasibiltiy check와 solution check가 무슨 차이인지 이해하지 못했다. 수업을 더 들어보고,,,)

 

 

출처: 교수님 강의노트

 

 

 

 

 

 

 

 

 

greedy algorithms에 대한 예로 activity selection에 대한 문제를 다룬다.

이번시간엔 dp로 접근했고, 다음시간에 greedy로 접근하는걸 배운다고 한다.

 

greedy algorithms으로 다룰 문제들

activity selection