그리디 알고리즘

동적 프로그래밍에서 지나치게 많이 일을 해서 좀 줄여보자는 취지로 만들어졌음.

미래를 생각하는게 아니라, 현재상황에서 최선을 택하는 기법이다.

활동선택문제와 백팩문제에서 쓰인다.

1.활동선택문제

이문제는 한 강의실에서 여러 수업을 진행한다고 했을 때, 가장 많이 할 수 있는 경우를 선택하는 문제이다.

Si는 시작시간, Fi는 종료시간이다.

위 표를 보면 a1, a4와 a1,a2는 동시대에 진행되기 때문에 선택을 할 수 없다. 하지만 a1,a3은 선택이 가능하다.

즉 결과적으로 

A1, a3, a6,a8 || A1, a3, a7, a9 이 후보지이다.

G18을 a1이후, a8 이전으로 보면 선택 될수 있는 후보는

{a3,a5,a6,a7} 이다.

이중에서도 겹치지 않게 골라보면

{a3,a6} {a3,a7} {a5,a7}이다

이러한 집합을 B18이라고 할때

만약 B18에서 a6을 선택했다고 가정

그러면 이 문제는 2가지로 쪼개진다.

즉 g16, g18에서 최적의 해인 b16, b68를 구해야한다

최종적으로 b16, b68의 개수와 a6의 개수를 구하면 최적활동의 갯수를 알 수 있다.

식으로 표현하자면 C[i,j] = max(C[i,k] +C[k,j]+1) 이다.

이런식으로 동적프로그래밍이 가능하지만 모든 C를 구해야 함으로 

항상 최선의 방법으로 해결 할 수 있는 그리디 알고리즘을 선택 해야 할 때가 있다.

맨처음 a1를 골랐고 제일 빨리 끝나고 할 수 있는 a3을 선택, 그후 a6, a8을 선택하면 그게 최적의 결과이다