코딩테스트 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이 된다는 것을 증명함
• 이 과정에서 수학적 귀납법을 명시적 혹은 내재적으로 사용함