[공부] 백준 11723 집합 C++

📝 문제

• 백준 11723 집합
  • https://www.acmicpc.net/problem/11723

---

🔍 문제 상황

---

💡 해결 방법 / 접근 방식

• 우선, 비어있는 공집합에 m번 동안 주어지는 연산(add, remove, check, toggle, all, empty)을 수행하는 문제입니다.
• 해당 문제는 비트 마스킹 문제로써 비트 연산이 필요합니다.

비트연산(Bitwise Operation)

연산자	이름	의미	예시 (a = 0101, b = 1100)
&	AND	둘 다 1일 때만 1	a & b → 0100
` | `	OR	하나라도 1이면 1
^	XOR	다르면 1	a ^ b → 1001
~	NOT	0은 1로, 1은 0으로 반전	~a → 반전된 a
<<	왼쪽 시프트	비트를 왼쪽으로 밀기	a << 1 → 1010
>>	오른쪽 시프트	비트를 오른쪽으로 밀기	a >> 1 → 0010

• 출처: https://hagisilecoding.tistory.com/54
• 출처: https://velog.io/@ggh-png/C-%EB%B9%84%ED%8A%B8-%EB%A7%88%EC%8A%A4%ED%82%B9

비트 마스킹(Bitwise Masking)

• 비트 하나하나를 켜고(1) 끄고(0) 체크하는 것

• 공집합 만들기

  int s = 0;
  

• s에 원소 추가

  s |= (1<<3);
  // 1을 3간 왼쪽으로 시프트(이동) 후 OR 연산 후 s에 대입
  // 1 > 10 > 100 > 1000
  

• s에 원소 삭제

  s &= ~(1<<3);
  // 1000 -> 0111로 변경 ("~"가 있기 때문) 후 AND 연산 후 s에 대입
  

• 원소 존재 여부 파악

  if(s & (1<<3){
    cout << "존재" << "\n";
  }
  

• s에 모든 원소 채우기

  s |= (1<<8) - 1;
  // 10000 0000 - 1 = 1111 1111 식으로 채우기 가능
  

• XOR

  s ^= (1<<3);
  // 3번째에 대한 XOR 연산 후 s에 대입
  

접근 방식

• 위에서 파악한 비트 마스킹에 따라 각각의 입력 받은 문자열에 따른 연산을 진행합니다.
• 문자열 뒤의 숫자(x)는 후에 입력 받아도 되기에 문자열로 입력 받은 후, 입력을 받습니다.
• 주의할 점은 비트 연산과 일반 정수 연산은 다르기에 if (s == x) 와 같이 같은 값이 있는지 비교한다고 사용한다면 안됩니다.
  • 이 조건은 s라는 전체 비트 상태와 x라는 단일 숫자가 완전히 같을 때만 참이 됩니다.
  • 하지만 우리가 원하는 건 x번째 비트가 켜져 있는지만 확인하는 것 입니다.
    • s == x가 참인 경우

        s = 8;  // => 000...01000
        x = 8;  // => 000...01000
      
      

    • 문제에서 원하는 것

        // x번째 비트가 켜져있는지만 확인하고 싶다
        if (s & (1 << x)) // x번째 비트가 1이면 true
      
      

---

🛠️ 구현 코드

// 비트마스킹 문제 <- 비트 연산 필요

#include <iostream>
#include <string>

using namespace std;

int m, x;
string str;

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

    int s = 0; // 공집합
    cin >> m;

    for (int i = 0; i < m; ++i) {
        cin >> str;
        if (str == "add") {
            cin >> x;
            s |= (1 << x); // s집합에 원소를 추가
        } else if (str == "check") {
            cin >> x;
            if (s & (1 << x)) {
                // s에 x가 있으면
                cout << "1" << "\n";
            } else {
                // s에 x가 없으면
                cout << "0" << "\n";
            }
        } else if (str == "remove") {
            cin >> x;
            s &= ~(1 << x); // s집합에 원소를 삭제
        } else if (str == "toggle") {
            cin >> x;
            s ^= (1 << x); // xor, 0 -> 1, 1 -> 0
        } else if (str == "all") {
            s = (1 << 21) - 1; // s에 모든 원소 채우기(1~20)
        } else if (str == "empty") {
            s = 0; // 공집합 화 시키기 == (s = 0)
        }
    }
    return 0;
}

🧷 결론

• 배열을 사용해서 푸는 방법도 있지만, 비트 마스킹과 비트 연산을 사용해서 바로 푸는 방법도 있어서 이 방법을 시도해보았습니다.
• 비트 마스킹에 대해 설명이 잘 되어있는 블로그들이 있어서 이를 참고하면서 풀이를 진행하였더니 수월하게 풀어나갈 수 있었습니다.