비트마스크(BitMask)

비트마스크를 활용한 테크닉과 기법

비트마스크 자체는 알고리즘이 아니지만 다른 알고리즘과 같이 사용되어 어렵게 느껴질 수가 있다.

 

비트마스크(BitMask)

정수를 이진수 형태로 표현하여 비트연산을 활용하는 방법

 

이를 활용하면 비트연산을 통해 삽입,삭제,조회 등이 간단해짐

시간복잡도 O(1)으로 더 빠른 연산이 가능

메모리를 적게 사용함

---

비트 연산

AND (&)

OR (|)

XOR (^)

SHIFT (>>,<<)

NOT (~)

 

비트 연산 응용 및 활용

원소 추가

00000000 | (1 << n) // n번째 인자 추가

원소 제거

11111111 & ~(1 << n) // n번째 인자 제거

원소 조회

???????? & (1 << n) // n번째 인자가 있는지(1) 없는지(0)

원소 토글

???????? ^ (1 << n) // n번째 인자를 on->off or off->on

진법 변환 활용

//4진법 변환
#define LIMIT 10

vector<int> gen(int k) {
	vector<int> a(LIMIT);
	for(int i=0; i<LIMIT; ++i) {
		a[i] = (k&3);
		k >>= 2;
	}
	return a;
}

vector<int> ans(LIMIT);
for (int i = 0; i < 4^LIMIT; ++i) { //4^LIMIT 4의 LIMIT 승
	ans = gen(i);
}

 

부분수열 활용

재귀뿐만 아니라 비트마스크를 이용하여 부분수열을 만들 수 있다.

부분수열 -> 이진수 -> 수로 표현 가능

 

 

 

 

 

비트마스크 예제

14225 부분수열의 합 : www.acmicpc.net/problem/14225

//boj 14225 부분수열의 합
#include <iostream>
using namespace std;

bool c[20 * 100000 + 10];
int a[21];

int main(void) {
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	for (int i = 0; i < (1 << n); ++i) {
		int sum = 0;
		for (int j = 0; j < n; ++j) {
			if (i&(1<<j)) sum += a[j];
		}
		c[sum] = true;
	}
	for (int i = 0; i <= (1 << n); ++i) {
		if (c[i] == false) {
			cout << i << '\n';
			break;
		}
	}
}

 

1062 가르침 : www.acmicpc.net/problem/1062

int는 32bit이므로 알파벳 26개를 표현할 수 있다.

비트마스크를 이용하여 단어별 검사를 O(1)으로 좀 더 효율적으로 문제를 풀 수 있다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int n, k;
int ans;

int count1(int mask, vector<int> &words) {//mask : 가르친 알파벳 마스크, words : 확인할 단어
	int sum = 0;
	for (auto word : words) { // word : i번째 단어를 구성하는 알파벳
		if ((word & ((1 << 26) - 1 - mask)) == 0) sum++; // (E-mask)교집합words = 공집합 임을 이용., 배우지 않은 알파벳이 있는지 검사
	}
	return sum;
}

void go(int index, int k, int mask, vector<int> &words) { // index : 알파벳, k : 남은 선택 수
	if (k < 0) return;
	if (index == 26) {
		int temp = count1(mask, words);
		if (temp > ans) ans = temp;
		return;
	}
	go(index + 1, k, mask, words); //index+1번째 알파벳을 배우지 않을 경우
	if(index+1 != 'c'-'a' && index + 1 != 'i'-'a'&& index + 1 != 'n'-'a'&& index + 1 != 't'-'a') {
		mask |= (1 << (index+1));
		go(index + 1, k - 1, mask, words); //index+1번째 알파벳을 배울경우
	}	
	return;
}


int main() {
	cin >> n >> k;
	vector<int> words(n);
	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		for (auto x : s) {
			words[i] |= (1 << (x - 'a')); // 단어를 비트형태로 저장
		}
	}
	int mask = 0;
	mask |= (1 << 'a' - 'a');
	mask |= (1 << 'c' - 'a');
	mask |= (1 << 'i' - 'a');
	mask |= (1 << 'n' - 'a');
	mask |= (1 << 't' - 'a');
	go(0, k - 5, mask, words);
	if (k < 5) cout << 0;
	else cout << ans;
}

 

 

13460 구슬탈출2 : www.acmicpc.net/problem/13460

상하좌우를 최대 10번 이동하는 모든 경우의수를 구하고 이를 시뮬레이션하는 문제

4^10으로 생각할 수 있지만, 같은 방향으로 한번 더 이동하는 경우는 최소가 아니므로 제외한다 : 4*3^9

반대방향으로 이동하는 경우도 최소가 아니므로 제외한다 : 4*2^9 고로 2048가지의 경우의수에 대하여 시뮬레이션하면 된다.

한칸씩 이동하는 걸로 생각하며 문제를 풀면된다.

1. 공이 벽에 의해 이동하지 못한 경우

2. 공이 구멍에 빠진경우

3. 공이 다른공에 의해 이동하지 못한 경우

4. 공이 빈공간으로 한칸 이동한 경우

#include<iostream>
#include <string.h>
#include <vector>
using namespace std;

int h, w;
char maps[12][12];
//0:위, 1:오른쪽, 2:아래, 3:왼쪽
int ny[4] = { -1, 0, 1, 0 };
int nx[4] = { 0, 1, 0, -1 };


vector<int> gen(int num) { // 4진법 전환
	vector<int> ret(10);
	for (int i = 0; i < 10; ++i) {
		ret[i] = num & 3;
		num >>= 2;
	}
	return ret;
}

bool isValid(vector<int> num) { // 유효한지? 이전과 같이 이동하는경우->->, 반대로 이동하는경우 <--> false

	for (int i = 0; i+1 < 10; ++i) {
		if (num[i] == num[i + 1]) return false;
		if ((num[i] + num[i + 1]) % 2 == 0) return false;
	}

	return true;
}

int go(int index, vector<int> &a, pair<int, int> r, pair<int, int> b, char maps[][12]) { //index : 몇번째 이동, a : 이동순서, r : 빨간볼 위치, b : 파란볼 위치
	if (index == 10) return 11;
	bool rHoll = false, bHoll = false; //구멍에 들어갔으면 true
	bool rMove = true, bMove = true; // 움직였으면 true
	pair<int, int> nr = r;
	pair<int, int> nb = b;

	int dir = a[index];
	while (rMove || bMove) { // 둘다 움직이지 않으면 break
		if (rHoll == false) {
			nr.first += ny[dir];
			nr.second += nx[dir];

			if (maps[nr.first][nr.second] == 'O') { //구멍에 빠진경우
				rMove = false;
				rHoll = true;
				maps[r.first][r.second] = '.'; 
				nr = r;
			}
			else if (maps[nr.first][nr.second] == '.') { //움직인경우
				swap(maps[r.first][r.second], maps[nr.first][nr.second]);
				rMove = true;
				r = nr;
			}
			else { // 움직이지 못할경우 
				rMove = false;
				nr = r;
			}
		}
		if (bHoll == false) {
			nb.first += ny[dir];
			nb.second += nx[dir];
			if (maps[nb.first][nb.second] == '#') {
				bMove = false;
				nb = b;
			}
			else if (maps[nb.first][nb.second] == 'O') {
				bMove = false;
				bHoll = true;
				maps[b.first][b.second] = '.';
				nb = b;
			}
			else if (maps[nb.first][nb.second] == '.') {
				swap(maps[b.first][b.second], maps[nb.first][nb.second]);
				bMove = true;
				b = nb;
			}
			else {
				bMove = false;
				nb = b;
			}
		}
	}
	if (bHoll) return 11;
	if (rHoll) return index;

	return go(index + 1, a, r, b, maps);
}

int main(void) {
	vector<int> a(10);
	cin >> h >> w;
	pair<int, int> r, b;
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			cin >> maps[i][j];
			if (maps[i][j] == 'R') {
				r.first = i;
				r.second = j;
			}
			if (maps[i][j] == 'B') {
				b.first = i;
				b.second = j;
			}
		}
	}
	int sum = 0;
	int ans = 11;
	for (int i = 0; i < 1048576; ++i) {
		a = gen(i);
		char temp_maps[12][12];
		if (!isValid(a)) continue;
		memcpy(temp_maps, maps, sizeof(maps));
		
		int temp = go(0, a, r, b, temp_maps);
		if (temp < ans) ans = temp;
	}
	if (ans + 1 > 10) cout << -1;
	else cout << ans + 1;
}