그리디

그리디

created: 2026.1.12

---

그리디

• 욕심쟁이 알고리즘
• 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘
• 관찰을 통해 탐색 범위를 줄이는 알고리즘

풀이

1. 관찰을 통해 탐색 범위를 줄이는 방법 고안
2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명
3. 구현

문제 풀이

• BOJ 11047번: 동전 0
  • 보조 정리 1: 10/100원 동전은 4개 이하, 50원 동선은 1개 이하
  • 증명: 10/100원 동전 5개 이상 -> 50/500원, 50원 동전 2개 이상 -> 100원 동전
  • 명제: 500원 동전을 최대한 많이 써야함
  • 증명: 10/50/100원으로는 최대 490원만 감당 가능
  • 큰 금액 동전부터 소진 -> 동전이 배수여서 가능한 방법
• BOJ 1931번: 회의실배정
  • O(2^N): 모든 가능한 배정 방법 확인
  • O(N^2): dp
    • 끝나는 시간-시작 시간이 빠른 순으로 정렬
    • D[i] = i번째 회의를 마지막으로 진행했을 때 최대 회의의 수
    • D[i] = max(D[j]) + 1 (j번째 회의의 끝나는 시간이 i번째 회의의 시작 시간 이하인 모든 j)
  • 명제: 현재 시간이 t라고 할 때 시작 시간이 t 이상인 모든 회의 중 가장 먼저 끝나는 회의 선택
  • 지금은 손해를 보더라도 나중에는 이득이 경우가 있을 수 있는지 고민 -> 반례 찾기