비트마스킹
1. 비트마스킹의 개념
이 문제는 비트마스킹을 사용하여 해결하는 방법입니다. 비트마스킹을 Set이라고 생각하고 접근하면 이해하기 수월합니다. Set은 객체에 값을 저장하고 중복을 제거하는 방식을 사용하지만, 비트마스킹은 정수의 이진수 비트 하나하나를 Boolean 배열처럼 사용하는 기법입니다.
알파벳 소문자를 기준으로 생각해보겠습니다. 소문자는 총 26자이며, 이를 아스키코드로 변환한 뒤 기준점('a'의 아스키코드)을 빼주면 0부터 25까지의 정수로 매핑할 수 있습니다. 'a'의 아스키코드는 97이므로 매핑 공식은 다음과 같습니다.
- 0번 비트: 'a' -> 97 - 97 = 0
- 1번 비트: 'b' -> 98 - 97 = 1
- ...
- 25번 비트: 'z' -> 122 - 97 = 25
문자열의 집합인 를 비트로 표현해보겠습니다.
- 'a'는 0번째 비트 ->
1 << 0= 001 (2진수) - 'c'는 2번째 비트 ->
1 << 2= 100 (2진수) - 둘을 합치면 -> 101 (2진수) = 5 (10진수)
즉, 정수 5가 곧 라는 집합을 의미합니다.
2. 핵심 비트 연산자
1. 원소 추가 (OR 연산 |) mask |= (1 << n) 연산은 mask에 특정 n번째 알파벳을 추가할 때 사용됩니다. "aca"라는 단어를 처리하는 과정을 예로 들어보겠습니다.
let bit = 0; // 00000
// 'a' 추가
let aBit = 'a'.charCodeAt(0) - 97; // 0
bit |= (1 << aBit);
위 연산은 00000 | 00001을 수행하여 00001이 됩니다. OR 연산자는 둘 중 하나라도 1이면 1을 반환합니다.
// 'c' 추가
let cBit = 'c'.charCodeAt(0) - 97; // 2
bit |= (1 << cBit);
00001 | 00100이 되어 결과는 00101입니다. 현재 상태는 입니다.
// 마지막 'a' 추가
bit |= (1 << aBit);
이미 'a'가 포함되어 있는 상태에서 00101 | 00001을 수행하면 결과는 그대로 00101입니다. Set에서 중복 값을 방지하듯, 비트마스킹도 중복된 상태 추가 시 값이 변하지 않습니다.
2. 포함 여부 확인 (AND 연산 &) 현재 상태 mask에 n번째 알파벳이 있는지 확인할 때는 AND 연산을 사용합니다.
if ((mask & (1 << n)) !== 0) {
// n번째 원소가 포함되어 있음
}
여러 원소가 모두 포함되어 있는지 확인할 때는 다음과 같이 검증합니다.
if ((wordMask & learnMask) === wordMask) {
// 단어에 필요한 모든 글자를 알고 있음
}
AND 연산은 두 비트가 모두 1일 때만 1을 반환하여 교집합을 구합니다.
올바른 AND 연산 예시 목표 단어가 "ac"(101), 내 지식이 "abc"(111)인 경우:
- 첫째 자리(a): 둘 다 1 -> 1
- 둘째 자리(b): 단어엔 없지만(0) 지식엔 있음(1) -> 0
- 셋째 자리(c): 둘 다 1 -> 1
- 결과:
101. 목표 단어(101)와 같으므로 읽을 수 있습니다.
못 읽는 경우의 AND 연산 예시 목표 단어가 "ac"(101), 내 지식이 "ab"(011)인 경우:
- 첫째 자리(a): 둘 다 1 -> 1
- 둘째 자리(b): 단어엔 없지만(0) 지식엔 있음(1) -> 0
- 셋째 자리(c): 단어엔 있지만(1) 지식엔 없음(0) -> 0
- 결과:
001. 목표 단어(101)와 다르므로 읽을 수 없습니다.
3. 추가적인 핵심 연산과 알고리즘 적용
비트마스킹을 자유자재로 다루기 위해서는 추가 및 확인 외에도 삭제와 토글 연산을 알아두는 것이 좋습니다.
- 원소 삭제 (
& ~연산):mask &= ~(1 << n)특정 원소를 집합에서 제거할 때 사용합니다. NOT 연산자(~)로 n번째 비트만 0으로 만들고 나머지를 1로 뒤집은 뒤 AND 연산을 하면, n번째 비트만 정확히 0으로 바뀝니다. - 원소 토글 (
^연산):mask ^= (1 << n)XOR 연산은 두 비트가 다를 때만 1을 반환합니다. 따라서 n번째 비트가 1이면 0으로, 0이면 1로 상태를 반전시킵니다.
알고리즘에서의 비트마스킹 활용 '달이 차오른다, 가자'와 같은 문제에서 비트마스킹이 핵심인 이유는 단순히 집합을 표현하기 위함이 아니라, 그래프 탐색(BFS)에서의 상태 관리 때문입니다.
해당 문제에서는 열쇠(a~f)를 획득한 상태에 따라 같은 위치(좌표)라도 다른 상태로 취급해야 합니다. 만약 배열이나 Set 자료구조를 상태 확인에 사용한다면 메모리 초과나 시간 초과가 발생합니다. 하지만 비트마스킹을 사용하면 visited[Y좌표][X좌표][열쇠상태(0~63)]와 같이 3차원 배열의 인덱스로 현재 보유한 열쇠 집합을 O(1)의 시간 복잡도로 관리할 수 있습니다.
마무리 정리
비트마스킹은 다수의 상태(State)나 요소의 포함 여부를 단 하나의 정수로 압축하여 표현하는 강력한 최적화 기법입니다. 논리 연산자(|, &, ~, ^)를 활용해 빠른 속도로 교집합, 합집합, 포함 여부 검증을 수행할 수 있습니다. 처음 접할 때는 이진수 연산이 추상적으로 느껴질 수 있으나, 본문의 설명처럼 '크기가 고정된 가벼운 Set 자료구조'로 접근하면 쉽게 이해할 수 있습니다. 이를 완벽히 숙지하면 복잡한 상태 관리가 요구되는 BFS 탐색이나 동적 계획법(DP) 문제를 매우 효율적으로 해결할 수 있습니다.