비트마스킹

비트마스킹

이번 포스트에서 정리할 주제는 비트마스킹입니다. 비트마스킹은 알고리즘 문제에서 자주 등장하는 기법 중 하나로 이진수(bit)를 활용해 여러 개의 상태를 한 개의 정수로 표현할 수 있도록 도와주며, 공간 절약과 연산 최적화 측면에서 매우 유용합니다.

 

예시는 다음과 같습니다.

• n = 5 → 101
  → 0, 2번 인덱스가 켜져 있다라는 의미로 해석이 가능합니다.

비트마스킹 활용 사례

• 부분 집합을 효율적으로 순회할 때
• 중복 방문을 피하는 DP/DFS에서 방문 여부를 저장할 때
• 상태를 배열 대신 정수 하나로 표현하고 싶을 때
• 메모리/성능 최적화가 필요할 때

기본 연산 정리표

연산 목적	표현식	설명	예제 입력 / 결과 예시
i번째 비트 켜기 (Set)	S = S | (1 << i)	i번째 자리를 1로 설정	S = 0; i = 2; → S = 00000100 (4)
i번째 비트 끄기 (Unset)	S = S & ~(1 << i)	i번째 자리를 0으로 설정	S = 15; i = 2; → S = 00001011 (11)
i번째 비트 반전 (Toggle)	S = S ^ (1 << i)	i번째 자리가 1이면 0으로, 0이면 1로 반전	S = 4; i = 2; → S = 00000000 (0)
i번째 비트 확인 (Check)	(S & (1 << i)) != 0	i번째 자리가 1이면 true, 아니면 false	S = 5; i = 0; → true (101)
전체 비트 켜기	S = (1 << n) - 1	0부터 n-1번째 비트를 모두 1로 설정	n = 4; → S = 00001111 (15)
비트 전부 끄기	S = 0	모든 비트를 0으로 초기화	S = 10010101; → S = 00000000
모든 비트가 켜졌는지 확인	S == (1 << n) - 1	n개의 비트가 모두 켜졌는지 체크	S = 111111; n = 6; → true

예시 문제

백준 - 11723번 : 집합

 

마지막으로 예시 문제를 풀이해보겠습니다. 해당 문제는 비트마스킹을 활용하지 않고도 충분히 풀이가 가능하지만, 비트마스킹을 활용하여 문제를 풀이해보겠습니다.

package 비트마스킹;

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

public class 백준_11723 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int M = Integer.parseInt(br.readLine());
        int S = 0; // 비트마스킹용 집합 변수 (0으로 초기화)

        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            String command = st.nextToken();

            switch (command) {
                case "add": {
                    int value = Integer.parseInt(st.nextToken());
                    // value번째 비트를 1로 만든다 (켜기)
                    S = S | (1 << (value - 1));
                    break;
                }
                case "remove": {
                    int value = Integer.parseInt(st.nextToken());
                    // value번째 비트를 0으로 만든다 (끄기)
                    S = S & ~(1 << (value - 1));
                    break;
                }
                case "check": {
                    int value = Integer.parseInt(st.nextToken());
                    // value번째 비트가 1이면 1 출력, 아니면 0 출력
                    if ((S & (1 << (value - 1))) > 0) {
                        sb.append(1).append("\n");
                    } else {
                        sb.append(0).append("\n");
                    }
                    break;
                }
                case "toggle": {
                    int value = Integer.parseInt(st.nextToken());
                    // value번째 비트를 반전시킨다 (1이면 0, 0이면 1)
                    S = S ^ (1 << (value - 1));
                    break;
                }
                case "all": {
                    // 1~20까지 비트를 모두 1로 설정
                    // 21번째 비트까지 포함해서 2^21 - 1
                    S = (1 << 21) - 1;
                    break;
                }
                case "empty": {
                    // 모든 비트를 0으로 초기화 (집합 비우기)
                    S = 0;
                    break;
                }
            }
        }

        System.out.println(sb);
    }
}