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

16.3 비트마스크의 응용 예제

지수 시간 동적 계획법

배열 대신 정수로 집합을 표현하면 이것을 곧장 배열의 인덱스로 쓸 수 있따는 점을 이용함. 따라서 메모이제이션의 구현 또한 훨씬 간단해짐 

 

에라토스테네스의 체

k번 원소가 참인지 알기 위해서는 k/8번째 원소의 k%8번째 비트가 켜져 있는지를 확인하면 됨. 실제로 비트마스크를 사용하는 부분은 isPrime(), setComposite() 임. 

inline bool isPrime(int k) {
	return sieve[k >> 3] & (1 << (k & 7));
}

inline void setComposite(int k) {
	sieve[k >> 3] &= ~(1 << (k & 7));
}

void eratosthenes() {
	memset(sieve, 255, sizeof(sieve));
	setComposite(0);
	setComposite(1);
	int sqrtn = int(sqrt(n));
	for (int i = 2; i <= sqrtn; ++i) {
		if (isPrime(i))
			for (int j = i * i; j <= n; j += i)
				setComposite(j);
	}
}

 

15퍼즐 상태 표현하기

표현해야 하는 값의 범위가 작을 때는 2비트씩, 3비트씩 묶어서 배열로 쓸 수도 있음. 16개의 숫자가 있기 때문에 비트마스크를 사용하면 이 배열 전체를 64비트 정수 하나로 표현할 수 있음. 64비트 아키텍처의 겨우 상태 전체를 워드 하나에 넣을 수 있다는 것은 큰 장점임. 

 

O(1) 우선순위 큐

우선순위가 특정 범위로 제한되어 있을 경우 비트마스크를 이용하면 모든 작업을 O(1)에 할 수 있는 우선순위 큐를 만들 수 있습니다. 큐에 넣는 원소의 우선순위가 1이상 140이하의 정수라고 합니다. 각 우선순위를 갖는 원소들을 담는 140개의 큐를 만들고, 각 큐에 워노가 있는지 여부를 비트마스크로 표현함. 140개의 불린 값을 64비트 정수 세 개에 저장하면 첫 번째 비트를 찾는 연산을 이용해 모든 큐를 뒤질 필요 없이 가장 우선순위가 높은 원소가 어디에 있는지를 쉽게 찾을 수 있음. 

 

예제 : 극대 안정 집합

물질이 하나만 있는 집합은 항상 안정적임. 안정된 집합은 여러개가 있을 수 있음. 그중 물질을 하나라도 추가하면 폭발이 일어나는 집합을 극대 안정 집합. 각 화학 물질의 정보가 주어질 때 극대 안정 집합의 수를 세는 코드를 작성해봅니다. 이것을 푸는 좋은 방법은 한 개의 물질을 갖는 모든 집합으로부터 시작해서 그래프의 탐색 알고리즘을 사용해 모든 안정 집합을 만들어 나가는 것이 필요함. 이 탐색 과정에서 더이상 물질을 추가할 수 없는 집합의 수를 반환하면 됨. 하지만 이 문제에서는 입력의 크기가 그렇게 크지 않기 때문에 좀더 효율적이라도 짧은 코드를 작성하고 싶음. 비트마스크를 사용하여 모든 쌍의 물질에 대해 이둘을 같이 뒀을 때 폭발하지 않는지 확인하는 것이 필요함. 

const int MAXN = 10;
int n;
int explodes[MAXN];
bool isStable(int set) {
	for (int i = 0; i < n; i++) {
		if ((set & (1 << i)) && (set & explodes[i]))
			return false;
		
	}
	return true;
}

int countStableSet() {
	int ret = 0;
	for (int set = 1; set < (1 << n); ++set) {
		if (!isStable(set)) continue;
		bool canExtend = false;
		for(int add =0; add < n; ++add)
			if ((set & (1 << add)) == 0 && (explodes[add] & set) == 0) {
				canExtend = true;
				break;
			}
		if (!canExtend)
			++ret;
	}
	return ret;
}

이렇게 하고 나면 2^N개의 모든 집합을 전부 만들어 보면서 각 집합이 안정적인지, 안정적이라면 다른 물질을 추가할 수 있는지 확인하는 알고리즘 코드를 간단하게 작성할 수 있음. 어떤 안정 집합에 다른 원소 add를 넣을 수 있는지를 isStable()를 다시 호출하는 대신 explodes[add] & set이 0인지만 확인하는 것을 눈여겨보세요.