💡 비트마스크(BitMask)
-
비트연산을 이용하여 정수로 집합을 나타낼 수 있는 기법
-
비트로 부분집합을 나타낼 수 있다.
비트마스크를 사용하는 이유
-
완전 탐색을 할 때, 재귀호출 없이 모든 경우를 살펴볼 수 있다.
(브루트포스와 콤비가 잘맞는 것 같다.) -
집합을 배열의 인덱스로 표현 가능하다. (※메모리 절약)
-
상태가 다이나믹한 경우에 자주 사용한다.
비트마스크 표기법
가 있으면, 우리는 이걸 정수로 라고 나타낼 수 있다.
🚩 연산
현재 집합 S에서, 비트마스크를 이용한 연산은 다음과 같다.
1 포함 검사
- AND 연산자(&) 이용
- 집합 S에 K가 포함되었는지 검사: (S>>X) & 1
- 0 : 포함되어있지 않음
- 2^i : 포함되어있음.
2 추가
- OR 연산자(|) 이용
- 집합 S에 X 추가: S |= (1<<X)
3 삭제
- '&', '~' 사용
- 집합 S에서 X 삭제: S &= ~(1<<X)
4 토글(0을 1로, 1을 0으로)
- '^' 사용
- 집합 S에 X 토글 : S ^= (1<<X)
5 전체 집합
- S = (1<<N)-1
이를 이용해서 문제를 하나 풀어보자.
BOJ :: 부분수열의 합(1182)
✔️ 문제
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.
💻 입력
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
💻 출력
첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.
🤔 내가 생각한 아이디어
부분 수열이라는 말에서 브루트포스+비트마스크 를 이용하여 풀 수 있겠다고 생각했다.
만약 N=5로 주어진다면, 공집합이 아닌 부분 수열의 갯수는 2^5-1=31개이다. 이는 길이가 5인 비트들로 표현할 수 있다. (0=미포함, 1포함)
- 상태 : 모두 고른 상태는 (1, 1, 1, 1, 1)
- 표현값 : 5개의 원소를 포함하고 있는 상태를 표현한 값 = 31(= 🚩연산에서의 집합 S)
☝️ STEP 1
표현값 1~31을 반복문을 통해 돌며, 문제의 모든 상태를 확인함을 의미한다.
다음 코드는 표현값을 이용한 것이다.
for(int i = 1; i < (1<<n); i++) ✌️ STEP 2
이제 모든 표현값(=모든 상태)를 확인하면서, 배열의 인덱스번째 수(j번째 수)가 포함되어있는지 판단해야 한다.
따라서 다음을 이용할 수 있다.
- 집합 S에 i가 포함되었는지 검사: S & (1<<i)
코드에서 살펴보면, 다음과 같다.
for(int i = 1; i < (1<<n); i++) { // i라는 표현값 생성 2^5-1 = 31개
int sum = 0;
for(int j = 0; j < n; j++){ // i라는 표현값과 &연산으로 배열의 0~n-1인덱스까지 비교
if(i&(1<<j)) { // j번째 인덱스가 i집합(표현값 i)에 들어있다면
sum+=a[j];
}
}
if(sum==s) cnt++;
}
💻 전체 코드
#include <iostream>
using namespace std;
int n, s;
int a[100004];
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> s;
for(int i = 0; i < n; i++) {
cin >> a[i];
}
int cnt =0;
for(int i = 1; i < (1<<n); i++) { //i라는 표현값 생성 2^5-1 = 31개
int sum = 0;
for(int j = 0; j < n; j++){ //i라는 표현값과 &연산으로 배열의 0~n-1인덱스까지 비교
if(i&(1<<j)) {
sum+=a[j];
}
}
if(sum==s) cnt++;
}
cout << cnt << "\n";
return 0;
} 