백준 11723 - 집합

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

11723번: 집합

비트 마스킹을 배우고 다시 풀었다.

정수의 이진수 표현을 이용해 위 문제를 다른 방식으로 해결할 수 있었다.

 

자연수 47을 이진수로 표현해보자. 47 = 32 + 0 + 8 + 4 + 2 + 1 = 101111(2)

 

이 이진수 101111를 하나의 집합으로 본다면 어떨까?

 

예를 들어, 101111의 오른쪽 4번째 자리의 값은 1이므로 이 집합은 4를 포함하고,

101111의 오른쪽 5번째 자리의 값은 0이므로 이 집합은 5를 포함하지 않는다.

 

이 개념을 확장하면 문제의 6가지 연산은 비트 연산자를 통해 다음과 같이 나타낼 수 있다.

 

1) add

집합 01011에 3을 추가해보자.

01011과 00100의 OR 연산을 통해 3번째 자리 값이 반드시 1이 되게 할 수 있다.

 

2) remove

반대로 집합 01111에서 3을 제거해보자.

01111과 11011의 AND 연산을 통해 3번째 자리 값이 반드시 0이 되게 할 수 있다.

 

3) check

마찬가지로 AND 연산을 통해 구현할 수 있다.

3을 포함하는 집합 01111과 00100의 AND 연산 수행 시 100(2)라는 양수값을 얻으며,

그렇지 않은 집합 01011과 연산할 경우 0을 얻게 된다.

 

4) toggle

01011에서 3을 토글(전환) 해보자.

01011과 00100의 XOR 연산을 수행하면 3번째 자리 값은 1에서 0, 0에서 1이 되며 (A xor 1 = ~A)

나머지 모든 자리의 값은 유지된다. (A xor 0 = A)

 

5) all, empty

쉽다.

all은 기존 집합(정수)에 1 20개짜리 이진수를,

empty는 0을 대입하면 된다.

 

마지막으로 구현한 코드는 다음과 같다.

    if (op == "all") { //all
        res = (1 << 20) - 1; //0b11111111111111111111
        return;
    }

    switch (op[0]) {
    case 'a':
        cin >> x;
        temp = 1 << (x - 1);
        res |= temp; //OR
        break;
    case 'r': //remove
        cin >> x;
        temp = ~(1 << (x - 1));
        res &= temp;
        break;
    case 'c': //check
        cin >> x;
        temp = 1 << (x - 1);
        cout << ((res & temp) > 0) << '\n';
        break;
    case 't': //toggle
        cin >> x;
        temp = 1 << (x - 1);
        res ^= temp;
        break;
    case 'e': //empty
        res = 0;
    }

 

배운 내용

 

비트마스킹이란? 정수의 이진수 표현을 사용한 문제 풀이 기법

XOR 연산 복기 (A xor 1 = ~A), (A xor 0 = A)

C++ 이진수 표현법 0b0101010101...