종만북 16장 비트마스크
이 포스팅은 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략>, 구종만, 인사이트(2012)을 읽고 개인 학습용으로 정리한 글입니다.
➖ 21-06-30
도입
비트 마스크를 사용하는 코드의 장점
-
더 빠른 수행 시간
-> 보통 비트마스크 연산 O(1)에 구현됨 -
더 간결한 코드
-> 다양한 집합 연산 반복문 없이 구현 가능 -
더 작은 메모리 사용량
-> 더 많은 데이터 미리 계산하여 저장
-> 프로그램 빨라지고 캐시 효율이 좋아진다
유의할 점
-
비트마스크와 실수 연산자 간 우선순위
-> 가능한 괄호를 자세하게 추가하는 습관 필요 -
64비트 정수 비트마스크 할 때 오버플로우
-> C++에서 1은 부호있는 32비트 상수로 취급
-> 접미사 ull(unsigned long long)를 붙여주어야 -
부호 있는 정수형 -> 최상위 비트로 자잘한 버그 발생 가능
-> 부호 없는 정수형 사용 권장 -
C++에서 N비트 정수를 N비트 이상 왼쪽으로 쉬프트하는 경우
-> 환경에 따라 다른 결과를 낼 수 있음
비트마스크를 이용한 집합의 구현
집합의 표현
-
0부터 번호가 매겨진 n개의 원소를 가질 수 있는 집합
-> 비트마스크를 이용하여 표현할 수 있다 -
상수 0은 공집합을 나타낸다
-
n 개의 원소를 모두 포함하는 꽉 찬 집합
int fullPizza = (1 << n) - 1;집합의 원소 p (0<=p<n)
- 원소 추가하기
toppings = toppings | (1 << p);
toppings |= (1 << p); - 원소 포함 여부 확인하기
-> 연산 결과 0 또는 (1<<p)라는 점 유의
if(toppings & (1 << p)) cout<< "pepperoni is in"<<endl;
//아래 코드는 제대로 동작하지 않는다
//if(toppings & (1 << p) == 1) cout<< "pepperoni is in"<<endl;- 원소 삭제하기
toppings = toppings & ~(1<<p);
toppings &= ~(1<<p);- 원소 토글(toggle)하기
-> 해당 비트가 1이면 0으로, 0이면 1로
-> XOR연산(^) 이용
toppings = toppings ^ (1<<p);
toppings ^= (1<<p);두 집합의 연산
int added = (a | b);
int intersection = (a & b);
int removed = (a & ~b);
int toggled = (a ^ b);집합의 크기
-
비트마스크를 이용할 때 집합에 포함된 원소의 수를 구하는 쉬운 방법은 딱히 없다
-
재귀 호출로 작성
int bitCount(int x){
if(x == 0) return 0;
return (x % 2) + bitCount(x/2);
}-
여러 프로그래밍 환경에서 관련 내장 명령어 제공
-> 다양한 최적화를 통해 구현됨 -> 매우 빠르다 -
Visual C++에서 32비트 부호 없는 정수 toppings에 켜진 비트의 수
= __popcnt(toppings)
집합의 최소 원소
-
집합에 포함된 가장 작은 원소 찾기
-> 이 정수의 이진수 표현에서 끝에 붙어있는 0의 개수
-> 이 정수의 이진수 표현에서 켜져있는 최하위 비트의 번호 -
Visual C++에서 32비트 부호 없는 정수 toppings에 켜져있는 최하위 비트의 위치
= _BitScanForward(&index, toppings) -
최하위 비트의 번호 대신 해당 비트를 직접 구하고 싶은 경우
-> 음수 표현 2의 보수를 사용한다는 점 이용
int firstTopping = (toppings & -toppings);- 최소 원소 지우기
toppings = toppings & (toppings - 1);
toppings &= (toppings - 1);- 어떤 정수가 2의 거듭제곱 값인지 확인할 때 유용하다
-> 2의 거듭제곱 값들의 이진수 표현에는 켜진 비트 1개 뿐이다
-> 최하위 비트를 지웠을 때 0이라면 주어진 수는 2의 거듭제곱
집합의 부분 집합 순회
for(subset = pizza; subset; subset = ((subset - 1) & pizza)){
//subset은 pizza의 부분집합
}- for문 subet = 0인 시점에서 종료
-> 공집합은 방문하지 않는다
비트마스크 응용 예제
에라토스테네스의 체
- Boolean 배열 sieve[MAX_N]
-> (MAX_N / 8)개의 Boolean 배열 sieve[8]
-> (MAX_N / 8)개의 비트마스크(8bit)
-> 비트마스크(8bit) 배열 sieve[(MAX_N + 7) / 8]
-> unsigned char 배열 sieve[(MAX_N + 7) / 8]
//unsigned char = 8bit = 1byte
unsigned char seive[(MAX_N + 7) / 8];-
(MAX_N / 8)바이트의 메모리 사용
-
k번 원소: 배열의 (k/8)번째 원소의 (k%8)번째 비트 확인
-
비트마스크 연산 사용
-> sieve[k >> 3]: 배열의 (k/8)번째 원소
-> (1 << (k & 7)): (k%8)번째 비트
-> sieve[k >> 3] & (1 << (k & 7)): 배열의 (k/8)번째 원소의 (k%8)번째 비트 확인
#include <iostream>
using namespace std;
const int MAX_N = 100000;
int n;
unsigned char sieve[(MAX_N + 7) / 8];
//k가 소수인지 확인
inline bool isPrime(int k) {
return sieve[k >> 3] & (1 << (k & 7));
}
//k가 소수가 아니라고 표시
inline void setComposite(int k) {
sieve[k >> 3] &= ~(1 << (k & 7));
return;
}
//비트마스크를 사용하는 에라토스테네스의 체 구현
//이 함수를 수행하고 난 뒤, isPrime()을 이용해 각 수가 소수인지 알 수 있다
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)) {
//i의 배수 j들에 대해 isPrime[j] = false로 둔다
//i*i 미만의 배수는 이미 지워졌으므로 신경쓰지 않는다
for (int j = i * i; j <= n; j += i)
setComposite(j);
}
}
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
eratosthenes();
if (isPrime(n)) cout << n << " is a prime number\n";
else cout << n << " is not a prime number\n";
return 0;
}
15퍼즐 상태 표현하기
- 15퍼즐의 상태: 0 ~ 15까지의 숫자가 들어 있는 4*4 크기의 배열
-> 크기 16인 char 배열로 표현 가능
-> 배열 전체를 64비트 정수 하나로 표현 가능
//64비트 부호 없는 정수를 [0, 15] 범위의 정수 16개를 담는 배열로 사용하기
typedef unsigned long long unit64;
//mask의 index위치에 쓰인 값을 반환한다
int get (unit64 mask, int index){
return (mask >> (index << 2)) & 15;
}
//mask의 index위치를 value로 바꾼 결과를 반환한다
unit64 set(unit64 mask, int index, unit64 value){
return mask & ~(15LL << (index<<2)) | (value << (index << 2));
}
📌참고자료
- inline 함수
https://boycoding.tistory.com/220
- inline 키워드: 컴파일러에서 함수를 인라인 함수로 처리하도록 요청
-> 컴파일러가 코드를 컴파일하면 모든 인라인 함수가 인-플레이스(in-place) 확장
-> 즉, 함수 호출이 함수 자체의 내용 복사본으로 대체된다
- 장점: 함수의 오버헤드 제거
단점: 인라인 함수가 길거나 인라인 함수를 여러 번 호출하는 경우 컴파일된 코드가 더 길어질 수도 있다
- 현대 컴파일러: 함수를 인라인으로 표시하지 않더라도 컴파일러가 성능이 향상될 것으로 생각하는 함수를 자동으로 인라인화
-> inline 키워드를 사용할 필요가 없다
➖ 21-07-02
비트마스크의 응용 예제
O(1) 우선순위 큐
-
N개의 원소를 가진 우선순위 큐에 자료 삽입/삭제 -> O(logN)
-
우선순위가 특정 범위로 제한되어 있는 경우 -> O(1)
-
k개의 우선순위를 갖는 우선순위 큐
-> k개의 큐를 만들기 -> 각 큐에 원소가 있는지 여부를 비트마스크로 표현
-> 비트마스크의 첫번째 1비트를 찾는 연산 -> 가장 우선순위가 높은 원소의 위치를 알 수 있다
극대 안정 집합
-
N(N<=20)개의 화학 물질 운반
-> 각 화학 물질은 무해하지만, 같이 두었을 때 폭발하는 물질들이 있다
-> 이때 한 상자에 넣어도 폭발하지 않는 물질의 집합 = 안정 집합
-> 안정 집합 중 물질을 하나라도 추가하면 푹발이 일어나는 집합 = 극대 안정 집합(maximal stable set) -
각 물질에 대해 같이 뒀을 때 폭발하는 물질의 집합 -> 비트마스크에 저장
-
ex.
화학 물질[0] = A
화학 물질[1] = B
화학 물질[2] = C
화학 물질[3] = D
-> A와 B를 같은 상자에 넣거나 C와 D를 같은 상자에 넣으면 폭발하는 경우
explodes[0] = 0010
explodes[1] = 0001
explodes[2] = 1000
explodes[3] = 0100
int n;
//explodes[i] : i와 같이 두었을 때 폭발하는 물질 집합의 비트마스크 표현
int explodes[MAXN];
//주어진 집합이 안정적인지 확인한다
bool isStable(int set){
for(int i = 0; i<n; ++i)
//set에 물질 i가 포함되어 있고, set과 explodes[i]의 교집합이 공집합이 아닐 경우
if((set & (1 << i) ) && (set & explodes[i]))
return false;
return true;
}
//모든 극대 안정 집합의 수를 센다
int countMaxStableSet(){
int ret = 0;
//모든 집합 만들어보기
for(int set = 1; set < (1<<n); ++set){
//안정 집합이 아닌 경우는 셀 필요가 없다
if(!isStable(set)) continue;
//안정 집합들 중 극대 안정 집합인지 확인
bool canExpand = false;
for(int add = 0; add<n; ++add){
//add가 set에 포함되지 않은 물질이고, set과 explodes[add]의 교집합이 공집합인 경우
if(((set & (1 << add) == 0)&&((explodes[add] & set) == 0)){
canExpand = true;
break;
}
}
//다른 물질을 추가했을 때 안정적이라면(canExpand == true) 극대 안정 집합이 아니다
if(!canExpand)
++res;
}
return res;
}📌참고자료
- int / signed int (4바이트, 32비트)
: -2,147,483,648 ~ 2,147,483,647- unsigned / unsigned int (4바이트, 32비트)
: 0 ~ 4,294,967,295- unsigned long long / unsigned long long int (8바이트, 64비트)
: 0 ~ 18,446,744,073,709,551,615
- C++ 10진수 2진수로 출력
https://smallpants.tistory.com/7
- #include bitset 추가
- bitset<변수의 자료형의 비트수>(변수)
➖ 21-07-06
졸업 학기(GRADUATION)
-
전공 과목 N개 중 K개 이상을 수강해야 한다
그런데 각 과목은 해당 과목의 선수과목을 미리 수강했어야만 수강할 수 있으며,
각 학기마다 모든 과목이 개설되는 것은 아니라고 한다
이때, 졸업하기 위해 최소 몇 학기를 다녀야할까?
(한 과목도 수강하지 않은 학기는 휴학한 것으로 하며, 다닌 학기 수에 포함하지 않는다) -
각 테스트 케이스의 입력:
전공 과목의 수 N(1<=N<=12) (과목에 0~N-1까지의 번호가 매겨진다)
들어야 할 과목의 수 K(0<=K<=N)
학기의 수 M(1<=M<=10)
한 학기에 들을 수 있는 과목의 수 L(1<=L<=10)
이후 0번 과목부터 N-1번 과목까지
-> 해당 과목의 선수 과목의 수 R_i(0<= R_i<=N)와 R_i개의 과목의 번호(prerequisite)
이후 0번 학기부터 M-1번 학기까지
-> 해당 학기에 개설되는 과목의 수 C_i(0<=C_i<=10)와 C_i개의 과목의 번호(classes) -
각 테스트 케이스의 출력:
다녀야 할 최소 학기 수 출력
(M학기 내에 졸업할 수 없는 경우 IMPOSSIBLE 출력)
const int INF = 987654321;
const int MAXN = 12;
int n, k, m, l;
//prerequisite[i]: i번째 과목의 선수 과목의 집합
int prerequisite[MAXN];
//classes[i]: i번째 학기에 개설되는 과목의 집합
int classes[10];
//cache[semester][taken]
//semester: 현재 학기
//taken: 지금까지 들은 과목의 집합
int cache[10][1<<MAXN];
//n의 이진수 표현에서 켜진 비트의 수 반환
int bitCount(int n);
//이번 학기가 semester이고, 지금까지 들은 과목의 집합이 taken일 때
//k개 이상의 과목을 모두 들으려면 몇 학기나 더 있어야 하는가?
//불가능한 경우 INF 반환
int graduate(int semester, int taken){
//base case
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))
if((prerequisite[i] & taken) == prerequisite[i])
canTake &= ~(1<<i);
}
//canTake 집합의 모든 부분집합을 순회한다
for(int take = canTake; take > 0; take = ((take - 1) & canTake)){
if(bitCount(take) > l) continue;
ret = min(ret, graduate(semester+1, take | taken) + 1);
}
//이번 학기에 아무것도 듣지 않을 경우 = 휴학
ret = min(ret, graduate(semester+1,taken));
return ret;
}