[Algorithm/C] 탐욕 알고리즘(Greedy Algorithm) - 1931번: 회의실 배정

 

Greedy Algorithm 

---

여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최선이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종 해답에 도달하는 알고리즘이다.

 

참고자료

탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전

 

최적해를 구하기 위한 조건

1. 탐욕스런 선택 조건(greedy choice property): 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것

2. 최적 부분 구조 조건(optimal substructure): 최적해가 부분문제에 대해서도 최적해라는 것

-> 성립하지 않으면 최적해를 구하지 못한다.

 

 

문제 해결

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.

2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.

3. 해답 검사(Solution Check): 최종적으로 문제가 해결됐는지 검사한다.

 

 

Activity selection problem(활동 선택 문제)

참고 자료

Activity selection problem - Wikipedia

해당 알고리즘은 사람 또는 기계가 한 번에 한 가지의 활동만 수행할 수 있다고 가정할 때,

수행할 수 있는 최대 활동 수를 도출하는 것이다.

 

그리디 알고리즘을 활용한 것이다.

이 알고리즘은 '최대 활동 수'를 도출해내는 과정이 즉 최적해를 구하는 것이 된다.

 

 

문제 해결

1. 완료 시간을 기준으로 오름차순으로 정렬한다.

2. 정렬된 활동 중, 첫 번째 활동을 선택한다. (선택 절차)

3. 단계 2에서 선정된 활동을 제외한 나머지 활동 중에서

    시작 시간이 단계 2의 활동의 종료 시간보다 크거나 같으면(적절성 검사) 이 활동을 선택한다. (선택 절차)

 

 

이 개념들을 토대로 문제를 풀어 보자.

 

 

 

---

1931번: 회의실 배정

 

문제

---

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

입력

---

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

 

출력

---

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

구현

---

#include <stdio.h>
#include <stdlib.h>
#define _CRT_SECURE_NO_WARNINGS

typedef struct
{
	int x;
	int y;
} greedy;

/*
		qsort()의 인자인 포인터 함수 compare의 원형
		: int (*compare)(const void *,const void *)
		- void형 포인터 2개를 받아서 int형 리턴
		- 첫 번째 인자가 우선 순위가 높다면 음수, 두 번째 인자가 우선 순위가 높다면 양수, 같으면 0
		- 이해하기 힘들다면 첫 번째 인자의 우선순위에 두 번째 인자 우선순위를 뺀다고 생각하면 된다.
		  1(순위) - 3(순위) = -2 이기 때문.
*/

int compare(const void* a, const void* b)
{
	greedy A = *(greedy*)a;
	greedy B = *(greedy*)b;

	// 종료 시간이 A가 B보다 늦으면 양수 반환
	if (A.y > B.y)
		return 1;
	// 종료 시간이 같을 경우
	else if (A.y == B.y)
	{
		if (A.x > B.x)	// 시작 시간이 A가 더 느릴 때
			return 1;
		else   // B가 더 느릴 때
			return -1;
	}
	// B 종료가 더 느리면 음수 반환 
	else
		return -1;
}

int main()
{
	greedy arr[100010];
	int i, j, n, count;
	scanf("%d", &n);
	i = 0;
	while (i < n)
	{
		scanf("%d %d", &arr[i].x, &arr[i].y);
		i++;
	}

	/*
		qsort 함수 원형
		void qsort(void *base, size_t num, size_t size, int (*compare)(const void *,const void *));
	*/
	qsort(arr, n, sizeof(greedy), compare);	

	i = 1;
	j = 0;
	count = 1;
	while (i < n)
	{
		//시작 시간이 이전 활동의 종료 시간보다 같거나 느리다면 최적해로 선정
		if (arr[j].y <= arr[i].x) 
		{
			j = i;
			count++; 
		}
		i++;
	}
	printf("%d", count);
}

 

참고 자료

qsort