백준 11723. 집합

알고리즘 기초 문제 중 브루트포스 - 비트마스크 문제(540)

집합

1. 간단 설명

구현 문제

각 명령어와 숫자가 주어지면, 해당하는 명령을 수행한다

check로 출력하여 결과를 확인하는 문제

2. 예시

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

가 주어진다면

add 1, add 2를 수행하여 S = {1, 2} 가 있는 상태가 된다

이후 check 1, 2, 3을 하면

1, 2는 있고, 3은 없으므로 1 1 0 을 출력한다

remove 2 를 수행하면 s = {1}만 남은 상태이므로

check 1, 2 수행 시 1 0을 출력한다

toggle 3 수행 시, 3은 없었으나, 토글되므로 s = {1, 3}이 된다

이후 check 1234를 하면 1 0 1 0 을 출력하게 된다

주의사항

• 주어지는 연산의 수가 엄청 많음 M (1 ≤ M ≤ 3,000,000)
• 입출력이 많으므로, cin, cout 사용 시 주의

3. 알고리즘

집합 S를 어떤 자료형을 사용할것인지에 따라 다양한 방법으로 문제를 해결할 수 있다

간단하게 bool 형을 사용하는 방법과

비트마스킹을 이용하는 방법 2가지로 풀어볼 예정

필요 변수

• 연산의 수 int M(1 ≤ M ≤ 3,000,000)
• 주어진 명령어 string cmd
• 매개변수 int x (1 ≤ x ≤ 20)

bool 형을 사용 시

• bool arr[21] <- 각 자리별로 해당 수가 집합 S에 들어있다면 True, 없다면 False

비트마스킹을 이용한다면

• unsigned int s 혹은 bitset<21> s 사용

4. 소스코드

• bool형을 사용한 방법

#include <iostream>

using namespace std;

bool arr[21];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	// freopen_s(new FILE*, "input.txt", "r", stdin);
	int M; cin >> M;
	while (M--) {
		string cmd;
		int x;
		cin >> cmd;

		if (cmd == "add") {
			cin >> x;
			arr[x] = true;
		}
		else if (cmd == "remove") {
			cin >> x;
			arr[x] = false;
		}
		else if (cmd == "check") {
			cin >> x;
			cout << arr[x] << '\n';
		}
		else if (cmd == "toggle") {
			cin >> x;
			arr[x] = !arr[x];
		}
		else if (cmd == "all") {
			for (int i = 1; i <= 20; i++) {
				arr[i] = true;
			}
		}
		else if (cmd == "empty") {
			for (int i = 1; i <= 20; i++) {
				arr[i] = false;
			}
		}

	}

	return 0;
}

• 비트 마스킹을 사용한 방법

#include <iostream>
#include <string>

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	//freopen_s(new FILE*, "input.txt", "r", stdin);

	int M, N;
	unsigned int s = 0;
	string cmd;

	cin >> M;
	while (M--) {
		cin >> cmd;
		if (cmd == "add") {
			cin >> N;
			s |= (1 << N); // 원소 추가
			/*
			1 << N : 1을 왼쪽으로 N비트 이동
			이를 S 와 or 연산하여 해당 비트를 1로 설정
			*/
		}
		else if (cmd == "remove") {
			cin >> N;
			s &= ~(1 << N); // 원소 제거
			/*
			1 << N : 1을 왼쪽으로 N비트 이동
			이를 NOT 연산 (~)를 이용하여 0과 1을 모두 바꿈
			이를 S와 AND 연산하여 해당 비트를 0으로 설정 
			*/

		}
		else if (cmd == "check") {
			cin >> N;
			if (s & (1 << N)) {
				cout << 1 << '\n';
			}
			else {
				cout << 0 << '\n';
			}
		}
		else if (cmd == "toggle") {
			cin >> N;
			s ^= (1 << N);
		}
		else if (cmd == "all") {
			s = (1 << 21) - 1; // 모두 1로 설정
		}
		else if (cmd == "empty") {
			s = 0;
		}
	}
	return 0;
}

• bitset 라이브러리를 이용한 방법

#include <iostream>
#include <bitset>

using namespace std;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	bitset<21> s = 0;
	string cmd;
	int x;

	// freopen_s(new FILE*, "input.txt", "r", stdin);
	int M; cin >> M;
	while (M--) {
		cin >> cmd;

		if (cmd == "add") {
			cin >> x;
			s.set(x, true);
		}
		else if (cmd == "remove") {
			cin >> x;
			s.set(x, false);
		}
		else if (cmd == "check") {
			cin >> x;
			cout << s[x] << '\n';
		}
		else if (cmd == "toggle") {
			cin >> x;
			s.flip(x);
		}
		else if (cmd == "all") {
			s.set();
		}
		else if (cmd == "empty") {
			s.reset();
		}

	}

	return 0;
}