[백준] 11723 집합(BitMasking)

백준 집합 문제 비트마스킹으로 풀어보기

비트마스크

컴퓨터는 기본적으로 모든 자료를 이진수로 사용합니다. 이때 정수로 이진수로 표현하는 점을 활용해서 정수의 이진수 표현을 자료구조로 쓰는 기법을 말합니다. 비트는 이진수를 뜻하는 말로 0, 1의 값을 가진다.

---

비트 마스크 장점

• 빠른 연산속도를 가진다.

비트마스크 연산을 bit연산인만큼 O(1)에 구현되는 경우가 대부분이다. 비트의 개수만큼 원소를 다룰 수 있기에 연산 횟수가 늘어날수록 차이가 커진다.

• 메모리 사용량이 적다.

bit가 n개라고 가정하면 bit당 2가지의 경우의 수를 가지기 때문에 $2^n$ 의 경우의 수를 하나의 정수로 표현할 수 있다는 점에서 메모리 효율성이 극대화된다.

---

비트 연산자

연산자	사용	설명	예시
AND	A & B	A의 모든 비트와 B의 모든 비트를 AND연산한다. AND연산: 비교하는 두 비트가 둘다 1이라면 1, 아니라면 0 출력	A = 5 = 101(2); B = 7 = 111(2); A & B = 5 = 101(2);
OR	A | B	A의 모든 비트와 B의 모든 비트를 OR연산한다. OR연산: 비교하는 두 비트중 하나라도 1이면 1, 둘다 0이라면 0 출력	A = 5 = 101(2); B = 7 = 111(2) A | B = 7 = 111(2);
XOR	A ^ B	A의 모든 비트와 B의 모든 비트를 XOR연산한다. XOR연산: 비교하는 두 비트가 다르다면 1, 같다면 0 출력	A = 5 = 101(2); B = 7 = 111(2) A ^ B = 2 = 010(2);
NOT	~A	A의 모든 비트에 NOT연산한다. NOT연산: 비트가 0이라면 1, 1이라면 0 출력	A = 5 = 101(2); ~A = 2 = 010(2);
SHIFT	A « B A » B	A를 B비트만큼 SHIFT연산한다. SHIFT연산: 비트를 왼쪽, 오른쪽으로 옮긴다. 이때 옮기고 남는 비트는 0으로 출력	A = 5 = 101(2); A « 2 = 4 = 100(2); A » 2 = 1 = 001(2);

---

[백준] 11723 집합

문제

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

조건

add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
all: S를 {1, 2, …, 20} 으로 바꾼다.
empty: S를 공집합으로 바꾼다.

입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력

check 연산이 주어질때마다, 결과를 출력한다.

코드

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int m;
    cin >> m;
    int bits = 0;   //집합 S의 원소 유무를 표현할 수 있는 변수 ex) 1 = 0000...0000001(2) 일때 자릿수 순서대로 1인 경우는 집합안에 존재, 0인경우 집합안에 존재하지 않음
    for(int i = 0; i < m; i++){
        string order;
        int val = 0;
        cin >> order;
        if(order == "add"){
            cin >> val;
            bits |= (1 <<  val);    // OR 연산
        }
        else if(order == "remove"){
            cin >> val;
            bits &= ~(1 << val);    // AND, NOT, SHIFT 연산 활용
        }
        else if(order == "check"){
            cin >> val;
            if(bits & (1 << val))   // AND, SHIFT연산 활용
                cout << "1\n";
            else
                cout << "0\n";
        }
        else if(order == "toggle"){
            cin >> val;
            bits ^= (1 << val);     // XOR, SHIFT연산 활용
        }
        else if(order == "all"){
            bits = (1 << 21) - 1;   // SHIFT 연산 활용
        }
        else if(order == "empty"){
            bits = 0;
        }
    }
    return 0;
}

참고자료

https://velog.io/@codenmh0822/%EB%B9%84%ED%8A%B8%EB%A7%88%EC%8A%A4%ED%81%ACBitMask-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98A
https://travelbeeee.tistory.com/451