최근 수정 시각: 2021-08-08 15:22:21
_
1. 소개
비트마스크란, 비트를 변경하여 정보를 저장하는 방법을 뜻한다. 비트마스킹에서는 모든 연산에 Bit Operator를 사용한다.
2. 장점
비트마스크는 다음과 같은 주요 장점이 있습니다.
-
메모리 사용량의 큰 단축
비트마스크는 하나의 bool 정보를 하나의 비트에 저장할 수 있습니다. 실제 하나의 int형 정수는 \(32bit = 4byte\) 이므로, 1 byte bool 정보 32개(\(1 \times 32 = 32\)(byte))를 int형 정수 1개(4(byte))로 표현하여 메모리 사용량을 줄일 수 있습니다.
-
실행시간의 단축
예를 들어 int형 정수로 비트 연산을 하면 32개의 bool 정보에 대한 연산을 한번에 진행할 수 있기 때문에 연산 횟수가 상수배 줄어들게 됩니다.
-
코드 길이의 단축
비트마스크를 쓸 경우 복잡한 코드가 짧게 줄어들 수 있습니다. 비트마스킹을 잘 사용하면, 코드의 가독성이 향상될 수 있습니다.
3. 코드
비트마스킹으로 배열에서 처리할 수 있는 있는 많은 기능들을 구현해 봅시다. 대부분의 구현들이 간단한 비트 연산 한번으로 가능합니다. 다음 코드를 봅시다.
#include <bits/stdc++.h>
int Bitmask;
int main(){
Bitmask = 10; //이진수로 1010
int n, tmp = Bitmask;
scanf("%d", &n);
if(Bitmask & (1 << n)) printf("arr[%d] is true.\n", n); //원소의 존재 확인
scanf("%d", &n);
Bitmask |= (1 << n); //원소 추가
printf("%dth(st, nd, rd) element added.\n", n);
scanf("%d", &n);
Bitmask &= ~(1 << n); //원소 삭제, 만약 원소가 없으면 그대로
printf("%dth(st, nd, rd) element deleted.(if in array)", n);
scanf("%d", &n);
Bitmask ^= (1 << n); //원소 토글, if문이 필요 없습니다.
printf("%dth(st, nd, rd) element toggled.", n);
int Union = (Bitmask | tmp); //합집합, for문 불필요
int Intersection = (Bitmask & tmp); //교집합
int Relative_Component = (Bitmask & ~tmp); //차집합
int Symmetric_Difference = (Bitmask ^ tmp) //대칭차집합
int Complement_Set = ~Bitmask //여집합
int Min_element = (Bitmask & -Bitmask); //최소원소
Bitmask &= (Bitmask - 1); //최소원소 지우기
for(int Sub = Bitmask, i = 1; Sub; Sub = ((Sub - 1) & Bitmask), i++){
printf("Subset %d: %d", i, Sub); //모든 부분집합 순회
}
//비트마스킹을 사용할 때는 모든 비트 연산의 주변에 괄호를 치는 것을 추천합니다. 잘못하면 연산자 우선순위 때문에 어이없는 오류가 날 수도 있기 떄문입니다.
}
3.1. 코드 설명
3.1.1. 원소 확인
Shift 연산을 통해 1비트의 자리를 설정하고, AND연산을 하여 0인지 0이 아닌 다른 값인지 확인하여 원소가 존재하는지 검사할 수 있습니다. 이떄, AND연산의 결과가 꼭 1은 아닙니다. 왜냐하면 AND연산은 참 거짓이 아닌 계산의 결과값, 즉 그 자리에 원소가 있다면 2의 거듭제곱을 반환하기 떄문입니다.
3.1.2. 원소 추가
OR 연산을 통해 원소를 추가해 줍니다. 이미 원소가 있다면 아무런 변화가 생기지 않습니다.
3.1.3. 원소 삭제
AND 연산을 통해 원소를 삭제해 줍니다. 삭제할 위치의 비트만 1인 상태에서 NOT연산을 취해 준다면 비트가 반전되어 그 비트만 0이 됩니다. 원소가 없는 상태에서 특정 원소를 삭제하려 한다면 아무런 변화가 생기지 않습니다.
3.1.4. 원소 반전(토글)
XOR 연산으로 원소를 토글해줍니다. 원소가 1이면 0으로, 0이면 1으로 바꿔준다는 것을 쉽게 알 수 있습니다. 여기서 눈여겨봐야 할 점은, 조건문이 전혀 필요없다는 것입니다. 조건문 없이 원소를 토글할 수 있다는 점에서 코드 길이를 줄일 수 있다는 장점을 확인할 수 있습니다.
3.1.5. 합집합
두 집합 사이 OR 연산으로 원소가 둘 중 한 곳에라도 있다면 1로 표시하여 합집합을 계산합니다.
3.1.6. 교집합
두 집합 사이 AND 연산으로 원소가 두 곳 모두 있다면 1로 표시하여 교집합을 계산합니다.
3.1.7. 차집합
두 번째 집합을 비트반전(NOT) 반전한 다음 AND 연산으로 첫 번째 원소에만 포함한 원소를 구하여 차집합을 계산합니다.
3.1.8. 대칭차집합
두 집합 사이 XOR 연산으로 원소의 유무가 다르다면 1로 표시하여 대칭차집합을 계산합니다.
3.1.9. 여집합
NOT 연산으로 원소를 반전하여 여집합을 계산합니다.
3.1.10. 최소 원소 찾기
최소원소 찾기는 비트마스킹의 장점을 다시 한번 보여주는 좋은 예입니다. 위 식은 보수를 이용한 것으로, 보수가 -N-1으로 표현가능함을 이용하여 가장 작은 원소를 손쉽게 찾을 수 있습니다.
또한, 1을 빼면 최소원소 직전의 0들은 모두 1로 반전되고 최소비트 하나만 0으로 반전되기 떄문에 최소비트를 빠르게 뺄 수도 있습니다. 최소 원소를 구하고 반전시키는 것보다 훨씬 빠릅니다.
3.1.11. 시간복잡도
여기까지 모든 연산의 시간복잡도는 모두 \(O(1)\)입니다.
3.1.12. 부분집합 순회
마지막으로 부분집합 순회입니다.
먼저 현재 상태를 나타내는 변수에 1을 뺀다면 최하위 비트와 그 밑의 0들은 전부 반전됩니다. 따라서 최소 원소의 유무가 바뀝니다. 그 후 원래 집합과의 교집합을 구한다면, 그 원래 집합에 속하지 않던 원소들은 모두 0이 됩니다. 그리하여 모든 부분집합을 순회할 수 있습니다.
시간복잡도는 \(O(2^{N})\)입니다.
4. 예제
비트마스킹은 주로 동적계획법, 즉 다이나믹 프로그래밍과 같이 자주 쓰입니다. 다음 예제를 봅시다. 이 문제는 외판원 순회 문제입니다.
이 문제의 풀이 방법은 비트마스크와 다이나믹 프로그래밍입니다. 먼저 시작 도시를 정한 후, 그 도시로 부터 갈 수 있는 방법을 완전탐색 해 나갑니다. 이떄, 그냥 일반적인 완전탐색은 시간이 엄청나게 오래 걸리므로, 다이나믹 프로그래밍을 사용합니다. 점화식은 다음과 같습니다.
\(TSP(curr, visited) = min(TSP(next, visited \cup next) + dist[curr][next]) \)
\((0 \leq next \leq N - 1, next \neq curr, next \notin visited)\)
현재 도시의 순회 최솟값을 알기 위해 다음 돌아가는 모든 경로를 탐색한 후 그 값을 DP에 저장하면 문제가 풀릴 수 있습니다. 이떄, 집합 visited를 비트마스킹으로 구현할 수 있습니다.
이 코드는 DP의 원소의 개수가 \(2^{N} \times N\)이고 이를 각 도시마다 한 번씩 N번 탐색하여 총 시간복잡도는 \(O(2^{N} \times N^{2})\)입니다. 만약 다이나믹기법을 쓰지 않았다면 모두 일일이 탐색해야 하므로 시간복잡도는 \(O(N!)\)이 되었을 것입니다. 아직 느리기는 하지만, 확실히 빨라졌습니다. 여기에 비트마스킹으로 연산속도까지 빨라졌으니, 문제에서 주어진 N의 범위쯤은 거뜬합니다.
최근 수정 시각: 2021-08-08 15:22:21