그리디 알고리즘

그리디 알고리즘

각 단계에서 최적이라고 생각하는 것을 하기

회의실 배정 문제

1개의 회의실을 다수의 팀이 시간대 별로 사용하고자 할 때, 최대한 많은 회의를 하기

예시 상황:
- 회의 개수 = 8
- 회의 시간 목록 = 
	1번팀: 1시 ~ 4시
	2번팀: 3시 ~ 5시
	3번팀: 0시 ~ 6시
	4번팀: 5시 ~ 7시
	5번팀: 3시 ~ 8시
	6번팀: 5시 ~ 9시
	7번팀: 6시 ~ 10시
	8번팀: 8시 ~ 11시

그리디 방식으로 접근

1. 회의 종료시간이 가장 빠른 순서대로 정렬한다

2. 이전 회의 종료 시각 이후 시작하는 회의 중 가장 일찍 끝나는 회의를 선택한다

그리디 방식의 장단점

• 장점

  • 구현이 단순, 실행속도가 빠름

  • 직관적

• 단점

  • 최적의 해를 보장하진 않는다

    • 각 단계의 최적의 선택이 전체적인 최적의 해결책이 아닐 수 있다

  • 적용이 한정적이다

그리디 알고리즘의 필수 조건

1. 탐욕 선택 속성

   1. 각 단계에서 선택한 방법이 이후의 결정과
      상관없이 최종 답의 최적성을 유지해야 한다

   💡

   회의실 배정에서 가장 빨리 끝나는 팀을 골랐을 때
   → 이 선택이 최대 회의 수라는 최종 목표에 최선이다

2. 최적 부분 구조

   1. 전체 문제의 최적해가 문제를 나눈 각 부분 문제의
      최적해를 결합하여 얻을 수 있어야 한다

   💡

   거스름돈 금액을 어떤 동전을 써야 최소의 동전 갯수를 보장하는가?

   이런 문제에선 최대한 큰 동전을 사용한다 가 최적해를 만든다

이 두 가지가 만족되어야 그리디 알고리즘을 사용할 수 있음

증명하기

1. 수학적 증명

   1. 귀류법, 가정 등을 통해 분석

      귀류법 → 명제가 참임을 증명하기 위해 거짓이라고 가정한 후 모순을 이끌기

2. 작은 예시로 검증

   1. 입력값을 다양하게 하여 직접 테스트

3. 반례 찾기

   1. 그리디 알고리즘이 실패하는 경우를 찾기

4. 기존 문제와 비교