비트마스킹은 언제 사용할 것인가 241107

모든 원소들의 사용유무를 판정해 모든 경우의 수를 나타내거나, 집합으로 표현할 때 사용한다.

• on / off 동작에 의해서 구분 지을수 있고, 모든 집합의 경우의 수를 작성해야 할 때 떠올려야 한다!

사용법

• xor 는 두비트가 같으면 0이고, 다르면 1이다.
• or는 하나라도 1이면 1이고, 나머지는 0이다.
• and는 모두 1이면 1이고, 나머지는 0이다.
• not은 모든 비트를 반전
• << n 은 왼쪽으로 n번 시프트 할것이다.
  ->> n 은 오른쪽으로 n번 시프트 할 것이다.

비트마스킹 문제는 반드시 괄호를 사용하자!

예시 : {a,b,c,d}를 집합으로 표현하라

: {공집합}, {a} , {b} {c} {d} {a,b} {a,c} {a,d} {b, c} {b, d} {c, d} {a,b,c} {a,b,d} {a, c,d} {b, c, d} {a,b,c,d}
=> 총 16개로 표현할 수 있다.

각 요소들의 있고 없고에 따라 나타낼 수 있다.
없음을 0으로 하고, 있음을 1로 나타내면, 비트로 나타낼수 있다.
십진수 : 부분집합 : 비트로 표현
0 : {} -> {0,0,0,0}
1 :{a} -> {0,0,0,1}
2 : {b} -> {0,0,1,0}
3 : {c} -> {0,1,0,0}
4 : {d} -> {1,0,0,0}
5 : {a,b} -> {0,0,1,1}
6 : {a,c} -> {0,1,0,1}
7 : {a,d} -> {1,0,0,1}
8 : {b, c} -> {0,1,1,0}
9 : {b, d} -> {1,0,1,0}
10 : {c, d} -> {1,1,0,0}
11 : {a,b,c} -> {0,1,1,1}
12 : {a,b,d} -> {1,0,1,1}
13 : {a, c,d} -> {1,1,0,1}
14 : {b, c, d} -> {1,1,1,0}
15 : {a,b,c,d}-> {1,1,1,1}
: 이렇게 표현하는 것을 비트마스킹이라고 한다.

• 부분집합의 총 개수는 " 1 << 요소의 갯수 " : 현재 위에서는 16이다.
• 0000 에서부터 "+ 1" 씩 증가를 하면 모든 집합을 표현할 수 있다.

비트 연산자 공식.

0) 전체의 경우 탐색

: i << (1 << cnt);
왜 이거냐면 (1 << cnt)
만약에 cnt가 4라면 (1 << 4) 는 10000 이렇게 나오고
십진수로 나타내면 16이기 때문이다.
{a,b,c,d}의 총 집합의 수는 16이다.

왜 ?
: 원소가 3개일 경우에는 a , b, c, 이렇게 있다 하면
a, b, c
x x x
0 x x
0 0 x
0 x 0
x 0 x
x x 0
x 0 0
0 0 0
-> 총 8개의 경우의 수가 나옴.
이것은 원소 각자리의 비트를 나타낸것이나 다름없음.
1 << 원소의 개수를 이용해서 모든 경우의 수를 나타낼 수 있음.

0) i번째 원소로 이동시키자.

1 << i 를 하면 된다.
1을 2번 이동하게 되면 100 이 된다.

1) i번째 원소가 있는지 확인

: i번째 원소가 있는지 확인하는 방법은
(비트로 표현된 집합) & (1 < i) 결과가 0이 아니면 존재
<i를 증가 시키면서 순서대로 확인이 가능하다>
ex) 2번째 원소가 있는지 확인
: 0101 & (1 << 2) =>(결과) 0101 & 0100 = 0100 이므로 존재한다.

-> 예시는 맨 위에서 과일을 선택할 수 있는 모든 경우의 수를
구할 때 사용됨.

2) i번째 원소를 추가

: (비트로 표현된 집합) | (1 << i)

왜냐하면 | 연산자는 더하는 의미이다.

ex) 1번째 원소를 추가
0101 | (1 << 1) => (결과) 0101 | 0010 = 0111

3) i번째 원소를 삭제

: (비트로 표현된 집합) &~(1<<i)

왜냐하면 & 연산자는 2개의 비트가 모두 동일해야 1로 반환되기 때문에
한곳을 0으로 만들어보리자는 의도이다.

ex) 2번째 원소를 삭제
0101 & ~(1<<2) => (결과) 0101 & ~(0100) = 0101 & 1011 = 0001

4) 1이 존재하고 있는 비트수 세기

• 예를 들어서 두수의 합이 7인 경우의 수를 구해라 할때 사용하면 된다.

int countBits(int n)
{
	int ret = 0;
    while(n)
	{
    	if(n & 1) ret++;
        n = n >> 1;
    }
	return ret;
}

5) 전부다 1 만들기

5의 원소를 가지고 있는 집합이라고 한다면
// { 1,1,1,1,1};
data = ( ( 1 << 5) - 1 )

• 의미하는 것은 data 를 100000 만들어 놓고,
  빼기 1을 하면 1,1,1,1,1 됨.

출처

: 유튜브 ezsw 님 강의!
https://www.youtube.com/watch?v=Bujy_-O99xQ&list=PL6YHvWRMtz7DS3hVaqMazHujPcKVfblQa&index=3

😅정의

: 불리언 배열의 역할을 하는 하나의 숫자를 만들어서, 비트연산자를 통해
탐색, 수정 등의 작업을 하는 것을 비트마스킹이라고 함.

• 있다 없다 또는 on / of 를 선택해야 만 하는 경우의 수를 구할 때,
  비트마스킹을 생각하자.

어떻게 생각해야 하면 좋을까?

: 2진수만 비트연산자 표현되는 것이 아니라, 10진수는 컴터 입장에서
알아서 2진수로 바라봄.
-> 10진수를 2진수로 바라보는 시선을 가지고 진행하자.
--> 전체를 for 문으로 1 << cnt 이렇게 표현할 건데
10진수 일 뿐, 컴터는 2진수로 바라본다는 생각을 가지자.

비트 연산자 왜씀??

• O(1) 에 구현되는 것이 많음.
• 반복문 없이 사용 가능

비트마스킹 사용 조건

: 요소의 , 인덱스의 갯수가 30개 이하일 경우에 사용가능함.

어떻게 만들 것인가?

• 만약에 3개의 인덱스가 존재한다고 가장하자.

1) 모든 경우의 수를 범위로 만들어야 함.
[가][나] [다]
: 모든 경우의 수 : 000 / 001 010 100 101 110 111
하나의 구획에서 선택할 수 있는 경우, 2가지 , 총 몇개 3개
-> 2의 3승.
2의 n승 - 1임
-> 이 범위를 먼저 만들어야 함.

1단계
: for(int i =0; i < (1 << n); ++i)

2) 인덱스 하나하나씩 1과 & 연산자로 비교하기

---

Problem 1번 : 큰돌님.

사과 , 귤, 포토 ,딸기 중에서 선택할 수 있는 모든 경우의 수를 비트마스킹을 이용해서 표현하라.

#include <iostream>
using namespace std;
#include <string>

int main()
{
	string fruit[4] = { "사과","귤","포도","딸기" };
	cout << "나타낼 수 있는 모든 경우의 수는? " << endl;

	// 15 번을 돌려야 함.
	// 15번을 어떻게 표현할 수 있을 까???
	// 이진수로 나타낼수 있음을 알고 있어야 함. 
	// 모든 수는 2진수로 표현이 가능하다라는 것을 숙지 해야함.
	
	int n = 0;
	// 시프트를 하면서 비교할 횟수
	// 여기서 시프트는 그냥 + 1씩 증가하는 값으로 비교하면 될듯>?
	for (int i = 0; i < (1 << 4) ; ++i)
	{
		// 0 0 0 1
		// 0 0 1 0
		// 등등...
		
		cout << "{ ";
		for (int j = 0; j < 4; j++)
		{
			// 이미 i 값을 고정되어 있는데//
			// 이거를 어떻게 각 인덱스와 비교를 할것인가
			// 에 대한 고찰이 중요함...

			// 0000 과 4개를 비교?? 
			// 결과 : 아무것도 안나옴,. 

			// 0001 과 4개를 비교?? 
			// 결과 : 사과만 나옴

			// 각 자리의 위치와 i를 비교해야함.
			// 각 자리수는 2의 제곱승임을 파악을 해야함.
            // 밑에서 i번째 원소가 있는지 확인하는 공식을 여기서 사용하자.
			if (i & (1 << j))
				cout << fruit[j] << " ";

		} 
		cout << " } ";

	}
	
}

최근 : 구현하는 방법에 대해서

: 모든 수는 2진수로 표현이 가능함.
-> 비트마스킹을 이용해 처리 가능함.

문제!
예시 : 사과, 귤, 포도, 딸기 의 모든 경우의 수를 표현하라.
1번 : 아무것도 없음
2번 :사과
3번 :귤
4번 :사과 귤
5번 :포도
6번 :포도 사과
7번 :포도 귤
8번 :포도 사과 귤
...
15번 :사과 귤 포도 딸기
: 총 15개로 나타낼수 있음!

1. 전체를 돌려야 하는데, 원소의 개수가 4개일때는 총 15번임.
   : 시프트 연산자로 전체를 나타낼 수 있음.
2. 전체를 순환하는 i와 4개의 원소간의 & 를 하면 뭔가 될것
   같다는 느낌이 옴,
   : 여기서 알아야 할게 인덱스 자리의 위치값은 2의 제곱이라는 것임
   -> 뭔 소리냐면 string fruit[4] = { "사과","귤","포도","딸기" };

   사과 : -> 0 0 0 1 => 1
   귤 : -> 0 0 1 0 => 2
   포도 : -> 0 1 0 0 => 4
   딸기 : -> 1 0 0 0 => 8
   이다.

어차피 for문으로 4개를 돌리면서 조합하면서 처리할 것이므로
각 원소들의 위치값과 i를 & 하자는 이야기임.

결과 :
for (int i = 0; i < (1 << 4) ; ++i)
{
	for(int j = 0; j < 4; j++)
    {
      i & (1 << j)
      // 이런식으로 진행! 
    }
}

---

소스코드

: 집합{a,b,c,d}를 나타낼수 있는 모든 경우의 수를 출력하라!

1) for문을 어디까지 돌릴지를 생각해보면, 0에서 16미만 까지이다.
그러므로 for(int i = 0; i < (1 << size); i++) 이렇게 표현할 수 있다.
2) & 연산자를 이용한 결과가 1이면 출력하고, 아니면 PASS
A가 있음으로 나오게 하려면 마지막 비트가 "1" 이어야 한다.
일단 가장 큰 for문은 0 에서부터 15까지 돈다.
0000 -> 1111 까지 돌게 되는 것인데 , i번째 원소가 있는지 확인하는 방법은
(비트로 표현된 집합) & (1 < i) 결과가 0이 아니면 존재
ex) 2번째 원소가 있는지 확인
: 0101 & (1 << 2) =>(결과) 0101 & 0100 = 0100 이므로 존재한다.

#include <iostream>
using namespace std;

void printSubset(char *data, int cnt)
{
	int c = 0;
	for (int i = 0; i < (1 << cnt); i++)
	{
		cout << " { ";
		for (int j = 0; j < cnt; j++)
		{			
			c++;
			if (i & (1 << j))
				cout << data[j] << " ";
		}
		cout << " } " << endl;
	}

	cout << c << endl;
}
//0000
//0001
//0010
//0011

int main()
{
	char word[4] = { 'a', 'b', 'c', 'd' };
	printSubset(word, 4);

	return 0;

}

Problem 2번.: ezsw 님 출처!

연습문제 : 1,2,3,4,5,6 로 이루어진 집합의 원소를 한번만 사용해서 합이 7이 나올 수 있는 모든 경우의 수는?
집합 형식으로 출력하라!!

#include <string>
#include <vector>
#include <sstream>
#include <iostream>
using namespace std;


int arr[] = { 1,2,3,4,5,6 };

void solve()
{
	int cnt = 0;

	cout << "1,2,3,4,5,6을 한번씩 만 사용해서 더해서 7이 나올수 있는 모든 경우의 수는" << endl;
	//조합해서 합이 7 인 경우의 집합을 출력하고 경우의 수도 출력하자.
	for (int i = 0; i < (1 << 6); i++)
	{
		vector<int>v;
		int sum = 0;
		for (int j = 0; j < 6; j++)
		{
        //0720 왜 이렇게 해야하는지 의도를 파악해야 함...
			if (i & (1 << j))
			{
				sum += arr[j];
				v.push_back(arr[j]);
			}
		}

		if (sum == 7)
		{
			cnt++;
			cout << "{";
			for(auto k : v)
			cout << k;
			cout << "}" << endl;
		}

	}
	cout << "7을 만든 횟수는 ?" << endl;
	cout << cnt;
}


int main()
{
	solve();
	

}

• 풀이
  

관련 문제

: 카카오 2019 후보키