알고리즘 문제 해결 전략2 16장 비트마스크(4)

16.4문제:졸업 학기

졸업 필수 학점을 채우려면 전공 과목 N개 중 K개 이상을 수강해야 함. 각 과목의 정보와 앞으로 M학기 동안 개설될 과목의 목록이 주어질 때, 태우가 최소 몇 학기를 다녀야 졸업할 수 있느지 계산하는 프로그램을 작성하시오. 한 과목도 수강하지 않는 학기는 휴학한 것으로 하며, 다닌 학기 수에 포함되지 않음. 

 

예제 입출력 설명 : 첫 학기에 0번 과목, 번 과목을 듣고, 두 번째 학기에 1번 과목을 들은 뒤, 네 번째 학기에 2번 과목을 들으면 됩니다. 세 번째 학기에는 2번 과목이 개설되지 않으므로 다니지 않아도 됨.

두 번째 테스트 케이스에서는 2번과 3번 과목이 서로 선수과목으로 지정되어 있기 때문에 두 과목은 들을 수 없습니다. 0번 과목을 듣기 위해 1번 과목을 미리 들어야 하므로, 첫 번째 학기에는 아무 것도 들을 수 없음. 두 번째 학기에 1번 가목을 듣더라도 2학기 내에는 졸업할 수 없음. 

 

16.5 풀이:졸업 학기

동적 계획법 알고리즘을 만들기 위해서는 우선 완전 탐색 알고리즘을 설계하고 이것을 메모이제이션으로 최적화해야 함. 그리고 완전 탐색으로 문제를 풀기 위해서는 문제를 여러 조각으로 나눈 다음 한 조각을 해결하고 나머지를 재귀 호출을 통해 해결해야 함. gratuate(semester, taken)=현재 학기가 semester이고 지금까지 들은 과목의 집합이 taken일때, 앞으로 다녀야 하는 최소 학기의 수는?

graduate()에서 choose()를 호출하고, choose()에서 스스로를 호출하다가 L개의 과목을 선택하고 나면 다시 graduate를 호출하는 등 코드의 구조가 너무 복잡해짐. 이렇게 재귀 호출을 이용해 모든 조합을 만들기가 번거로울 때 비트마스크를 유용하게 쓸 수 있음. 

 

구현하기

- 어떤 과목의 선수 과목을 이미 전부 들었는지를 확인하는 작업 : taken과 prerequisite[i]의 교집합이 prerequisite[i]와 같은지만 확인

- canTake에서 아직 선수 과목을 다 듣지 않아 들을 수 없는 과목들을 미리 걸러냄. 이 집합의 부분 집합을 순회하면 됨.

- 이미 들은 과목의 수나 이번 학기에 들을 과목의 수를 세기 위해 비트의 수를 세는 함수를 사용함.

const int INF = 987654321;
int n, k, m, l;
int prerequisite[MAXN];
int classes[10];
int cache[10][1 << MAXN];
int bitCount(int n);
int graduate(int semester, int taken) {
	if (bitCount(taken) >= k) return 0;
	if (semester == m) return INF;
	int& ret = cache[semester][taken];
	if (ret != -1) return ret;
	ret = INF;
	int canTake = (classes[semester] & ~taken);
	for (int i = 0; i < n; i++)
		if ((canTake & (1 << i) && (taken & prerequisite[i])))
			canTake &= ~(1 << i);
	for (int take = canTake; take > 0; take = ((take - 1) & canTake)) {
		if (bitCount(take) > l) continue;
		ret = min(ret, graduate(semester + 1, taken | take) + 1);
	}
	ret = min(ret, graduate(semseter + 1, taken));
	return ret;
}

canTake의 모든 부분 집합을 순회하려면 최대 2^C의 시간이 걸림. 전체 M*2^N개의 부분 문제가 있으므로 프로그램의 전체 시간 복잡도는 O(M*2^(N+C))이 됨. 

비트 연산만을 전문적으로 다루는 책으로 해커의 즐거움이 있음.