코딩테스트 1주차 - 그리디알고리즘
그리디 알고리즘
그리디 알고리즘은 결정의 순간에 모든 경우를 보지 않고 근시안적인 최선의 선택을 하는 알고리즘이다.
즉, 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지 고려하지 않고 어떤 기준에 의해 그 시점에 최선인 것 같은 것을 선택한다. 따라서 전체적으로 봤을 때 최선이 아닐 수도 있다.
그리디 알고리즘 정당성 증명
Greed Choice 를 해도 그것이 실제로 최선의 선택이라는 것을 증명해야 하는데 이 부분이 어렵다.
1. 탐욕적 선택 속성
2. 최적 부분 구조
이 두가지 속성을 증명함으로써 그리디 알고리즘이 항상 최적해를 찾아낼 수 있다는 것을 보인다.
그리디 알고리즘을 설계하는 과정
Scheduling Classes 문제
수요일에 신청할 수 있는 과목이 n개가 있다.
각 과목의 시작, 끝 시간이 입력으로 주어질 때 어떤 과목을 선택하면 수요일에 최대한 많은 과목을 신청할 수 있을까?
가능한 Greedy Choice 는 뭐가 있을까?
1. 시작시각(S[i])이 가장 이른 class를 먼저 선택
2. 길이(F[i]-S[i])가 짧은 class를 먼저 선택
3. 서로 겹치는 class 개수가 가장 적은 것을 먼저 선택
가장 적은 것 먼저 - 3개 최대 - 4개
4. 종료시각(F[i])이 가장 이른 class를 먼저 선택
-> 이 방법을 사용하면 가장 많은 과목을 선택하는 것이 가능하다.
따라서
Greedy Choice의 기준은
- 종료시각(F[i])이 가장 이른 class를 먼저 선택이다.
그리디 알고리즘 증명
1. 탐욕적 선택 속성이란
- 탐욕적으로만 선택하더라도 최적해를 구할 수 있다는 것이다.
Scheduling Classes 문제의 경우, 탐욕적 선택 속성이 성립한다는 것은
가장 먼저 종료되는 과목을 포함하는 최적해가 반드시 존재한다는 의미이다.
Proof.
- f를 가정 먼저 종료하는 과목이라고 하자.
- X는 최적해(maximal conflict-free schedule)이고 f를 포함하지 않는다고 가정하자.
- g를 X에 포함된 것 중 가장 먼저 끝나는 과목이라고 하자.
- 그러면 f가 g보다 먼저 끝나기 때문에 X에서 g를 빼고 f를 넣어도 여전히 conflict-free이다.
-> (X - { g }) U { f }도 역시 최적해(maximal conflict-free schedule)이다. 이 증명은 가장 일찍 끝나는 과목을 선택해서 최적해를 얻는 것이 불가능한 경우는 없다는 것을 나타낸다.
2. 최적 부분 구조란
- 항상 최적의 선택만을 내려서 전체 문제의 최적해를 얻을 수 있다는 것이다. 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있음을 보여주면 된다.
Proof.
- f를 가장 먼저 종료하는 과목이라하자.
- A를 f와 겹치지 않는(이후에 시작하는) 과목들의 집합이라하자.
- 위(탐욕적 선택 속성)에서 f를 포함한 최적해가 존재한다고 했으니까, f를 선택한 schedule 중에 최선인 것이 역시 최적해이다. 즉, f가 포함된 것중 최선인 schedule을 X라고 하면 X는 최적해이다.
- X는 f와 A에서의 최적해를 포함한다.
- GreedySchedule은 f를 선택하고 나머지에서 최적해를 찾을 수 있다.
정확성 증명의 패턴
- Greedy soultion과 optimal solution이 다르다고 가정
- 두 solution에서 처음으로 다른 부분(다른 결정을 한 부분)에 대해서
- 그 부분을 Greedy solution의 greedy choice로 대체해도 여전히 optimal solution이 된다는 것을 증명함
- 이 과정에서 수학적 귀납법을 명시적 혹은 내재적으로 사용함