[C++] 집합 (백준 11723번)

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

 

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int m, n;
    string op;
    cin >> m;
    int now = 0;

    for (int i = 0; i < m; i++) {
        cin >> op;
        if (op == "add") {
            cin >> n;
            now = now | (1 << (n - 1));
        }
        else if (op == "remove") {
            cin >> n;
            if ((now & (1 << (n - 1))) != 0) {
                now = now ^ (1 << (n - 1));
            }
        }
        else if (op == "check") {
            cin >> n;
            if ((now & (1 << (n - 1))) == 0) {
                cout << 0 << '\n';
            }
            else {
                cout << 1 << '\n';
            }
        }
        else if (op == "toggle") {
            cin >> n;
            now = now ^ (1 << (n - 1));
        }
        else if (op == "all") {
            now = -1;
        }
        else if (op == "empty") {
            now = 0;
        }
    }
}

(정답)

 

비트 연산자

AND 연산 (&) : 둘 다 1이면 1 반환 (ex) 1010 & 1111 = 1010

OR 연산 (|) : 하나라도 1이면 1 반환 (ex) 1010 | 1111 = 1111

XOR 연산 (^) : 둘이 같으면 0, 다르면 1 반환 (ex) 1010 ^ 1111 = 0101

NOT 연산 (~) : 반전 (0이면 1, 1이면 0 반환) (ex) ~1010 = 0101

왼쪽 shift (<<) : 왼쪽으로 특정 칸만큼 이동 (ex) 001010 << 2 = 101000

오른쪽 shinft (>>) : 오른쪽으로 특정 칸만큼 이동 (ex) 001010 >> 2 = 000010

 

비트마스킹

컴퓨터는 내부적으로 bit 단위로 연산을 한다. 이러한 비트의 특성을 이용해서 이진수 표현을 자료구조로 쓰는 기법을 비트마스킹이다. 

 

비트마스킹을 통한 집합 표현

비트마스킹을 이용하면 집합을 쉽게 표현할 수 있다. 구체적으로, 원소의 개수가 n개인 집합이 있다고 하면, 원소에 0부터 n-1까지 번호를 부여해서 부분 집합으로 나타낼 수 있다. 번호에 해당하는 비트 하나가 하나의 원소 상태며, 비트가 1이면 해당 원소가 집합에 포함되어 있다는 의미고, 0이면 포함되지 않는다는 의미이다. 예를 들어, 0부터 4까지의 수가 있을 때 1, 3, 4로 이루어진 집합은 01011로 표현할 수 있는 것이다. 

 

비트마스킹의 장점

1. 빠른 수행 시간

2. 간결한 코드

3. 적은 메모리 사용량