백준 C++ 11723번 집합 ( 비트마스크 )

 

요즘 독서 중인데

진짜 그.. 뭐랄까 심신에 위안을 받는달까..

책이랑 예전엔 조금 거리가 있었는데

요즘은.. 힐링도서를 종종 찾아서 읽는다.

마음이 따뜻해지는 느낌이다.

다음에는 철학책을 좀 읽어보고 싶다 ㅎ

---

 

집합..?

흠.. 그 내 경험적 지식(?)으로는...ㅋㅋㅋㅋ

막 스택 덱 이런 거에 나오던 건데..

집합..?! 은 처음이다.

 

약간 배열로 푸는 건가?

집합 s라니까..

근데 연산의 수가.. 3백만 개다..ㄷ 흠

그러면 for문을 300백만 번.. 흠..

ㅋㅋ

 

일단 풀었다.

배열로

 

자잔!

하지만 제씨는 나에게 이거 말고 더 쉬운 게 있다고 속삭였다.

 

비트마스킹..?!

비트마스킹

이진수의 각 bit를 플래그 ( 0 또는 1 )로 사용하여

정수 하나로 여러 개의 상태정보를 효율적으로 관리하고 조작하는 기법

 

비트 단위 연산은 총 4개

AND ( & ) 두 비트가 1일 때만 1

OR ( | ) 두 비트가 둘 중 하나만 1 이어도 1

XOR ( ^ ) 두 값이 다르면 1 같으면 0 

NOT( ~ ) 0은 1로 1은 0으로

 

비트마스킹은 32개의 0과 1을 담고 있기 때문에

굳이 배열을 21개 만들지 않아도!

이 숫자 안에 있는 0과 1을 사용한다...라고 했다.....

 

그래서...

int S= 0로 정해두고.

S에서 비트연산자를 사용하는 것..

---

 

1. add

add는 추가라서 0이 1이 되어야 하니까

겹칠 수 있는 OR이 와야 한다.

S |= ( 1 << x )

그리고 OR이 와주어야

다른 애들은 저장이 되는 동시에 x 칸만큼 이동한 것이 추가로 켜지게 된다.

 

 

2. remove

사실 이거 add는 조금 쉬웠는데 remove는 좀 어려웠다.

왜냐면 결과적으로 무조건 0이 되어야 한다.

그럴 땐

AND와 NOT 이 들어와야 한다.

 

네..?!!? 어려워요.

 

자 ( 1 << x ) 는 x 만 켜진 상태이다.

그러면 앞에 ~ 를 넣어서

~ (1 << x ) 는 뭘까?

x 빼고 다 켜진 상태가 된다.

 

이 상태에서

& 를 해주면 된다.

 

예시로 01010 { 1,3 } 에서 3을 remove 해보자.

 

1 << 3일 것이고 그럼 01000이다.

~ 해주면 10111이고

이 식을 기존에 01010이랑 & 해주면

AND는 두 비트가 1일 때만 1이니까

00010만 남는다.

그러면 3은 빠지고 1만 된 모습을 볼 수 있다.!

 

 

3. check 

이거는 이제 if문만 잘 써주면 될 거 같은데?

...

그냥

 

if (S == (1<<x)) 해주면 안 되나?

NO

 

이렇게 해주면

x만 가지고 있냐?라고 해석이 되어서 좋은 방향이 아니라고 한다.

 

그러면.. 뭐가 있을까?

더 좋은 친구가 있다며 소개해주었다...

 

이 친구 이름은  &

S에 들어있는 식과 (1<<x) 값을 겹쳐서 보는 것이다.

근데 기존에 있던 식과 x칸 간 식 0001이라면 x칸도 기존칸도 1이 같으면 무조건 1이니까!

 

if문은 & 로 마무리해 준다.

 

 

4. toggle

있으면 없애고 없애면 있게 해 주는 것

사실 이거 이름만 들어도 NOT이긴 한데

 

그냥.. 위에 식들 고대로 옮겨주면 안 되나?

 

 

그냥 x가 있으면 빼주고, 없으면 더해주는 위에서 했던 add / remove 쓰면 된다.

 

하지만 제씨는 아쉬워했다.

진짜가 따로 있다고....

상태를 뒤집기 위해서 태어난 친구가 있다며..

NOT이 아닌 XOR 을 소개해주었다..

두 값이 다르면 1 같으면 0 이 되는 특징을 가지고 있어서

 

그냥 S ^= (1 << x ) 만 해줘도 된다.

한 줄로 끝!

 

 

5. all

모두 1로 만드는 방법이 뭐가 있을까?

전혀 감을 잡지 못하는 나에게 제씨는

이게 비트마스킹의 꽃이라며.. 알려주었다.

S ( 1 << 21) -1;

만 해주면 된단다.

음? 값은 20개까진데 왜 21을? 

21을 1이 가면

21번째 칸만 1인, 

0이 뒤에 20개인 친구가 만들어진다.

 

근데 여기서 -1을 해주면

1이 지워지면서

뒤에 친구들이 다 1로 바뀐다.

 

제씨는 마치 1000-1은 999라고 설명했다.

 

그리고 사실

S = ~0

도 있다고 한다.

0을 not 해주니 다 1이 된다는 뜻이다.

대신 주의할 점이 비트는 32개라

  20번 이상의 숫자를 물어본다면 1이 나온다.

 

S=1이 안되려나? 했는데

... 이거는 그냥 1인 거고

S ~0 이랑 다른 거다.

 

 

6. empty

그냥 S를 0으로 만들면 된다.

 

 

---

 

와... 비트마스킹..

진짜 비전공자가 비트마스킹을 이해할 수 있을까?

진짜 머리 아프다...

안 엮이고 싶어.......ㅋㅋㅋㅋ

 

푸는데 두 시간이나 걸렸다.

정확히 말하면

푸는데 10분

답보고 이해하고 정리하는데 1시간 50분..

고생했습니다..........^^