Plite
전자오락 공방
Plite
전체 방문자
오늘
어제
  • 분류 전체보기 (274)
    • 프로젝트 (18)
      • 완성 프로젝트 (3)
      • 프로젝트 진행 내역 (15)
    • 공부 및 정리 (241)
      • 백준 코드 (222)
      • C++ (8)
      • DirectX (2)
      • Unreal Engine (6)
      • 프로그래밍 패턴 (3)
    • 기타 (12)
      • 기타 주저리 (10)
    • 게임과 취미 (1)
    • 대문 (1)

블로그 메뉴

  • 홈
  • 프로젝트
  • 취미, 일상
  • 백준 프로필

공지사항

  • [Read Me]
  • 제 블로그에 방문하신 것을 환영합니다.

인기 글

태그

  • 누적합
  • 백트래킹
  • 큐
  • 조합론
  • 정렬
  • 트리
  • UC++
  • 우선순위큐
  • KMP
  • 브루트포스
  • 정수론
  • 세그먼트 트리
  • 기하
  • 투포인터
  • 위상 정렬
  • 수학
  • 최소 스패닝 트리
  • 동적계획법
  • 유니온 파인드
  • 구현
  • 백준
  • SCC
  • 그래프
  • 스택
  • C++
  • 분할정복
  • 이분탐색
  • 문자열
  • 트라이
  • LCA

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Plite

전자오락 공방

[C++]백준 - 11723번 문제
공부 및 정리/백준 코드

[C++]백준 - 11723번 문제

2021. 9. 25. 16:02

11723번: 집합 (acmicpc.net)

 

11723번: 집합

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

www.acmicpc.net

 

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 연산이 주어질때마다, 결과를 출력한다.

 


 

생각해 볼 점


메모리제한이 꼴랑 4MB 밖에 안됩니다. 배열 등을 이용하면 순식간에 메모리 초과를 보게 될 것 같습니다.

 

따라서, 이 문제는 비트마스크 문제입니다.

 

비트마스크 (BitMask) 알고리즘 (rebro.kr)

 

비트마스크 (BitMask) 알고리즘

[목차] 1. 비트마스크(BitMask)란? 2. 비트마스크의 장점 3. 비트 연산자 4. 비트마스크를 이용한 집합 구현 5. 비트필드(bitfield)를 이용한 DP 6. 비트마스크 예제 문제 * 종만북에 잘 설명되어 있어 기본

rebro.kr

비트마스크를 왜 이용하는지, 어떤 장점이 있는지에 대하여는 위의 링크에서 잘 설명해주고 있습니다.

 

 

우선, 이진수 비트를 이용해서, 해당 자리에 X가 있는 지 없는 지를 나타낼 것입니다.

 

예시)

처음 상태 : 0000

 

add 3 -> 0100

add 2 -> 0110

remove 3 -> 0010

all -> 1111

 

 

1 ~ 20자리 까지 사용하므로, int의 범위 내로 감당 가능합니다.

 

비트를 저장한 int 하나를 만든 후, 비트 연산을 이용해 명령어를 구현하고, 실행하면 됩니다.

 

 

코드


#include <iostream>
#include <string>
using namespace std;

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int M;
    cin >> M;
    int bit = 0;
    for(int i = 0; i < M; i++)
    {
        string command;
        cin >> command;
        
        switch(command[1])
        {
            //add
            case 'd':
            {
                int x;
                cin >> x;
                bit |= 1 << x-1;
                break;
            }
            //remove
            case 'e':
            {
                int x;
                cin >> x;
                bit &= ~(1 << x-1);
                break;
            }
            //check
            case 'h':
            {
                int x;
                cin >> x;
                bool is_it = bit & (1 << x - 1);
                cout << is_it << "\n";
                break;
            }
            //toggle
            case 'o':
                int x;
                cin >> x;
                bit ^= (1 << x-1);
                break;
            //all
            case 'l':
                bit = (1 << 20) -1;
                break;
            //empty
            case 'm':
                bit &= 0;
                break;
        }
    }
	return 0;
}

 

그 외


 

저작자표시 (새창열림)

'공부 및 정리 > 백준 코드' 카테고리의 다른 글

[C++]백준 - 1717번 문제  (0) 2021.09.26
[C++]백준 - 6549번 문제  (0) 2021.09.26
[C++]백준 - 4803번 문제  (0) 2021.09.25
[C++]백준 - 5639번 문제  (0) 2021.09.24
[C++]백준 - 2263번 문제  (0) 2021.09.24
    '공부 및 정리/백준 코드' 카테고리의 다른 글
    • [C++]백준 - 1717번 문제
    • [C++]백준 - 6549번 문제
    • [C++]백준 - 4803번 문제
    • [C++]백준 - 5639번 문제
    Plite
    Plite
    개발 일지, 게임 이야기 등을 적어두는 공간입니다.

    티스토리툴바