[알고리즘] 그리디 알고리즘이란?

그리디 알고리즘이란 무엇인가? (What)

현재 상태에서 최선의 선택을 반복하는 알고리즘. 

 

아이디어가 간단하다. 전체는 모르겠고 지금 눈 앞의 선택들 중 가장 좋은 선택을 하겠다는 것.

 

특징 

-> 구현이 매우 쉬움 (How는 쉬움)

-> dp나 분할 정복과 같이 목적이 한정되지 않고 범용적으로 쓰일 수 있는 알고리즘.

---

언제 쓰는가? (Why)

항상 최적해를 보장하지 않는다. 때문에 언제 쓸 수 있는지를 파악하는 것이 중요하다. 

 

조건 2가지

• optional substructure 최적 부분 구조 가질 때
• greedy choice property 그리디 우선 선택 - 한번의 선택이 다음 선택과 무관할 때(영향을 주지 않을 때)
•  

최적 부분 구조란 무엇인가? 

부분 문제의 최적해가 전체 문제의 최적해를 구성하는 구조. (특징)

최적 부분 구조임을 판별하려면

1. 문제를 쪼갤 수 있는가? - 문제 자체를 쪼갤 수 없는 경우가 있을 수 있음. 

2. 쪼갰을 때 해를 구한 것이 전체 문제의 해를 구하는 데에 유효한가? - 문제를 쪼갰을 때의 답이 전체 문제의 답을 구하는데 기여하지 못할 수 있음. 

 

최적 부분 구조 특징을 필요로 하는 알고리즘

• 그리디 
  • 최적 부분 구조 & 그리디 우선 선택 (Greedy Choice Property) 
• dp 
  • 최적 부분 구조 & 부분 반복 문제 (Overlapping Subproblem - 반복되어 답을 재사용할 수 있는지)
• 분할 정복
  • 최적 부분 구조

 

 

그리디 문제를 보고 해야할 질문!

1. 문제를 쪼갤 수 있는가?

2. 쪼갰을 때 해를 구한 것이 전체 문제의 해를 구하는 데에 유효한가?

3. 이 선택이 다음 선택에 영향을 주지 않는가?

-> 이 선택으로 인해서 향후 다른 선택의 가능성이 배제되지 않는가?

-> 이 선택을 했을 때의 조합 말고 다른 조합이 존재하지 않는가?  

-> 개별로서 의미를 갖는 게 맞는지, 조합으로서 의미를 가지는 것이 아닌지? 

4. 어떤 것이 최선의 선택인가?

---

 

어떻게 구현하는가? (How)

현재 상태에서 가능한 경우의 수 중 가장 좋은 것 고르기 (기준) -> 목표 상태에 가장 적합한 선택. 

기준을 고르는 것이 까다로울 수는 있음. 

 

강의실 배정 문제의 경우 기준을 시작하는 시간이나 길이로 잡으면 안됨. 끝나는 시간으로 잡아야함.