Algorithm

[Algorithm] 백준 알고리즘 기초 2/2 - 비트마스크

tenacy 2024. 7. 20. 00:00

비트마스크는 비트(bit) 연산을 사용해 부분 집합을 표현하는 것이다.

비트 연산

비트 연산에는 대표적으로 다음과 같이 네 가지 연산이 있다.

  • & ($AND$) : 두 조건이 참이면 참, 아니면 거짓으로 처리
  • | ($OR$) : 두 조건 중 하나라도 참이면 참, 아니면 거짓으로 처리
  • ~ ($NOT$) : 주어진 조건이 참이면 거짓, 거짓이면 참으로 처리
  • ^ ($XOR$) : 두 조건이 서로 다르면 참, 아니면 거짓으로 처리

다음은 비트 연산의 이해를 돕기 위한 표이다.

십진수 $A$와 $B$의 비트 연산은 $A$와 $B$를 이진수로 변환하여 가장 뒤의 자리부터 하나씩 연산을 수행하면 된다.

예를 들어, $A=27$, $B=83$인 경우 이를 이진수로 변환하면 $A = 11011_{(2)}$, $B=1010011_{(2)}$이다.

$A$와 $B$에 대해 $AND$ 연산을 진행할 때, $B$에 비해 $A$의 부족한 자리를 $0$으로 채운다.

따라서, $0011011_{(2)}\,\&\,1010011_{(2)}=0010011_{(2)}=10011_{(2)}$이다.

$OR$ 연산, $XOR$ 연산에 대해서도 동일하다.

$NOT$ 연산의 경우에는 자료형에 따라 결과가 달라진다.

예를 들어, $A=83$인 경우 이를 이진수로 변환하면 $A=1010011_{(2)}$인데

$A$가 8비트 자료형이라면 $\sim{A}=0101100_{(2)}$이지만,

$A$가 32비트 자료형이라면 $\sim{A}=11111111\,11111111\,11111111\,0101100_{(2)}$이 된다.

이는 $A$의 남은 비트에 $0$이 채워져있기 때문이다.

또한, unsigned와 signed에 따라서 보여지는 값이 다르다.

추가적으로 비트 연산에는 << ($SHIFT\,LEFT$)와 >> ($SHIFT\,RIGHT$) 연산이 있다.

$A<<B$는 $A$를 왼쪽으로 $B$비트 만큼 민다는 뜻이며, 식으로는 $A\times{2^B}$와 같이 쓸 수 있다.

그리고 $A>>B$는 $A$를 오른쪽으로 $B$비트 만큼 민다는 뜻이며, 식으로는 $A\div{2^B}$와 같이 쓸 수 있다.

비트마스크를 이해하기 위한 비트 연산의 내용은 가볍게 이 정도로 마친다.

비트마스크

비트 연산은 정수로 집합을 표현할 수 있다.

예를 들어, 정수 $570$이 있다.

이를 이진수로 나타내면 $570=2^1+2^3+2^4+2^5+2^9=100011101_{(2)}$이고,

집합으로 표현하면 ${1, 3, 4, 5, 9}$이다.

이것으로 알 수 있는 비트 연산의 장점에는 무엇이 있을까?

  1. 공간을 절약할 수 있다.

만약 앞의 이진수를 배열을 이용하여 나타낸다고 했을 때, 0부터 9까지 10개의 인덱스가 필요하지만 비트 연산을 이용하면 정수 하나로 나타내기 때문에 공간을 절약할 수 있다.

  1. 시간을 절약할 수 있다.

정수는 배열의 인덱스로 사용할 수 있지만, 집합은 불가능하다.

물론, 가능한 언어도 있지만 시간 복잡도가 $\log{}{}$단위이기 때문에 불가능하다고 보면 된다.

따라서, 정수는 배열에서 탐색할 때 $1$의 시간 복잡도를 가지기 때문에 시간을 절약할 수 있다.

다음은 비트마스크를 사용할 때 주의할 점이다.

  1. 정수로 표현한 집합에 들어갈 수 있는 최댓값을 알아야 한다.

보통 32비트의 int형을 사용하여 수를 나타내는데 $2^{32}$을 넘어가는 수는 int형으로 나타낼 수 없기 때문에 $2^{32}$이 넘지 않는 선에서 수를 나타내야 한다.

  1. 비트마스크는 보통 $0$부터 $N-1$까지 정수로 이루어진 집합을 나타낼 때 사용한다.

만약 $1$부터 $N$까지 정수로 이루어진 집합을 사용하면, 공간이 2배 더 필요하다.

때문에 각종 연산을 변형해서 사용해야 한다.

정수 $570$으로 표현한 집합 ${1, 3, 4, 5, 9}$가 있다고 할 때, 비트마스크는 다음과 같은 역할을 수행한다.

  1. 어떤 수가 포함되어 있는지 검사

$AND$ 연산을 이용한다.

정수 $570$에 $0$이 포함되어 있는지 검사하려고 한다.

$570\,\&\,2^0=570\,\&\,(1<<0)=0$



이해를 위해 하나만 더 해보자.

정수 570에 3이 포함되어 있는지 검사하려고 한다.

$570\,\&\,2^3=570\,\&\,(1<<3)=8\neq{0}$



이와 같이 연산의 결과가 0이면 포함되어 있지 않다는 것이고, 0이 아니면 포함되어 있다는 것이다.

  1. 추가

$OR$ 연산을 이용한다.

정수 $570$에 $2$를 추가하려고 한다.

$570\,\vert\,2^2=570\,\vert\,(1<<2)=574$



정수 $570$에 $3$을 추가하려고 한다.

$570\,\vert\,2^3=570\,\vert\,(1<<3)=570$



이와 같이 추가하려는 수가 이미 존재하면 기존의 수를 반환하고, 존재하지 않으면 기존의 수에 추가하여 반환한다.

  1. 제거

$AND$와 $NOT$ 연산을 이용한다.

정수 $570$에서 $3$을 제거하려고 한다.

$570\,\&\,\sim(2^3)=570\,\&\,\sim(1<<3)=562$



정수 $570$에 $2$를 제거하려고 한다.

$570\,\&\,\sim(2^2)=570\,\&\,\sim(1<<2)=570$



이와 같이 제거하려는 수가 존재하지 않으면 기존의 수를 반환하고, 존재하면 기존의 수에서 제거하여 반환한다.

  1. 토글

$XOR$ 연산을 이용한다.

정수 $570$에 $2$를 토글하려고 한다.

$570\,\,$^$\,\,2^2=570\,\,$^$\,\,(1<<2)=574$



정수 $570$에 $3$을 토글하려고 한다.

$570\,\,$^$\,\,2^3=570\,\,$^$\,\,(1<<3)=562$



이와 같이 토글하려는 수가 존재하면 기존의 수에서 제거하여 반환하고, 존재하지 않으면 기존의 수에서 추가하여 반환한다.

비트마스크에서 전체 집합은 $(1<<N)-1$으로 나타내고, 이는 $1-N$을 $0-(N-1)$로 바꿔 공간을 절약하기 위함이다.

공집합은 $0$으로 나타낸다.

비트 연산을 사용할 때는 연산자 우선순위를 생각해야 한다.

일반적으로 비트 연산은 사칙 연산보다 우선순위가 낮고 비트 $AND$, $OR$, $XOR$는 비교 연산보다 운선순위가 낮다.

그리고 예외적으로 비트 $NOT$은 사칙 연산보다 우선순위가 높다.

예를 들어, $1<<N-1은$ $(1<<N)-1$일까? $1<<(N-1)$일까?

앞서 말했듯이, 비트 연산은 사칙 연산보다 우선순위가 낮기 때문에 $1<<(N-1)$이다.

  • C언어 연산자 우선순위 표

출처: https://dojang.io/mod/page/view.php?id=188

C++ 기준으로 int는 32비트, long long은 64비트이다.

이런 이유로, 64비트를 넘는 비트는 정수로 나타낼 수 없는 게 원칙이지만 C++의 bitset을 이용하면 가능하다.

bitset STL의 사용법은 이 포스팅에서 다루지 않는다.

문제를 하나 풀어보면서 비트마스크의 사용법을 알아보자.

백준 1182번 - 부분수열의 합

https://www.acmicpc.net/problem/1182

서로 다른 $N$개의 정수로 이루어진 수열이 있으므로, 모든 집합의 개수는 $2^N$이다.

전체 집합은 $(1<<N)-1$이고 공집합은 제외해야 하므로 모든 부분 수열을 만드는 코드는 다음과 같다.

  • 모든 부분 수열 생성 구현
for (int i=1; i<(1<<n); i++) { // 공집합은 제외해야 하므로 i=1부터
    // ...
}

그리고 집합에 무엇이 포함되어 있는지 검사하는 코드는 다음과 같다.

for (int i=1; i<(1<<n); i++) {
    for (int k=0; k<n; k++) {
        if (i&(1<<k)) {
            // ...
        }
    }
}

소스코드(C++)

#include <iostream>
using namespace std;

int main() {
    int n, s;
    cin >> n >> s;
    int a[20];
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ans = 0;
    for(int i = 1; i < (1 << n); i++) {
        int sum = 0;
        for(int j = 0; j < n; j++) {
            if(i & (1 << j)) {
                sum += a[j];
            }
        }
        if(sum == s) {
            ans += 1;
        }
    }

    cout << ans << '\n';

    return 0;
}