집합의 요소들의 구성 여부를 표현할 때 유용한 테크닉
왜 사용할까?
- DP, Permutation 등 배열 활용으로만 해결이 불가한 문제
- 작은 메모리와 빠른 수행시간으로 해결 가능(원소가 적다는 가정 하)
- 집합을 배열의 인덱스로 표현 가능
- 코드가 간결해짐
Bit?
- 컴퓨터에서 사용되는 데이터의 최소 단위(0,1) - 2진법을 생각하자
우리가 사용하는 10진수를 2진수로 바꾸면?
9(10진수) -> 1001(2진수)
비트마스킹 활용
0과 1로, flag 활용하기
[1,2,3,4,5]라는 집합이 있다.
여기서 임의로 몇 개를 골라 뽑아서 확인을 해야하는 상황이 주어졌다. (즉, 부분집합을 의미)
{1}, {2} , ... , {1,2} , ... , {1,2,5} , ... , {1,2,3,4,5}
물론, 간단히 for문을 돌려가며 배열에 저장하며 경우의 수를 구할 순 있다.
하지만, 비트마스킹을 하면, 각 요소를 인덱스처럼 표현하여 효율적인 접근이 가능하다.
[1,2,3,4,5] → 11111
[2,3,4,5] → 11110
[1,2,5] → 10011
[2] → 00010집합의 i번째 요소가 존재하면 1, 그렇지 않으면 0을 의미한다.
이러한 2진수는 다시 10 진수로 변환도 가능하다.
11111은 10진수로 31이므로, 부분집합을 정수를 통해 나타내는 것이 가능하다는 것을 알 수 있다.
- 31은 [1,2,3,4,5] 전체에 해당하는 부분집합에 해당한다는 것!
이로써, 해당 부분집합에 i를 추가하고 싶을 때 i번째 비트를 1로만 바꿔주면 표현이 가능해졌다.
이런 행위는 비트 연산을 통해 제어가 가능하다.
비트 연산
AND, OR, XOR, NOT, SHIFT
- AND(&) : 대응하는 두 비트가 모두 1일 때, 1 반환
- OR(|) : 대응하는 두 비트 중 모두 1이거나 하나라도 1일때, 1 반환
- XOR(^) : 대응하는 두 비트가 서로 다를 때, 1 반환
- NOT(~) : 비트 값 반전하여 반환
- SHIFT(>>,<<) : 왼쪽 혹은 오른쪽으로 비트 옮겨 반환
- 왼쪽 시프트 : A * 2^B
- 오른쪽 시프트 : A / 2^B
[왼 쪽] 0001 → 0010 → 0100 → 1000 : 1 → 2 → 4 → 8
[오른쪽] 1000 → 0100 → 0010 → 0001 : 8 → 4 → 2 → 1
developer