4주차: 비트 마스킹

https://www.inflearn.com/course/10%EC%A3%BC%EC%99%84%EC%84%B1-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%81%B0%EB%8F%8C/dashboard

10주완성 C++ 코딩테스트 | 알고리즘 IT취업 자료구조 문제풀이 - 인프런 | 강의

 

https://blog.naver.com/jhc9639/222310927725

[알고리즘 강의] 4주차. 비트마스킹

위 수업을 듣고 정리한 글입니다.

 

 

비트연산자 활용

idx번째 비트 끄기

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int S=18;
    int idx = 1; //인덱스
    S &= ~(1<<idx); //S의 1번째 비트 끄기
    cout << S << "\n";

    return 0;
}



idx번째 비트 XOR 연산

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int S=18;
    int idx = 1; //인덱스
    S ^= (1<<idx); //toggle
    
    cout << S << "\n";

    return 0;
}

 

최하위 비트 찾기

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int S=16;
    int idx = (S & -S);
    
    cout << idx << "\n";

    return 0;
}

 

idx번째 비트 켜기

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int S = 18;
    int idx=0;
    S |= (1<<idx);
    cout << S; //19
    return 0;
}

 

idx번째 비트 켜져있는지 확인

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int S = 18;
    int idx=1; //1번째 켜졌는지 확인 
    if(S &= (1<<idx)){ //0이 아니면
        cout << idx<<"가 켜져있습니다.";
    } else //값이 0이면
    cout << idx<<"가 꺼져있습니다.";
    cout << S; //19
    return 0;
}

 

비트마스킹

해당 비트(이진수, binary digit)를 켜거나 끄는 등의 마스킹을 함

boolean 역할을 하는 하나의 숫자를 만들어서 비트 연산자를 통해 탐색, 수정 작업을 하는 것

즉 5는 {1,0,1}을 뜻함

 

 

비트 마스킹을 이용한 경우의 수

{사과, 딸기, 포도, 배}의 모든 경우의 수 => 16가지

포함하거나(1), 포함하지않거나(0) 2개의 상태값을 가짐

 

#include <bits/stdc++.h>
using namespace std;

const int n = 4;
int main(){
    string a[n]={"사과", "딸기", "포도", "배"};
    for(int i=0;i<(1<<n);i++){ //0~1111까지
        string ret = "";
        for(int j=0;j<n;j++){ //0번째~3번째
            if(i &(1<<j)){ //자리수 있는지 확인
                ret += (a[j]+" ");
            }
        }
        cout << ret << "\n";
    }
    return 0;
}

출력값

조합 결과 정상적으로 나온다.

조합을 사용하지않고 for문으로 표현이 가능하다.

 

 

비트마스킹을 이용한 매개변수 전달

사과라는 매개변수가 포함되어있고 사과+포도, 사과+배 매개변수를 더하는 것을 구현한다면?

 

#include <bits/stdc++.h>
using namespace std;

const int n = 4;
string a[4]={"사과", "딸기", "포도", "배"}; //사과부터 0,1,2,3

void go(int num){
    string ret = "";
    for(int i=0;i<4;i++){
        if(num & (1<<i)) ret += a[i] + " "; //자리수가 있는지 확인
    }
    cout << ret << "\n";
    return;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    for(int i=1;i<n;i++){
        go(1|(1<<i)); //사과+딸기, 사과+포도, 사과+배
    }
}

출력결과

비트마스킹의 한계

int형 숫자의 한계로 31까지 가능하다. 

2^30승정도는 10억이므로 그 정도까지이다. 그 이상이면 어차피 셀때 시간복잡도를 많이 초과한다.