1. 비트마스크
비트마스크(BitMask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말합니다.
이진수는 0 또는 1을 이용하므로 하나의 비트(bit)가 표현할 수 있는 경우는 두 가지입니다.
보통 어떤 비트가 1이면 "켜져 있다"라고 말하며, 0이면 "꺼져 있다"라고 말합니다.
https://ko.wikipedia.org/wiki/마스크_(컴퓨팅)
마스크 (컴퓨팅) - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서 마스크(mask) 또는 비트마스크(bitmask)는 특히 비트 필드에서 비트 연산에 사용되는 데이터이다. 마스크를 사용하면 바이트, 니블, 워드 등의 다
ko.wikipedia.org
가. 비트 크기 정하기
두 가지 상태(보통은 포함될지 말지)를 갖는 요소가 n개 있는 경우, 나타날 수 있는 경우의 수는 \(2^{n}\)가지 이고, 이는 n자리 이진수로 표현할 수 있습니다.
예를 들어, 다섯 의 요소가 각각 포함될지, 말지 알아봐야한다면 다섯 자리 이진수가 필요합니다.
나. 유용한 비트 연산
1) 비트의 위치를 옮기기: 쉬프트 연산(<< , >>)
일반적으로 진수 체계를 이용하여 십진수에서 쉽게 계산하는 방법이 있습니다.
바로 10의 제곱 계산은 10 뒤에 0을 더 붙여주거나, 빼는 방법으로 쉬운 계산이 가능합니다.
이진수 체계를 사용하는 컴퓨터도 같은 방법의 이진수 계산을 쉽게 해낼 수 있습니다.
그 방법이 바로 쉬프트 연산입니다.
쉬프트 횟수만큼 이진수의 자릿수를 늘리거나 줄입니다.
이 방법을 이용해 이진수를 필요한 만큼 옮기는 데 활용합니다.
연산 결과는 \(2^{n}\)배 만큼 커지거나 작아지며, 나머지는 버려집니다.
따라서 계산 결과를 십진수로 나타내면 1 << n 은 \(2^{n}\)입니다.
2) 비트 켜기: OR 연산(|)
OR 연산은 논리 연산입니다.
OR 연산의 경우 피연산자의 각각의 자리가 둘 다 0일 때만 0, 나머지 경우는 1이 됩니다.
| 연산자 | 피연산자1 | 피연산자2 | 결과 |
| OR(|) | 0 | 0 | 0 |
| 0 | 1 | 1 | |
| 1 | 0 | 1 | |
| 1 | 1 | 1 |
이런 결과와 위에서 배운 쉬프트 연산을 활용하여 주어진 이진수의 특정 자리 비트를 켤 수 있습니다.
3) 특정 자리의 비트 확인하기: AND 연산(&)
AND 연산도 OR 연산과 마찬가지로 논리 연산입니다.
AND 연산의 경우 피연산자의 각각의 자리가 둘 다 1일 때만 1, 나머지 경우는 0이 됩니다.
| 연산자 | 피연산자1 | 피연산자2 | 결과 |
| AND(&) | 0 | 0 | 0 |
| 0 | 1 | 0 | |
| 1 | 0 | 0 | |
| 1 | 1 | 1 |
이런 결과와 쉬프트 연산을 활용하여 주어진 이진수의 특정 자리 비트가 켜져있는지 확인할 수 있습니다.
2. 동적 프로그래밍
가. DP 테이블의 인덱스
비트마스크를 동적 프로그래밍에 활용하므로 보통 이진수가 DP 테이블의 인덱스가 됩니다.
따라서 DP 테이블의 크기는 2에 이진수의 자릿수(비트의 크기)를 제곱한 만큼이 됩니다.
\(2^{n}\)의 크기는 n이 커질수록 엄청나게 커지므로 보통 비트마스크와 동적 프로그래밍을 활용하기 위해서는 n의 값이 그렇게 크지 않습니다.
나. 쉬프트 연산 횟수에 의미 부여하기
비트마스크를 쓰는 이유는 비트 연산이 효율적으로 활용되기 때문입니다.
위에서 살펴본 비트 연산 활용법을 보면 쉬프트 연산이 거의 필수적으로 활용되는 것을 볼 수 있습니다.
따라서 동적 프로그래밍에 비트마스크를 활용하기 위해서는 쉬프트 연산의 횟수를 바꿔가며 진행하는 것이 일반적이고, 이 때 쉬프트 연산 횟수에 어떤 의미를 부여할지 중요하게 생각해보아야 합니다.
3. 비트마스크와 동적 프로그래밍을 사용하는 예시 문제
가. 선택된 숫자가 모든 가로, 세로 줄에 한 개씩만 되도록 최대값 구하기
가로, 세로 크기가 n이라면, 일일이 찾아본다면 n!만큼의 시간이 걸립니다.
하지만 비트마스크와 DP를 활용하면 \(2^{n}\cdot n\) 시간이 걸립니다.
엄청 효율적이진 않지만 n이 클수록 브루트포스보다 훨씬 효율적입니다.
나. 그래프에서 모든 정점을 한 번씩만 순회하고 다시 제자리로 돌아오는 최소 경로(외판원 문제)
1) 한 사이클에서는 어느 점에서 시작해도 동일한 가중치
그래프에서 사이클이 존재한다면 이 사이클 안에서는 어느 정점에서 출발하든지 다시 제자리로 돌아오는 경우에는 가중치의 합이 같습니다.
따라서 외판원 문제를 해결할 때에는 아무 정점이나 선택해서 출발지로 선택하면 됩니다.
저는 a 정점을 출발지로 정하겠습니다.
2) 비트마스크의 의미
비트마스크는 DP테이블의 인덱스로 활용이 됩니다.
그리고 비트마스크는 특별한 의미를 가집니다.
바로 특정 정점을 방문했는지 여부를 비트의 켜짐과 꺼짐으로 나타냅니다.
아래와 같이 정점이 네 개인 그래프에서는 비트의 크기를 4로 정하면 됩니다.
3) 동적프로그래밍 점화식
a 정점을 출발점으로 정했으므로 모든 정점을 방문한 경우에는 다시 a로 돌아오면 됩니다.
따라서 DP테이블의 1111 인덱스의 값들은 각 정점에서 a 정점으로 이어지는 간선의 가중치가 됩니다.
이 값들을 활용하여 a 정점에서 출발하는 경우까지 재귀적(bottom up 방식)으로 구해낼 수 있습니다.
4) 모든 경우를 탐색하며 최적의 값을 구하기
