[Coding Test] Algorithm(2)

1. 비트 마스킹

컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다. 이와 같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크라고 한다.

비트 마스크를 이용하면 더 빠른 수행 시간, 더 간결한 코드, 더 적은 메모리 사용이라는 효과를 얻을 수 있다.

비트 연산자

비트 마스킹은 기본적으로 비트를 다뤄야 하므로, 비트 연산자를 알아야 한다.

집합의 표현

비트 마스크를 이용하면 집합을 쉽게 표현할 수 있다. 또, 집합에 원소를 추가, 삭제하는 등 다양한 연산을 굉장히 빠르게 수행할 수 있다.

만약 원소의 개수가 N인 집합이 있다고 하면, 각각의 원소는 0번부터 (N-1)번 까지 번호를 부여하고, 번호에 해당하는 비트가 1이면 원소가 포함, 0이면 원소가 불포함이라고 한다면 집합을 비트를 이용해 표현할 수 있다.

예를 들어, {A, B, C, D, E, F, G}집합이 있다고 하자.
총 7개의 원소가 존재하므로 우리는 7개의 비트로 이 집합을 표현할 수 있다. 즉, 각 원소마다 비트를 하나씩 대응시켜서 원소가 존재한다면 1, 존재하지 않다면 0으로 표현해본다.
예를 들어, {A}라는 부분집합은 64=10000000(2)로 표현하고, {C, F}는 18=0010010(2)로 표현할 것이다.

원소 추가

cur = cur | (1<<p)

1<<p를 통해서 p번 비트만 1, 나머지 비트는 0인 값을 만들고 |연산을 진행하다면 cur의 p번 비트는 1로 바뀌게 되고, 나머지 비트는 원래 상태를 유지하게 된다.

원소 삭제

cur = cur & ~(1<<p);

1<<p를 통해서 p번 비트만 1, 나머지 비트는 0으로 만든다. 그 후, ~연산을 통해 p번비트만 0, 나머지 비트는 1로 만들고 & 연산을 진행한다면 p번 비트만 0으로 바뀌고 나머지는 현재 상태 cur과 동일하게 유지할 수 있다.

원소 토글

cur = cur^(1<<p);

1<<p를 통해서 p번 비트만 1, 나머지 비트는 0으로 만든다. cur의 나머지 비트들은 0과 XOR 연산을 진행하므로 0이면 0, 1이면 1로 현재 상태를 유지하고, p번 비트는 1과 XOP 연산을 진행하므로 1이면 0, 0이면 1로 토글이 된다.

집합 연산 (합집합)

a | b;		// a와 b의 합집합
a & b;		// a와 b의 교집합
a & ~b;		// a에서 b를 뺸 차집합
a ^ b; 		// a와 b 중 하나만 포함된 원소들의 집합

집합의 크기 구하기

int bitCount(int x) {
	if(x==0) return 0;
    else x%2 + bitCount(x/2);
}

x%2를 하면 마지막 비트를 얻게 되고, x/2를 하게 되면 마지막 비트를 삭제할 수 있다. 따라서, 모든 비트를 재귀적으로 순회할 수 있다.

모든 부분 집합 순회하기

for (int subset = set; subset >0; subset = (subset - 1) & set) {}

예를 들어, {A, B, D}를 포함한 집합을 생각해보자.
모든 부분 집합은 공집하을 제외하고 {A}, {B}, {D}, {A,B}, {A,D}, {B,D}, {A,B,D}가 존재한다.
비트로 표현하면 다음과 같다.

위에서 구현한 코드를 한번 따라가면 다음와 같다. set = 1101(2) = {A,B,D}이다.

for문을 통해 모든 부분 집합을 다 순회하는 것을 확인할 수 있다.

2. 실전 문제

막대기 (백준 1094)

import java.io.*;

public class P1094_막대기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int X = Integer.parseInt(br.readLine());
        int count = 0;

        for (int i = 0; i < 7; i++) {
            if ((X & (1 << i)) > 0) count++;
        }

        /* 비트 마스킹 X
        int stick = 64;
        while (X > 0) {
            if (stick > X) stick /=2;
            else {
                X -= stick;
                count++;
            }
        }
         */

        bw.write(count + "");
        bw.flush();
        bw.close();
        br.close();
    }
}

집합 (백준 11723)

import java.io.*;
import java.util.StringTokenizer;

public class P11723_집합 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int S = 0;
        int M = Integer.parseInt(br.readLine());

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();

            if (str.equals("all")) S = (1 << 21) - 1;
            else if (str.equals("empty")) S = 0;
            else {
                int num = Integer.parseInt(st.nextToken());
                switch (str) {
                    case "add":
                        S = S | (1 << num);
                        break;
                    case "remove":
                        S = S & ~(1 << num);
                        break;
                    case "check":
                        bw.write(((S & (1 << num)) != 0 ? 1 : 0) + "\n");
                        break;
                    case "toggle":
                        S = S ^ (1 << num);
                        break;
                }
            }
        }
        bw.close();
    }
}