[백준] 11723번 : 집합 [C/C++]

#문제

11723번: 집합

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

11723번: 집합

 

---

#접근방법

비스마스크 기법을 사용하는 문제이다. 하지만 범위가 1~20 이라서 그냥 배열로 풀어도 메모리 제한은 걸리지 않는다.

반응형

---

#풀이

#include <stdio.h>
#include <string.h>

char a[10];

int main(){
    int M,x;
    int s = 0;

    scanf("%d",&M);

    while(M--){
        scanf("%s",a);
        if(strcmp(a,"all")==0){
            s = (1<<20)-1;
            continue;
        }
        else if(strcmp(a,"empty")==0){
            s = 0;
            continue;
        }

        scanf("%d",&x);

        int k = 1<<(x-1);

        if(strcmp(a,"add")==0){
            s |= k;
        }
        else if(strcmp(a,"remove")==0){
            s &= ~k;
        }
        else if(strcmp(a,"check")==0){
            printf("%d\n",(s&k)>0);
        }
        else if(strcmp(a,"toggle")==0){
            s ^= k;
        }
    }

    return 0;
}

 

메모리 제한이 4MB 밖에 안되지만 범위가 1~20이라서 크기가 20인 배열을 잡고 풀어도 풀 수 있는 문제이다.

 

20크기의 배열을 만들고 all, empty 명령이 들어오면 반복문을 통해 배열 전체를 1 또는 0으로 초기화 해주고 add, remove, toggle 명령은 해당 배열을 1또는 0으로 만들어 주면 되고 check 명령이 들어오면 해당 배열을 출력해주면 된다.

 

하지만 이번 풀이는 비트마스크를 이용하여 풀어보았다.

 

비트마스크를 사용하면 코드가 간결해지고 메모리를 줄일 수 있다는 장점이 있다.

 

배열 풀이와 비교를 하자면 배열 풀이는 bool 자료형의 20크기 배열을 사용한다면 1byte * 20 = 20byte의 메모리를 사용한다. 하지만 비트마스크를 사용하면 20bit를 저장할 수 있는 int 자료형을 사용한다고 하면 4byte의 메모리를 사용하므로 메모리 측면에서 5배의 이득을 볼 수 있다.

 

그리고 배열 풀이에서 all, empty 명령은 반복문으로 20번의 시간이 소요되지만 비트마스크는 한번의 비트연산으로 시간 측면에서도 큰 이득을 볼 수 있다.

 

그러면 이제 위의 풀이를 설명하겠다.

 

M을 입력받고 M만큼 반복문을 실행시켜준다.

 

char 자료형인 a로 all, remove같은 명령을 입력받고 strcmp 함수로 명령들을 구분해준다.

 

all 명령은 s = (1<<20)-1으로 20bit의 공간을 1로 채워준다.

 

1<<20의 의미는 1을 왼쪽 비트로 얼마나 옮기냐의 의미이다.

 

컴퓨터의 숫자들은 자세하게 들어가면 전부 0과 1로 이진법으로 이루어져 있다.

 

예를들어 8은 1000(2) 이고, 5는 0101(2)이다.

 

4bit의 공간을 전부 1로 만들려면 (1<<4)-1을 하면 된다.

 

먼저 1<<4을 하면 10000(2) 즉 16이 되고 1을 빼면 1111(2) 즉 15가 된다. 그러면 4bit의 공간을 전부 1로 만들 수 있다.

 

따라서 all과 empty명령은 하나의 비트 연산으로 처리를 할 수 있는 것이다.

 

add, remove, check, toggle 명령에 앞서 코드를 간결하게 하기 위해 k변수에 1<<(x-1)를 저장해주었다. k의 의미는 해당 bit의 위치이다.

 

add 명령은 s |= k 로 처리해주었는데 s |= k 는 s = s | k와 의미가 같다. s | k에서 |의 의미는 s와 k의 각각의 비트가 [1,1], [1,0], [0,1] 이면 1이고 [0,0] 이면 0으로 바꿔주는 것이다. 따라서 s의 k위치의 bit에 0이던 1이던 1을 만든다는 의미가 된다.

 

remove 명령은 s &= ~k로 처리해 주었다. ~k는 0은 1로 1은 0으로 전부 바꾸는 연산이다. 예를들어 001001(2)은 110110(2)으로 바꿔진다. &는 [1,1]만 1로되고 [1,0], [0,1], [0,0]은 전부 0으로 된다. 따라서 s의 k위치에 있는 bit가 0이던 1이던 0을 만들고 다른 비트들은 전부 그대로가 된다.

 

toggle 명령은 s ^= k 로 처리해 주었다. ^는 서로 다르면 1 같으면 0이다. 따라서 1이면 0으로 바뀌고 0이면 1로 바뀌게 된다.

 

check 명령이 들어오면 (s&k)>0로 해당 비트의 AND연산으로 양수값이 나오면 1을 출력하고 아니면 0을 출력한다.

---

#성능

---

#정리

비트마스크 알고리즘이 무엇인지 아는 것,

 

적절한 비트 연산을 사용할 수 있으면 풀 수 있는 문제였다.