비트마스크 (Bitmask)
쉽게 풀면
물건 5개 중에서 "어떤 것을 담았고 어떤 것을 안 담았는지"를 표시한다고 해봅시다. 물건마다 담았으면 1, 안 담았으면 0으로 놓고 이걸 나란히 이어 붙이면 00101 같은 이진수 하나가 만들어집니다. 이 숫자 하나만 보면 5개 물건의 포함 여부를 전부 알 수 있고, 컴퓨터는 이런 이진수를 정수로 저장해 매우 빠르게 다룰 수 있습니다. 이것이 비트마스크입니다. "두 조합을 합치기"(비트 OR), "공통된 것만 남기기"(비트 AND), "포함 여부 뒤집기"(비트 NOT) 같은 집합 연산을 배열이나 반복문 없이 정수 연산 한 번으로 처리할 수 있어서, 부분집합을 다루는 문제나 상태 전체를 하나의 값으로 압축해야 하는 동적계획법에서 특히 자주 사용됩니다.
왜 중요한가
비트마스크는 단순한 구현 트릭처럼 보이지만, 알고리즘 논문에서는 상태 공간의 크기를 줄여 계산 복잡도를 낮추는 핵심 수단으로 다뤄집니다. 특히 부분집합 열거나 상태 기반 동적계획법에서는 상태를 정수 하나로 표현함으로써 배열 인덱싱과 비교 연산을 정수 연산 수준으로 단순화할 수 있어, 조합 최적화나 그래프 탐색 문제의 실용적인 성능 개선과 직결됩니다. 또한 시스템 소프트웨어나 하드웨어 설계 분야에서는 여러 플래그나 권한, 자원 상태를 압축 저장하는 표준적인 방법으로 자리 잡고 있어 자료구조와 실무 양쪽에서 반복적으로 등장합니다.
논문에서는 이렇게 쓰입니다
이 문장은 "지금까지 어떤 지점들을 들렀는지를 하나의 이진수로 표현해서, 그 상태별로 계산 결과를 저장하는 방식을 사용했다"는 뜻입니다. 조합 최적화 문제나 상태가 많은 탐색 문제의 계산량을 줄이는 데 널리 쓰입니다.
운영체제나 보안 분야 논문에서 흔히 볼 수 있는 표현으로, 여러 개의 권한(읽기, 쓰기, 실행 등)을 각각 별도의 필드로 저장하는 대신 하나의 정수 안 비트들로 합쳐 두고, 권한이 있는지는 AND 연산 한 번으로 즉시 확인한다는 뜻입니다. 이렇게 하면 조건문을 여러 번 거치지 않아도 되어 처리 속도가 빨라집니다.
기계학습이나 데이터 분석 논문에서는 여러 특징(feature)을 사용할지 말지의 조합 전체를 빠짐없이 표현할 때 비트마스크를 사용하기도 합니다. 특징이 n개면 가능한 조합은 2의 n제곱 가지인데, 이를 0부터 2의 n제곱 마이너스 1까지의 정수로 하나씩 대응시켜 모든 경우를 체계적으로 순회했다는 의미입니다.
조금 더 깊게 보면
논문을 읽다 보면 비트마스크와 함께 "비트 연산(AND, OR, XOR, NOT)"과 "시프트 연산(왼쪽/오른쪽 시프트)"이 자주 함께 등장하는데, 이는 비트마스크로 표현된 상태를 조작하거나 특정 비트만 확인·설정·해제할 때 쓰이는 기본 도구입니다. 예를 들어 특정 원소를 집합에 추가할 때는 OR 연산을, 포함 여부만 확인할 때는 AND 연산을 사용하는 식입니다. 동적계획법에서는 이렇게 만든 비트마스크 값을 배열의 인덱스로 그대로 사용해 "상태별 최적값"을 저장하는 방식이 일반적이며, 이런 기법을 흔히 "비트마스크 동적계획법"이라 부릅니다. 다만 상태 수가 2의 원소 개수제곱으로 늘어나기 때문에, 원소 개수가 커지면 메모리와 연산량이 급격히 증가한다는 점도 함께 언급되는 경우가 많습니다.
주의할 점
비트마스크로 표현할 수 있는 집합의 크기는 컴퓨터가 한 번에 다루는 정수의 비트 수(보통 32비트나 64비트)에 제한되므로, 원소 개수가 수십 개를 넘어가는 큰 집합에는 그대로 적용하기 어렵습니다. 이런 경우 유니온-파인드처럼 집합을 다루는 다른 자료구조를 함께 고려해야 합니다.