그리디 알고리즘

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올 릴 수 있는 능력 요구
• 그리디 해법은 그 정당성 분석이 중요
  • 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토
• 거스름돈 문제
  • 거스름울 줄 수 있는 화폐의 단위가 500원 ,100원 ,50원이 있을 때 N원을 거슬러 주어야할 동전의 최소갯수
  • 가장 큰 화폐 단위부터 돈을 거슬러주면 됨
    • 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문

회의실 배정(1931) - 백준

• 모든 가능한 배정 방법을 확인 O(2^N) => 시간초과
• DP로 풀이 => O(N^2)
  • 회의를 끝나느 시간이 빠른 순으로, 끝나는 시간이 같다면 시작 시간이 빠른 순으로 정렬
  • dp[i] = i 번째 회의를 마지막으로 진행했을 때 최대 회의 수
  • dp[i] = max(d[j]) + 1 => j번째 회의의 끝나는 시간이 i번째 회의의 시작 시간 이하인 모든 j
• 그리디 : 가능한 회의 중에서 가장 먼저 끝나는 회의를 택하기
  • 맞는지 검증하기 위해 귀류법 생각
  • 명제 : 현재 시간이 t라고 할 때, 시간이 t 이상인 모든 회의 중에서 가장 먼저 끝나는 회의를 택하는 것이 최적해이다.
    • 귀류법으로 증명 : 회의 A 대신 회의 B를 택했을 때 더 많은 회의를 배정할 수 있다고 가정
    • 이때, 회의 B 대신 A를 사용한다 하더라도 스케줄에는 아무런 문제가 없음. 왜냐하면 회의 A는 남아있는 회의 중에서 가장 먼저 끝나는 회의이기 때문
    • 따라서 회의 B 대신 회의 A를 사용해도 아무런 모순이 발생하지 않음 => 가정은 거짓
• 이 문제를 통해, 내가 떠올린 그리디 알고리즘이 올바른지 확인할 때, 지금 당장 손해를 보더라도 나중에 가서 이득인 경우가 있을 수는 없는지 고민해보면 정당성을 확인 가능!

```