14주차 - 그리디 알고리즘

그리디 알고리즘

• 현재 시점의 이익만 선택하는 알고리즘
• 대부분 최적해와는 거리가 멀음
  • 단, 드물게 최적해가 보장 될 때가 있음
• 최소 신장 트리가 그리디 알고리즘에 포함됨

최적해가 보장되지 않는 사례

1. 이진트리의 최적합 경로 탐색
2. 보따리 문제
3. 동전 바꾸기 문제

최적해가 보장되는 사례

1. 프림 알고리즘 및 크루스칼 알고리즘
2. 회의실 배정 문제
   • 회의실이 1개이고, 여러 곳에서 사용 요청을 했을때 해결법은?
     • 회의 시작/종료 시간을 명시해 신청한 건 중 종료 시간이 가장 이른 회의 순으로 배정