알면 도움되는 코딩 테스트 유형: 5) #Bitmask

비트마스크(Bitmask)란?

 

• 비트마스크는 컴퓨터 메모리의 이진수 표현을 활용하여 집합을 나타내는 방식입니다. 각 원소를 이진수의 한 자리로 대응시켜 해당 원소의 포함 여부를 나타냅니다. 따라서, 집합 연산을 비트 연산으로 처리할 수 있어 간결하고 빠른 알고리즘 구현이 가능합니다.
• 비트마스크를 사용하기 위해 알아야 할 주요 개념은 다음과 같습니다.

 

1. 이진수 표현: 숫자를 이진수로 변환하여 각 자릿수가 원소에 대응되도록 합니다.
2. AND(&), OR(|), XOR(^): 비트 연산자들을 활용하여 집합 연산(교집합, 합집합, 차집합 등)을 수행합니다.
3. 시프트(Shift): 왼쪽 시프트(<<), 오른쪽 시프트(>>) 연산자를 사용하여 비트를 이동시킵니다.
4. 부분집합 생성: 모든 부분집합을 생성하거나, 주어진 조건에 맞는 부분집합만 생성할 수 있습니다.

 

비트마스크 문제 접근 전략

 

• 코딩 테스트에서 비트마스크 문제는 집합 관련된 문제나 경우의 수 탐색 등 다양한 상황에서 활용됩니다.
• 문제를 해결하기 위해서는 다음과 같은 접근 방법을 사용합니다.

 

1. 주어진 문제가 비트마스크 관련 문제인지 확인합니다.
2. 필요한 데이터나 조건에 맞게 이진수 형태로 변환하여 저장합니다.
3. 필요한 집합 연산이 있다면 적절한 비트 연산자와 함께 사용합니다.
4. 경우의 수 탐색이 필요한 경우, 모든 부분집합 또는 조건에 맞는 부분집항만 생성하는 방식으로 접근합니다.
5. 결과값 계산이 필요한 경우, 해당하는 자릿수에 대응되는 값을 추출하거나 적절한 조작 후 결과값을 도출합니다.

 

2961번: 도영이가 만든 맛있는 음식

  문제  

 

• 도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.
• 지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.
• 시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.
• 재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.

 
  해결 방법  

 

• 이 문제는 주어진 재료들로 음식을 만들 때, 신맛과 쓴맛의 차이를 최소로 만드는 조합을 찾아내야 합니다. 각 재료별로 신맛과 쓴맛의 정도가 주어집니다.
• 먼저 가능한 모든 부분집합(재료 조합)에 대해 탐색합니다.
• 각 부분집합에 대해서 신맛(재료들의 곱)과 쓴맛(재료들의 합)의 차이를 계산합니다.
• 결과적으로 가장 작은 차이 값을 출력합니다.

import sys; input=sys.stdin.readline

N = int(input())
ingred = [list(map(int, input().split())) for _ in range(N)]
answer = float('inf')

for i in range(1, 1<<N):
    bitter, sour = 0, 1
    for j in range(N):
        if i & (1<<j):
            sour *= ingred[j][0]
            bitter += ingred[j][1]
    answer = min(answer, abs(sour-bitter))

print(answer)

 
 

1194번: 달이 차오른다, 가자.

  문제  
 

• 지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.
• 민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.
• 하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.
• 영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.
• 민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.

- 빈 칸: 언제나 이동할 수 있다. ('.')
- 벽: 절대 이동할 수 없다. ('#')
- 열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. ('a', 'b', 'c', 'd', 'e', 'f')
- 문: 대응하는 열쇠가 있을 때만 이동할 수 있다. ('A', 'B', 'C', 'D', 'E', 'F')
- 민식이의 현재 위치: 빈 곳이고, 민식이가 현재 서 있는 곳이다. ('0')

 

• 달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.
• 민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

 

  해결 방법  

 

• 이 문제는 BFS 알고리즘을 활용하여 풀 수 있습니다. 먼저, 각 위치별로 가지고 있는 열쇠의 상태를 비트마스크로 표현합니다.
• 그리고 현재 위치와 가지고 있는 열쇠 상태에 따라 방문 여부를 체크하며 BFS를 진행합니다.
• 목표 지점에 도착했을 때 움직인 거리가 답이 됩니다.

import sys; input=sys.stdin.readline
from collections import deque

N, M = map(int, input().split())
maze = [list(input().rstrip()) for _ in range(N)]
visited = [[[0] * 64 for _ in range(M)] for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
q = deque()

for i in range(N):
    for j in range(M):
        if maze[i][j] == '0':
            q.append([i, j, 0])
            visited[i][j][0] = 1
            
while q:
    x, y, key = q.popleft()
    
    if maze[x][y] == '1':
        print(visited[x][y][key] - 1)
        exit(0)
        
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0 <= nx < N and 0 <= ny < M:
            char = maze[nx][ny]
            
            if char != '#' and visited[nx][ny][key] == 0:
                if 'a' <= char <= 'f':
                    new_key = key | (1<<(ord(char)-97))
                    visited[nx][ny][new_key] = visited[x][y][key] + 1
                    q.append([nx, ny, new_key])
                elif 'A' <= char <= 'F':
                    if key & (1<<(ord(char)-65)):
                        visited[nx][ny][key] = visited[x][y][key] + 1
                        q.append([nx, ny, key])
                else:
                    visited[nx][ny][key] = visited[x][y][key] + 1
                    q.append([nx, ny, key])

print(-1)

 

• 이렇게 비트마스크를 활용한 문제 해결 전략에 대해 알아보았습니다. 비트마스크는 이진수를 활용하여 집합을 나타내고 연산하는 기법으로, 경우의 수 탐색이나 최적화 문제 등에서 효율적인 해결책을 제시합니다.