[백준/C++] 11723번: 집합 - 비트마스킹을 활용한 최적화

1. 문제 정보

• 문제 번호: 11723번
• 문제 이름: 집합
• 문제 요약:
• 비어있는 집합 $S$에 대해 add, remove, check, toggle, all, empty 연산을 수행하는 프로그램을 작성하라. 원소는 1부터 20까지의 정수이며, 수행해야 하는 연산의 수는 최대 3,000,000개이다.

 

2. 접근 방법 (알고리즘)

❌ 첫 번째 시도: std::set 사용 (시간 초과)

처음에는 원소를 관리하기 위해 std::set<int>을 사용했다.

• 원인: set의 각 연산은 O(log N)이지만, 300만 개의 연산을 처리하기에는 메모리 할당과 트리 균형 유지 등의 오버헤드가 너무 크다.
• 시간 복잡도: O(M log N), 여기서 M은 연산 횟수이다. 결과는 시간 초과였다.

✅ 최종 접근: 비트마스킹 (성공)

문제에서 주어지는 원소의 범위가 1~20으로 매우 작다는 점에 주목했다.

• 핵심 아이디어: 정수형 변수(int)는 32비트이므로, 각 비트를 하나의 원소로 취급할 수 있다.
  • 예를 들어, 3번 비트가 1이면 집합에 숫자 3이 포함된 것으로, 0이면 포함되지 않은 것으로 간주한다.
• 시간 복잡도: 모든 연산이 비트 연산 한 번으로 끝나므로 O(1)이다. 300만 건의 연산도 순식간에 처리 가능하다.

 

3. 코드 구현 (정답)

#include <iostream>
#include <string>

using namespace std;

int main() {
    // 입출력 최적화
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    int bit = 0; // 집합을 나타낼 비트마스크 변수

    for (int i = 0; i < n; i++) {
        string order;
        cin >> order;

        if (order == "add") {
            int num;
            cin >> num;
            // num번째 비트를 1로 만듦 (OR 연산)
            bit |= (1 << num);
        }
        else if (order == "remove") {
            int num;
            cin >> num;
            // num번째 비트를 0으로 만듦 (NOT 후 AND 연산)
            bit &= ~(1 << num);
        }
        else if (order == "check") {
            int num;
            cin >> num;
            // num번째 비트가 서 있는지 확인
            if (bit & (1 << num)) cout << 1 << "\n";
            else cout << 0 << "\n";
        }
        else if (order == "toggle") {
            int num;
            cin >> num;
            // num번째 비트를 반전시킴 (XOR 연산)
            bit ^= (1 << num);
        }
        else if (order == "all") {
            // 모든 비트를 1로 만듦 (1부터 20까지)
            bit = (1 << 21) - 1;
        }
        else if (order == "empty") {
            // 모든 비트를 0으로 만듦
            bit = 0;
        }
    }

    return 0;
}

---

4. 배운 점 & 회고 (TIL) ✍️

비트마스킹은 단순히 '기술'이 아니라, 데이터를 바라보는 '관점'의 전환임을 배웠다.

① 비트 연산의 마법

비트 연산자를 활용하면 집합 연산을 하드웨어 수준에서 처리할 수 있어 매우 빠르다.

• 1 << num: 숫자 1을 num만큼 왼쪽으로 밀어서 특정 위치만 1인 필터를 만든다.
• | (OR): 특정 원소 추가.
• & ~ (AND NOT): 특정 원소 삭제.
• ^ (XOR): 특정 원소가 있으면 삭제, 없으면 추가 (Toggle).
• & (AND): 특정 원소 존재 여부 확인.

② 정수형 변수의 효율성

int 타입은 보통 4바이트(32비트)이다. 문제에서 원소 범위가 1~20이었기 때문에 int 변수 하나만으로도 충분히 모든 상태를 표현할 수 있었다. 만약 범위가 64까지였다면 long long을 사용했을 것이다. 자료구조를 사용하는 것보다 메모리 사용량이 극적으로 줄어든다는 점이 놀랍다.

③ 'All' 연산의 최적화

all 연산 시 반복문을 돌며 insert 하는 대신, 비트 연산 한 번으로 모든 비트를 1로 채울 수 있다. (1 << 21) - 1은 0번부터 20번 비트까지 모두 1로 채워진 값을 의미한다. (실제 원소는 1~20이므로 0번 비트는 무시된다.)

④ 요약

데이터의 개수가 적고(보통 30개 이하), 존재 여부(True/False)만 관리하면 되는 상황이라면 복잡한 set이나 배열 대신 비트마스킹이 정답이다. O(1)의 속도와 극도의 메모리 효율성을 동시에 챙길 수 있는 아주 강력한 무기이다.