최적해 구하기 - 탐욕법

• 완전탐색, 동적계획법 - 전체를 고려해서 최적해 구하기
• 탐욕법 - 그때 그때 최선을 찾는 경우
  1. 동적계획법보다 수행시간이 빠르다.
  2. 최적해를 구하기 힘들때, 적당히 괜찮은 답을 찾는 것.(임의의 답보다는 좋은 답을 구하는 용도)

근사해 구하는 문제

1. 탐욕법
2. 조합탐색
3. 메타휴리스틱

---

알고리즘의 정당성을 증명하는 과정이 꼭 필요

예제 회의실 예약
회의실을 예약하는데, 최대로 예약할 수 있는 회의의 개수 구하기

알고리즘 정당성 증명

1. 무식하게 풀 수 있을까? - 시간대로 나누었을 때 n이 30만 되어도 시간안에 문제 풀긴힘들다(2^30)

2. 탐욕적 알고리즘의 구상

   1. 길이가 짧은 회의 선택(예외 발생)

   2. 빨리 끝나는 회의 선택

      - 목록에 남은 회의중 가장 일찍 끝나는 회의를 선택
      - 일찍끝나는 회의와 겹치는 회의를 다지운다.
      - 남은 회의 들로 같은 방법을 반복

정당성 증명은 굉장히 중요

탐욕적 알고리즘이 항상 최적해를 찾아낼 수 있다는 것을 2가지의 속성을 증명해서 보인다.

1. 답의 모든 부분을 고려하지않고 탐욕적 방법만 선택해도 최적해를 구할 수 있다.(탐욕적 선택 속성)

" 빨리 끝나는 회의 선택 " (증명 : 다음주에 계속)