[BaekJoon 11723][⚪5] 집합
❓ 문제
🎯 난이도
Silver ⚪5
🧠 풀이
1. 내 풀이 (bitset)
- 알고리즘
Bit Masking
- 설명
bitset를 사용하는 풀이이다.
비트 마스킹에 적합한 컨테이너인 bitset을 사용하는 방법이다. 원하는만큼의 비트수만큼 할당을 하고, 배열처럼 인덱스 기반으로 접근도 가능, set, reset, flip, test 같은 편리한 기능이 많이 있어서 사용을 했다.
하지만 후술하겠지만 'bitset'은 '64'보다 큰 크기의 비트 공간이 필요하거나 대량의 비트들을 한 번에 연산하는 데 적합하다. 따라서 이 문제에서는 약간 과한 편이긴 하다.
각각의 명령이 O(1)인 과정을 N번 반복하므로 시간 복잡도는 O(N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <bitset>
#include <string>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iN{};
cin >> iN;
bitset<21> bsNum{}; // 1 ~ 20의 범위 할당
while(iN--)
{
string strCmd{};
cin >> strCmd;
if(strCmd == "add")
{
int iInput{};
cin >> iInput;
// 해당 비트를 1로 변환
bsNum[iInput] = 1;
}
else if(strCmd == "remove")
{
int iInput{};
cin >> iInput;
// 해당 비트를 0으로 변환
bsNum[iInput] = 0;
}
else if(strCmd == "check")
{
int iInput{};
cin >> iInput;
// 해당 비트가 1인지 확인
cout << (bsNum.test(iInput) ? 1 : 0) << '\n';
}
else if(strCmd == "toggle")
{
int iInput{};
cin >> iInput;
// 해당 비트가 0이면 1로, 1이면 0으로 변환
bsNum.flip(iInput);
}
else if(strCmd == "all")
{
// 모든 비트를 1로 변환
bsNum.set();
}
else if(strCmd == "empty")
{
// 모든 비트를 0으로 변환
bsNum.reset();
}
}
return 0;
}
2. 추가 풀이 (정수 비트 마스킹)
- 알고리즘
Bit Masking
- 설명
bitset을 쓰지 않고 하나의 정수형 변수로 비트 마스킹을 하는 방식이다.
1 ≤ x ≤ 20이므로 int형 변수 하나만으로 충분히 모든 연산이 가능하므로 가능한 방법이다. 각종 비트 단위 연산자를 사용해서 명령을 실행하는데, 이는 직접적으로 비트를 연산하는 것이므로 bitset보다 가독성 자체는 좀 떨어지긴 한다.
주목할 점은 모든 비트를 1로 만드는 방법에 대해서인데, iMask = (1 << 21) - 2;로 했다. 이 과정은 다음과 같다.
1 << 21로 21번째 비트만 1이 된다.- 여기서
1을 빼면0 ~ 20까지의 비트가1, 21번째 비트는0이 된다. 1 ≤ x ≤ 20이므로0번째 비트는 제외해야 하므로1을 한 번 더 빼서1 ~ 20까지의 비트만1이 된다.
위와 같은 과정으로 all 명령을 수행하는 건데, 그럼 왜 iMask = -1으로 하지 않을까? 그렇게 하면 정수의 모든 비트가 '1'이 되는데, 이는 우리가 원하는 범위를 넘어서는 변환이기 때문에 의도와 다르므로 굳이 그렇게 하지 않는 것이다.
위와 마찬가지의 이유로 전체적인 시간 복잡도는 O(N)이다
- 코드
내 풀이 코드
#include <iostream>
#include <string>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iN{};
cin >> iN;
int iMask{}; // 0 ~ 31까지의 비트 연산 가능
while(iN--)
{
string strCmd{};
cin >> strCmd;
if(strCmd == "add")
{
int iInput{};
cin >> iInput;
// 해당 비트를 1로 변환
iMask |= (1 << iInput);
}
else if(strCmd == "remove")
{
int iInput{};
cin >> iInput;
// 해당 비트를 0으로 변환
iMask &= ~(1 << iInput);
}
else if(strCmd == "check")
{
int iInput{};
cin >> iInput;
// 해당 비트가 1인지 확인
cout << ((iMask & (1 << iInput)) ? 1 : 0) << '\n';
}
else if(strCmd == "toggle")
{
int iInput{};
cin >> iInput;
// 해당 비트가 0이면 1로, 1이면 0으로 변환
iMask ^= (1 << iInput);
}
else if(strCmd == "all")
{
// 모든 비트를 1로 변환
iMask = (1 << 21) - 2;
}
else if(strCmd == "empty")
{
// 모든 비트를 0으로 변환
iMask = 0;
}
}
return 0;
}
💭 후기
두 방법 모두 정석에 가까운 풀이이고, 속도는 두 번째 풀이가 조금 더 빠르지만 얼마 차이는 나지 않는다. 하지만 이 문제에서 두 번째 풀이가 더 나은 이유는 몇 가지 존재한다.
bitset은 내부적으로long long으로 구현되어 있기 때문에bitset<21>이더라도8바이트의 공간을 할당한다. 이는int형 변수 하나의4바이트보다 크다.- 일반
비트 마스킹이CPU단일 레지스터의 연산, 단일 명령이라 컴파일러 최적화인 반면에bitset은STL로써 하나의 컨테이너이기 때문에 내부적인 함수 호출, 비트 위치 계산, 마스크 연산 등의오버로딩이 생긴다.
따라서 bitset은 1) '정수형 변수' 하나만으로 불가능한 크기의 비트의 연산이나, 2) '비트의 집합'을 통째로 연산을 하는 경우, 3) '가독성'이 중요한 때에 사용하는 것이 좋다.
Comments