비트마스크를 사용해 부분집합을 표현하고, 완전탐색을 해봅시다.
std::bitset도 원리는 같습니다.
비트연산
먼저 1비트의 논리연산 truth table을 알아봅시다.
| A | B | A & B (AND) |
A | B (OR) |
A^B (XOR) |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
AND는 두 비트가 모두 1일때만 출력이 1, OR은 두 비트가 하나라도 1이면 출력이 1입니다.
XOR은 두 비트가 다르면 1입니다.
cout << (1 << 0) << '\n'; // 0000 0001 = 1
cout << (1 << 1) << '\n'; // 0000 0010 = 2
cout << (1 << 2) << '\n'; // 0000 0100 = 4
cout << (1 << 3) << '\n'; // 0000 1000 = 8
cout << (1 << 4) << '\n'; // 0001 0000 = 16
cout << (1 << 5) << '\n'; // 0010 0000 = 32
cout << (1 << 6) << '\n'; // 0100 0000 = 64
cout << (1 << 7) << '\n'; // 1000 0000 = 128시프트 연산자(shift operator) <<, >>를 사용해 비트를 좌우로 밀 수 있습니다. 이때 padding bit는 0이 들어갑니다
c++에서 음수의 시프트 연산은 undefined behaviour(논리시프트일지 산술시프트일지 모름)이기 때문에 시프트 연산할 때는 unsigned 정수 사용을 추천드립니다.
비트 검사, 수정 방법
(1) 검사(test)
어떤 수의 n번째 비트가 1인지 아닌지 검사하려면 어떻게 할까요?
n번째 비트에 1을 넣은 값과 and 연산을 한 값이 0이면 0, 1 이상이면 1입니다.
예를 들어 210의 뒤에서 다섯번째 비트가 1인지 아닌지 검사하는 식은 다음과 같습니다.
1101 0010 = 210
& 0001 0000 = 1<<(5-1) = 1<<4
-----------
0001 0000검사할 비트를 제외하고는 다 0을 넣고, 검사할 비트에만 1을 넣어 and 연산을 하면 그 비트가 1인지 아닌지 검사할 수 있습니다.
이때 and 연산의 결과는 1이 아닐 수 있습니다. 예시를 보면 결과가 2^4인걸 확인할 수 있습니다.
정리하면 n번째 비트가 1인지 검사하려면 1<<(n-1)과 and 연산을 한 값을 보면 됩니다.
std::bitset에서는 test 메소드를 사용하면 됩니다.
(2) 설정(set, reset)
특정 비트를 0, 1로 설정하려면 어떻게 할까요?
0으로 설정하려면 특정 비트만 0인 수와 AND 연산을, 1로 설정하려면 특정 비트만 1인 수와 OR 연산을 하면 됩니다.
예를 들어 210의 뒤에서 네번째 비트를 1로 설정해보겠습니다.
1101 0010 = 210
| 0000 1000 = 1<<(4-1) = 1<<3
-----------
1101 1010어렵지 않습니다.
210의 뒤에서 두번째 비트를 0으로 설정해보겠습니다.
1101 0010 = 210
& 1111 1101 = ~(1<<(2-1)) = ~(1<<1)
-----------
1101 0000두번째 비트는 0, 나머지는 다 1인 수와 and 연산을 하면 두 번째 비트를 0으로 만들 수 있습니다.
NOT 연산을 사용해 00000010에서 11111101로 뒤집는 것을 참고하시고요.
정리하면 n번째 비트를 0으로 설정하려면 ~(1<<(n-1))과 and 연산을 하면 되고, 1로 설정하려면 1<<(n-1)과 or연산을 하면 됩니다.
std::bitset에서는 set, reset 메소드를 제공합니다.
(3) 뒤집기(flip)
특정 비트가 0이면 1로, 1이면 0으로 바꾸려면 어떻게 해야 할까요? 물론 위 검사와 설정 방법을 사용해도 되지만 더 간편한 방법이 있습니다.
바로 XOR을 사용하는 건데요, XOR의 truth table을 다시 한번 확인해보겠습니다.
| A | B | A^B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
보시면 B=0일 때 결과값은 A과 동일하고 B=1일때는 ~A인 걸 확인할 수 있습니다.
즉, 뒤집을 비트는 1 아닌 비트는 0으로 설정한 값과 XOR 연산을 해주면 됩니다.
예를 들어 210을 뒤에서 네 비트 전부 뒤집으려면 아래처럼 하면 됩니다.
1101 0010 = 210
^ 0000 1111
-----------
1101 1101
std::bitset에서는 flip 메소드를 제공합니다.
비트마스크로 부분집합 표현
배열로 집합을 표현할 수 있는데요, 비트마스크로 부분집합을 표현할 수 있습니다.
0부터 \(2^N - 1\)까지 이진수로 표현했을 때 1인 비트만 부분집합에 포함하면 이렇게 모든 부분집합을 구할 수 있습니다.
int n = 6;
int arr[6] = { 3,4,5,7,8,9 };
for (int i = 0; i < (1 << n); ++i) {
cout << "{ ";
for (int j = 0; j < n; ++j) {
if (i & (1 << j))
cout << arr[j] << ' ';
}
cout << "}\n";
}{ }
{ 3 }
{ 4 }
{ 3 4 }
...
{ 4 5 7 8 9 }
{ 3 4 5 7 8 9 }위 코드는 모든 부분집합을 완전탐색하는 코드와 출력입니다.
그림이랑 순서가 좀 다른데, 그림 그릴때 인덱스 순서를 생각을 못했네요. 이점 참고해주시고요.
주의할 점은 집합의 크기가 int 범위를 넘어가는 경우, int의 배열로 비트마스크를 구성하거나 std::bitset을 사용해야 합니다. 물론 문제가 \(2^N\)의 시간복잡도로 풀리는지 그것도 고려해보고 안되면 다른 방법을 사용해야겠죠.
주의사항
비트시프트 연산자의 우선순위가 산술 연산자보다 낮은데 이 점 유의하셔야 합니다.
for (int i = 0; i < 1 << 3 - 1; ++i) {
cout << i << '\n';
}예를 들어 위 코드에서 i가 몇보다 작을 때까지 for문이 수행될까요? i<(1<<3)-1 일까요? i<1<<(3-1)일까요?
정답은 i<1<<(3-1)입니다. 더하기, 빼기가 비트시프트 연산보다 우선순위가 높기 때문입니다.
cpp 레퍼런스에서 연산자 우선순위를 보면 위와 같습니다. precedence가 낮을수록 우선순위가 높은데요, bitwise shift는 곱하기, 나누기, 나머지, 더하기, 빼기보다 우선순위가 낮기 때문에 프로그래밍 할 때 우선순위를 고려해야 합니다.
제일 편하고 확실한 방법은 괄호를 치는 것입니다.
for (int i = 0; i < (1<<3)-1; ++i) {
cout << i << '\n';
}괄호를 치면 무엇보다 보기 쉽고, 연산자 우선순위를 고민하지 않아도 됩니다.
연습문제
'알고리즘 > 완전탐색' 카테고리의 다른 글
| 재귀함수를 사용해 n개의 원소 중 m개를 고르는 모든 조합 찾기 (0) | 2020.04.26 |
|---|
