알고리즘) 그리디 알고리즘

그리디 알고리즘은 국내에서는 일반적으로 탐욕법이라고 알려져있다. 즉, 단순무식하게 탐욕적으로 문제를 푸는 방법이다.

 

그리디 알고리즘의 핵심은 '현재 상황에서 당장 최선의 방법을 고르는것'을 의미한다. 나중은 고려하지 않는다는 의미이다.

 

가장 큰 장점으로는 다른 자료구조와 비교해서 사전에 사용하는 방법을 알지 못해도 사용할 수 있다는 것이다. 

 

이것에 관한 문제에서 주로 가장 큰 순서, 혹은 작은 순서 등 정렬과 관련해서 문제가 나오는경우가 많다.

 

물론 모든 경우에 사용될 수 있는 알고리즘이 아니다. 예를들어 1분뒤에 500원, 2분뒤에 1000원을 받는 선택지 중에서 그리디 알고리즘으로 선택을 하면 1분뒤 500원을 받는 선택지를 선택하게 된다. 결과적으로는 2분뒤 1000원을 받는 선택이 더 이득이지만 선택을 하는 시점에서의 이득만을 생각하기 때문이다.

 

서치를 하다보니 많이 보이는 그리디 알고리즘의 대표적인 예시가 있었다. 바로  Activity-Selection Problem이다.

 

활동선택문제(Activity-Selection Problem)는 다른말로 교실 할당이라고도 한다. 한 강의실에서 여러 수업을 할때 한번에 가장 많은 수업을 할 수 있는 경우를 고르는 문제이다.

i	1	2	3	4	5	6	7	8	9
si	1	2	4	1	5	8	9	11	13
fi	3	5	7	8	9	10	11	14	16

위 테이블에서 i는 해당하는 과목이고 si는 i의 시작시간이고, fi는 i의 종료시간이다. 여기서 i가 1이면 해당 클래스를 a1 이라고 칭한다.

a1과 a2는 시간이 겹친다. 따라서 이 두과목은 함께 수업을 진핼 할 수 없고 a1과 a3는 가능하다.

 

이와같은 과정을 오름차순으로 정렬하여 표시하면 아래와 같다.

 

 

따라서 한 교실에 배정할 수 있는 최대 수업의 조합은 a1 + a3 + a6 + a8의 조합이다. 물론  a1 + a3 + a7 + a9의 경우 또한 정답이라고 볼 수 있다.

 

 

 

예제를 몇개 가져와보았다.

 

 

 

백준 1931 회의실 배정, 백준 11047 동전0

www.acmicpc.net/problem/1931

1931번: 회의실배정

www.acmicpc.net/problem/11047

11047번: 동전 0