비트마스크

interviewsangu·2020년 7월 14일
0

알고리즘

목록 보기
3/12
post-thumbnail

비트마스크

A << B 는 A x 2^B와 같다.
A >> B 는 A / 2^B와 같다.

보통 0 ~ N-1까지 정수로 이루어진 집합을 나타낼 때 사용한다.
1부터 N까지 정수로 이루어진 집합을 사용하는 경우 공간이 2배 더 필요하므로
0부터 사용한다.

i를 기준으로
& (1 << i) 검사
| (1 << i) 추가
&~ (1 << i) 제거
^ (1 << i) 토글 0 -> 1 , 1 -> 0
(1 << N) - 1 전체 집합
0 공집합

https://www.acmicpc.net/problem/11723
집합

#include <cstdio>
#include <cstring>
using namespace std;
char b[111];
int main() {
    int n = 20;
    int m;
    scanf("%d",&m);
    int s = 0;
    int x;
    while (m--) {
        scanf("%s",b);
        if (!strcmp(b,"add")) {
            scanf("%d",&x); x--;
            s = (s | (1 << x));
        } else if (!strcmp(b,"remove")) {
            scanf("%d",&x); x--;
            s = (s & ~(1 << x));
        } else if (!strcmp(b,"check")) {
            scanf("%d",&x); x--;
            int res = (s & (1 << x));
            if (res) {
                puts("1");
            } else {
                puts("0");
            }
        } else if (!strcmp(b,"toggle")) {
            scanf("%d",&x); x--;
            s = (s ^ (1 << x));
        } else if (!strcmp(b,"all")) {
            s = (1<<n)-1;
        } else if (!strcmp(b,"empty")) {
            s = 0;
        }
    }
    return 0;
}

https://www.acmicpc.net/problem/1182
부분집합의 합

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int n, s;
	cin >> n >> s;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int count = 0;
	// 크기가 양수인 부분수열이기 때문에 i = 1부터 시작 해야 한다.
	for (int i = 1; i < (1 << n); i++) {
		int temp = 0;
		for (int j = 0; j < n; j++) {
			if (i & (1 << j)) {
				temp += a[j];
			}
		}
		if (temp == s)
			count += 1;
	}
	cout << count << '\n';
	return 0;
}

0개의 댓글