조건문 없이 깔끔하게, 자바 비트마스킹으로 문제 해결하는 법 (사용 유형 정리)

비트마스킹 기본 연산

1.1 특정 비트 확인 (Check)

boolean isSet = (mask & (1 << i)) != 0;

• `1 << i`는 1을 i만큼 왼쪽으로 이동해 i번째 비트를 의미한다.
• `&` 연산을 통해 i번째 비트가 1인지 0인지 확인 가능.

1.2 특정 비트 세팅 (Set)

mask |= (1 << i);

• i번째 비트를 1로 설정한다.

1.3 특정 비트 해제 (Clear)

mask &= ~(1 << i);

• i번째 비트를 0으로 만든다.

1.4 특정 비트 뒤집기 (Toggle)

mask ^= (1 << i);

• i번째 비트를 1이면 0, 0이면 1로 바꾼다.

 

 

/2 대신 >> 1, *2 대신 << 1

• `/2` 연산은 `>> 1`로 대체 가능
• `*2` 연산은 `<< 1`로 대체 가능
• 컴파일러가 대부분 최적화하므로 큰 체감은 없을 수 있으나, 간단한 비트 연산을 직접 사용하면 의도를 더 명확히 드러낼 수 있음.

 

 

방문 배열(visited) 대체

 

개념

• 기존에는 boolean[] visited를 사용해 특정 노드가 방문되었는지 추적한다.
• N이 15 이하라면 int visitedMask로 방문 상태를 표현할 수 있다.
• i번째 노드를 방문하면 visitedMask |= (1 << i)로 1비트를 설정한다.
• 이후 (visitedMask & (1 << i)) == 0이면 아직 방문하지 않은 상태다.

void dfs(int current, int visitedMask) {
    // 현재 노드를 방문 표시
    visitedMask |= (1 << current);

    // 다음 노드들 탐색
    for (int next = 0; next < N; next++) {
        // 방문 여부 확인
        if ((visitedMask & (1 << next)) == 0) {
            dfs(next, visitedMask);
        }
    }
}

• visitedMask 하나로 모든 노드의 방문 상태를 관리한다.
• 재귀호출 시 새로운 visitedMask값으로 다음 노드를 방문한다.

성능과 단순성

• 메모리: N이 작을 때 비트로 방문 상태를 저장하면 배열보다 공간을 절약한다.
• 연산: 비트 연산은 빠르고 간단하다.
• 가독성: 작은 N 범위에서는 비트마스킹이 더 간결하고 직관적일 수 있다.

 

 

모든 부분집합 순회하기

 

개념

• 어떤 집합의 부분집합을 모두 방문하고 싶을 때, 비트마스킹을 이용하면 효율적으로 순회 가능하다.
• 예를 들어, mask = (1 << N) - 1은 0부터 N-1까지 비트가 전부 1인 상태(즉, 모든 원소를 포함하는 부분집합)를 의미한다.

int mask = (1 << N) - 1;
for (int subset = mask; subset > 0; subset = (subset - 1) & mask) {
    // subset은 mask의 부분집합 중 하나
    // 필요한 로직 처리
}

• (subset - 1) & mask는 subset 바로 이전 부분집합을 추출하는 핵심 기법이다.
• 공집합까지 포함하려면 subset >= 0 조건으로 변경하면 된다.

성능과 단순성

• 부분집합의 개수는 2^N개이며, 위 기법은 해당 부분집합들을 빠짐없이 순회한다.
• 부분집합을 직접 만들기보다 비트마스크로 표현하면 구현이 단순해진다.

 

조합(Combination) 생성하기

 

개념

• N개 중 어떤 원소를 고를지 비트(0 또는 1)로 표현하면 모든 조합을 손쉽게 열거할 수 있다.
• 0번째 비트가 1이면 0번째 원소를 포함한다는 뜻이다.

int N = 4;
for (int bit = 0; bit < (1 << N); bit++) {
    List<Integer> subset = new ArrayList<>();
    for (int i = 0; i < N; i++) {
        if ((bit & (1 << i)) != 0) {
            subset.add(i);
        }
    }
    System.out.println(subset);
}

• bit가 0일 때는 공집합, (1 << N) - 1일 때는 전체 집합이 된다.
• 각 비트가 켜져 있는지 확인해 선택된 원소를 수집하면 된다.

성능과 단순성

• 2^N 번 반복하지만, N이 작으면 충분히 빠르다.
• 백트래킹보다 코드가 짧고 간단할 수 있다.

 

 

 간단한 예시: 부분수열 합 구하기

 

개념

• 어떤 배열 arr의 모든 부분수열 합을 구하고 싶다면, 비트마스킹을 이용해 부분집합을 표현할 수 있다.
• 각 부분집합에 대응하는 bit값을 순회하면서 해당하는 요소를 더한다.

public static void main(String[] args) {
    int[] arr = {1, 2, 3};
    List<Integer> sums = new ArrayList<>();
    int N = arr.length;

    for (int bit = 0; bit < (1 << N); bit++) {
        int sum = 0;
        for (int i = 0; i < N; i++) {
            if ((bit & (1 << i)) != 0) {
                sum += arr[i];
            }
        }
        sums.add(sum);
    }

    System.out.println("부분수열 합 리스트: " + sums);
}

 

• bit에 따라 어떤 원소를 포함할지 결정한다.
• 모든 부분수열 합을 쉽게 구할 수 있다.

성능과 단순성

• 시간 복잡도: O(N * 2^N)
• N이 15 이하라면 2^15(=32768) 안에서 문제없이 동작한다.
• 더 큰 N에서는 비트마스킹 대신 분할정복(Meet in the Middle) 등의 방식도 고려 가능.

비트마스킹? 백트래킹? 

1. 비트마스킹
   • 장점: 메모리 사용 감소, 빠른 연산, 간결한 코드
   • 단점: N이 커지면(보통 20 이상) 2^N 연산이 부담
   • 적절 사례: N ≤ 15, 방문 상태 관리, 부분집합/조합/부분수열 문제
2. 백트래킹
   • 장점: 직관적, 가지치기(pruning) 로직 추가 용이
   • 단점: (가지치기가 없으면) 같은 2^N 복잡도를 갖고 코드가 길어질 수 있음
   • 적절 사례: N이 커서 일부 가지치기가 필요한 경우, 상태에 따라 로직이 복잡해지는 경우

결과적으로 N이 작다면, 비트마스킹이 더 단순하면서도 성능이 우수하다.

만약 N이 커서 2^N이 너무 크다면, 문제 특성에 맞춰 백트래킹 + 가지치기를 병행하거나 Meet in the Middle 등의 전략이 필요해진다.

 

 

실전 + 야구 경기 비트 마스킹으로 묘사

 

우리가 흔히 아는 야구경기를 생각해보면, 아웃 카운트 3개가 쌓이면 공수가 바뀌고 그 외에 1루타 부터 홈런까지 주자가 1칸~4칸을 움직이는 것을 알수 있다. 

이를 단순하게 구현을 해보면 어쩔수 없이 많은 조건문으로 이를 처리해야하는데

static int simulateGame(int[] curOrder) {
        int score = 0;
        int batterIndex = 0;

        for (int i = 0; i < N; i++) {
            int outCount = 0;
            boolean base1 = false;
            boolean base2 = false;
            boolean base3 = false;

            while (outCount < 3) {
                int batter = curOrder[batterIndex];
                int result = game[i][batter];

                if (result == 0) {
                    outCount++;
                } else {
                    if (result == 1) {
                        if (base3) {
                            score++;
                            base3 = false;
                        }
                        if (base2) {
                            base3 = true;
                            base2 = false;
                        }
                        if (base1) {
                            base2 = true;
                            base1 = false;
                        }
                        base1 = true;
                    } else if (result == 2) {
                        if (base3) {
                            score++;
                            base3 = false;
                        }
                        if (base2) {
                            score++;
                            base2 = false;
                        }
                        if (base1) {
                            base3 = true;
                            base1 = false;
                        }
                        base2 = true;
                    } else if (result == 3) {
                        if (base3) {
                            score++;
                            base3 = false;
                        }
                        if (base2) {
                            score++;
                            base2 = false;
                        }
                        if (base1) {
                            score++;
                            base1 = false;
                        }
                        base3 = true;
                    } else if (result == 4) {
                        if (base3) {
                            score++;
                            base3 = false;
                        }
                        if (base2) {
                            score++;
                            base2 = false;
                        }
                        if (base1) {
                            score++;
                            base1 = false;
                        }
                        score++;
                    }
                }

                batterIndex = (batterIndex + 1) % 9;
            }
        }
        return score;
    }
}

위의 코드는 베이스 3개를 base1, base2, base3 같은 불리언 변수를 따로 두고 다양한 조건문으로 처리했지만,
비트 마스크를 활용한다면 단 하나의 정수(baseState)에 주자 상태를 압축해 둔 뒤 비트 연산으로 이동과 득점을 계산한다.

 

 

비트 마스크로 나타내어 보면 아래와 같다.

static int simulateGame(int[] curOrder) {
    int score = 0;
    int batterIndex = 0;

    for (int i = 0; i < N; i++) {
        int outCount = 0;
        int baseState = 0b000; // 1루, 2루, 3루 상태를 비트로 표현

        while (outCount < 3) {
            int batter = curOrder[batterIndex];
            int result = game[i][batter]; // 0: 아웃, 1~4: 진루

            if (result == 0) {
                outCount++;
            } else {
                // 1) 기존 주자들을 result만큼 이동
                baseState <<= result;

                // 2) 새로 타석에 들어선 타자가 result칸(루) 진루하는 것 처리
                //    예: 싱글(1루타)이면 baseState |= 0b001
                //        더블(2루타)이면 baseState |= 0b010
                baseState |= (1 << (result - 1));

                // 3) 홈에 들어온 주자(3루 초과로 넘어간 주자) 수를 점수로 추가
                //    0b1111000은 3루(비트 2)보다 높은 비트를 모두 체크하기 위한 마스크
                score += Integer.bitCount(baseState & 0b1111000);

                // 4) 3루 이하의 주자 상태만 남기고, 나머지는 제거(홈인으로 처리됨)
                baseState &= 0b111; // 하위 3비트만 유지
            }

            // 다음 타자로 이동
            batterIndex = (batterIndex + 1) % 9;
        }
    }
    return score;
}

1. baseState의 비트 구성

• baseState는 하위 3비트를 사용해 1·2·3루에 주자가 있는지 표현한다.
  • 하위 1비트(0번): 1루 주자 여부
  • 다음 1비트(1번): 2루 주자 여부
  • 다음 1비트(2번): 3루 주자 여부
• 예를 들어, baseState = 0b101(5)는 1루와 3루에 주자가 있다는 뜻이다.

2. 주자 이동 ( baseState <<= result )

• result가 1(싱글)이면 baseState를 왼쪽으로 1비트 이동
  • 예: 0b101(1,3루 주자) → 0b1010 (2,4루 주자)
  • 실제로 4루는 곧 득점(홈) 위치에 해당되므로, 이후에 점수 계산에서 반영한다.
• result가 2(더블)면 왼쪽으로 2비트, 3(트리플)이면 3비트, 4(홈런)이면 4비트 이동한다.

3. 새 주자(타자) 진루 ( baseState |= (1 << (result - 1)) )

• 타자가 1루타면 baseState |= 1 << 0 (즉, 0b001 추가)
• 타자가 2루타면 baseState |= 1 << 1 (즉, 0b010 추가)
• 홈런(4루타)일 때는 1 << 3을 추가하므로, 곧바로 홈으로 들어가는 위치(3보다 높은 비트)에 해당
  • 이는 결국 득점 처리에서 점수가 추가된다.

4. 득점 처리 ( score += Integer.bitCount(baseState & 0b1111000) )

• 0b1111000(이진수로 0111_1000)은 3루 비트(2번)보다 높은 비트를 확인하기 위한 마스크다.
• 왼쪽 시프트로 인해 3루를 초과한 모든 주자(즉, 홈에 들어온 주자)는 3번 비트 이상에 위치하게 된다.
• Integer.bitCount()를 사용해 해당 영역에 몇 명의 주자가 있는지를 세어 점수에 더해준다.

5. 3루 이하 상태만 남기기 ( baseState &= 0b111 )

• 3루(비트 2) 이하만 유지하고, 홈을 밟은 주자(비트 3 이상)는 날려버린다.
• 홈을 밟은 주자는 이미 득점 처리되었으므로 baseState에서 제거해도 무방하다.

 

 

결론

• 비트마스킹은 야구 주자 이동처럼 상태 변화가 규칙적이면서 간단한(여기서는 최대 3루까지) 문제에 탁월하다.
• 불리언 변수를 여러 개 두어 “1루 주자가 있을 때 → 2루로 옮김” 같은 if문을 일일이 쓰기보다,
  왼쪽 시프트 + 마스킹으로 한 번에 처리하므로 코드가 짧고 명료해진다.
• 또한 홈에 들어온 주자를 빠르게 계산할 수 있어, 숫자 조작 하나로 득점을 기록하기 쉬워진다.

이처럼 단순한 로직을 비트로 관리하면, 짧고 효율적인 코드로 구현이 가능해진다.