비트연산자
& : AND
| : OR
^ : XOR
~ : NOT
알고리즘 설명
- 00?0 | 0010 = 0010 (특정 위치 1로 만들기)
- 00?0 & 1101 = 0000 (특정 위치 0으로 만들기)
- 0010 ^ 0011 = 0001 (특정 위치 반대로 만들기)
- ~0000 = 1111 (전체 반전하기)
주의
오버플로우에 매우 유의
0 혹은 양의 정수에서만 연산이 이루어지게 하자.
비트의 개수를 잘 생각해서 int인지 long long인지 판단 잘하자.
만약 int 타입으로 충분하다면 1 << x 로 해도 되지만
long long 을 사용해야 한다면 1LL << x 로 리터럴 상수 타입을 long long으로 타입변환을 해야 한다.
연습문제
BOJ_11723번: 집합
문제
비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.
add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
all: S를 {1, 2, ..., 20} 으로 바꾼다.
empty: S를 공집합으로 바꾼다.
입력
첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.
둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.
출력
check 연산이 주어질때마다, 결과를 출력한다.
예제 입력 1
26
add 1
add 2
check 1
check 2
check 3
remove 2
check 1
check 2
toggle 3
check 1
check 2
check 3
check 4
all
check 10
check 20
toggle 10
remove 20
check 10
check 20
empty
check 1
toggle 1
check 1
toggle 1
check 1
예제 출력 1
1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0
풀이
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int M;
cin >> M;
int S = 0;
while(M--){
string op;
cin >> op;
int x;
if(op == "add"){
cin >> x;
S |= (1 << (x-1));
}else if(op == "remove"){
cin >> x;
S &= (~(1 << (x-1)));
}else if(op == "check"){
cin >> x;
cout << ((S >> (x-1)) & 1) << "\n";
}else if(op == "toggle"){
cin >> x;
S ^= (1 << (x-1));
}else if(op == "all"){
S = 0xfffff;
}else{
S = 0;
}
}
return 0;
}BOJ_1497번: 기타콘서트
문제
강토는 Day Of Mourning의 기타리스트로, 다가오는 공연을 준비하고 있다.
어느 날 강토의 집에 도둑이 들어서 기타를 모두 도둑맞고 말았다. 기타를 사야 한다.
강토는 공연 때 연주할 노래의 목록을 뽑아 놓았다. 하지만, 하나의 기타로 모든 곡을 연주할 수는 없다. 어떤 기타는 어떤 곡을 연주할 때, 이상한 소리가 나기 때문이다. 항상 완벽을 추구하는 강토는 이런 일을 용납하지 않는다.
최대한 많은 곡을 제대로 연주하려고 할 때, 필요한 기타의 최소 개수를 구하는 프로그램을 작성하시오.
예를 들어, GIBSON으로 1, 2, 3번 곡을 제대로 연주할 수 있고, FENDER로 1, 2, 5번 곡을 제대로 연주할 수 있고, EPIPHONE으로 4, 5번 곡을 제대로 연주할 수 있고, ESP로 1번곡을 제대로 연주할 수 있다면, 세준이는 EPIPHONE과 GIBSON을 사면 최소의 개수로 모든 곡을 연주할 수 있다.
입력
첫째 줄에 기타의 개수 N과 곡의 개수 M이 주어진다. N은 10보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 기타의 이름과 기타가 연주할 수 있는 곡의 정보가 1번 곡부터 차례대로 주어진다. Y는 연주할 수 있는 것이고, N은 없는 것이다. 기타의 이름은 알파벳 대문자로만 이루어져 있고, 길이는 2 이상, 50 이하이다. 두 기타의 이름이 같은 경우는 없다.
출력
첫째 줄에 필요한 기타의 개수를 출력한다. 만약 연주할 수 있는 곡이 없으면 -1을 출력한다.
예제 입력 1
4 5
GIBSON YYYNN
FENDER YYNNY
EPIPHONE NNNYY
ESP YNNNN
예제 출력 1
2
풀이
#include <bits/stdc++.h>
using namespace std;
int n, m;
long long state[10];
int bit_cnt(long long x){
int ret = 0;
for(int i = 0; i < max(n, m); i++){
ret += (x >> i) & 1;
}
return ret;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 0; i < n; i++){
string name, tmp; // name은 사실 의미없음
cin >> name >> tmp;
for(int j = m-1; j >= 0; j--){
state[i] = (state[i] << 1) | (tmp[j] == 'Y');
}
}
pair<int, int> ans = {0, -1}; // {연주할 수 있는 곡의 수, 필요한 기타의 수}
for(int tmp = 0; tmp < (1 << n); tmp++){
long long comb = 0; // 조합한 결과
for(int i = 0; i < n; i++){
if((tmp & (1LL << i)) == 0)
continue;
comb |= state[i];
}
int song_num = bit_cnt(comb);
int guitar_num = bit_cnt(tmp);
if(ans.first < song_num) // 1. 연주할 수 있는 곡의 수가 더 많을 경우
ans = {song_num, guitar_num};
// 2. 연주할 수 있는 곡의 수는 같은데 필요한 기타의 수가 더 적을 경우
else if(ans.first == song_num && ans.second > guitar_num)
ans = {song_num, guitar_num};
}
cout << ans.second << '\n';
}