[알고리즘] 배열을 쓰지말고 풀어봐 : 비트마스크

0과 1 대신, 위 아래?

비트 마스크 (Bitmask)란 무엇인가?

비트 마스크(Bitmask)는 비트 연산을 사용하여 데이터를 효율적으로 처리하고 조작하는 방법입니다. 특히, 원소의 개수가 적고 원소의 범위가 제한된 경우 매우 유용하게 사용됩니다. 비트 마스크는 메모리를 절약하고, 특정 연산을 빠르게 수행할 수 있는 장점이 있습니다. 막 주로 사용되는 알고리즘은 아니지만 분명히 알아둬야 하는 방법입니다.

비트 연산의 기초

비트 연산은 AND(&), OR(|), XOR(^), NOT(~) 및 시프트 연산(<<, >>) 등을 사용하여 이진 데이터를 조작합니다. 각 비트 연산은 다음과 같은 기능을 수행합니다:

• AND(&): 두 비트가 모두 1일 때 1, 그렇지 않으면 0.
• OR(|): 두 비트 중 하나라도 1일 때 1, 그렇지 않으면 0.
• XOR(^): 두 비트가 다를 때 1, 같을 때 0.
• NOT(~): 비트를 반전시킴.
• LEFT SHIFT(<<): 비트를 왼쪽으로 이동시킴.
• RIGHT SHIFT(>>): 비트를 오른쪽으로 이동시킴.

비트 마스크의 사용

비트 마스크는 특정 비트를 1로 설정하거나 확인하는 데 사용됩니다. 예를 들어, 1 << j는 숫자 1을 왼쪽으로 j 비트만큼 이동시키는 연산입니다. 이 연산은 다음과 같은 결과를 만듭니다: 

• 1 << 0은 0001 -> 1 (2^0)
• 1 << 1은 0010 -> 2 (2^1)
• 1 << 2은 0100 -> 4 (2^2)
• 1 << 3은 1000 -> 8 (2^3)

이를 통해 특정 비트를 설정하거나 확인할 수 있습니다. 보통 Board나 배열과 같은 자료를 확인하거나 설정할 때 주로 사용하며 밑의 예시를 보시면 더 도움이 될 것 같습니다.

---

비트 마스크를 이용한 문제 해결

문제: 백준 14391번 종이 조각

백준 14391번 문제는 종이 조각을 가로 또는 세로로 자른 후 각 조각의 숫자를 합하여 최대 합을 구하는 문제입니다. 비트 마스크를 사용하여 이 문제를 해결해보겠습니다. 이 문제는 처음 생각할 땐, 아예 시작조차 힘들었는데 코드를 보니 이해가되는 문제입니다.

접근 방법

1. 비트 마스크를 이용한 완전 탐색:
   • 각 칸을 가로로 자를지 세로로 자를지 결정해야 합니다.
   • 이를 위해 각 칸에 대해 비트를 사용하여 가로(0) 또는 세로(1)로 자르는 모든 가능한 경우를 탐색합니다.
2. 각 경우의 수에 대해 합 계산:
   • 각 비트 마스크에 대해 모든 가로 조각과 세로 조각의 합을 계산합니다.
   • 그 중 최대 값을 찾습니다.

구현 코드

아래는 Python으로 구현한 코드입니다:

n, m = map(int, input().split())
board = [input().strip() for _ in range(n)]

max_sum = 0

# 2^(n*m)가지 경우를 모두 검사
for bitmask in range(1 << (n * m)):
    total = 0

    # 가로 조각 합 계산
    for i in range(n):
        row_sum = 0
        for j in range(m):
            idx = i * m + j
            if bitmask & (1 << idx):
                # 현재 칸이 세로 조각이면 이전 가로 조각 합을 더하고 초기화
                total += row_sum
                row_sum = 0
            else:
                # 가로 조각인 경우 숫자를 가로로 이어붙임
                row_sum = row_sum * 10 + int(board[i][j])
        # 마지막 가로 조각 합 더하기
        total += row_sum

    # 세로 조각 합 계산
    for j in range(m):
        col_sum = 0
        for i in range(n):
            idx = i * m + j
            if bitmask & (1 << idx):
                # 현재 칸이 세로 조각인 경우 숫자를 세로로 이어붙임
                col_sum = col_sum * 10 + int(board[i][j])
            else:
                # 가로 조각이면 이전 세로 조각 합을 더하고 초기화
                total += col_sum
                col_sum = 0
        # 마지막 세로 조각 합 더하기
        total += col_sum

    # 최대 합 갱신
    max_sum = max(max_sum, total)

print(max_sum)

코드 설명

1. 입력 처리:
   • n과 m을 입력받고, board를 입력받습니다
2. 비트 마스크를 이용한 모든 경우 탐색:
   • 1 << (n * m)은 n * m개의 칸에 대해 모든 가로/세로 경우의 수를 나타냅니다. 여기서 머리가 뚫린 기분을 얻었습니다. 그냥 전체 board를 일렬로 세우고 0과 1으로 이루어질수 있는 모든 경우의 수를 만든 다음. 그 중에서 가장 큰 값을 찾아내면 되는 것입니다. 
3. 가로 조각 합 계산 & 세로 조각 합 계산 :
   • 각 행에 대해 비트 마스크를 검사하여 가로 혹은 세로 조각인지 확인합니다.
   • 가로 조각인 경우 숫자를 이어붙이고, 세로 혹은 가로 (위와 반대입니다.)조각인 경우 이전 가로 조각의 합을 총 합에 더합니다.
4. 최대 합 갱신:
   • 각 비트 마스크의 경우에 대해 계산된 합 중 최대 값을 갱신합니다.

성능

이 알고리즘은 시간 복잡도가 O(2^(n*m) * (n+m))로, n과 m이 작을 때(최대 4x4) 사용 가능합니다. 보통 시간 복잡도가 많기 때문에 소요시간과 n,m을 잘 확인할 필요가 있습니다.

결론

보통 비트 마스크 문제는 문제에서 티가 나는 경우가 많습니다. 그 전에 알려주기도 하는 경우도 있기에 이런 방법이 있다고 알아두시고 비트마스크로 풀어야한다면 그때 시도해보는 것이 현명한 방법이 아닐까 생각이 듭니다.

---

참고자료

1. 비트마스크를 이용한 주요 사용 예시 : https://lagooni.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EC%A2%85%EC%9D%B4-%EC%A1%B0%EA%B0%81-14391%EB%B2%88-Python-Bitmasking

[백준] 종이 조각 14391번 (Python) -Bitmasking