[Algorithm] 완전탐색0

비트마스크

시프트 연산자

A << B : A * 2ᴮ

A >> B : A / 2ᴮ

비트연산자

어떤 수가 홀수인지 짝수인지 판별할 때, if (N%2 == 1) 은 if (N&1) 로 쓸 수 있다

비트마스크

정수로 집합을 나타낼 수 있다

{ 1,3,4,5,9 } = 570 (1000111010) = 2¹ + 2³ + 2⁴ + 2⁵ + 2⁹

X가 포함되어있는지 검사

X번째 비트만 1 & 연산

S & ( 1<<X )

X를 추가해는 연산

X번째 비트만 1 | 연산

+는 중복된 것을 또 추가할 수 있지만 | 연산은 중복값이 추가되는것을 방지

S | ( 1<<X )

X를 제거하는 연산

X번째 비트만 1 Not 연산

연산 후 &연산을 통해 제거

S & ~ ( 1<<X )

X를 토글

X번째 비트만 1 XOR 연산

S ^ ( 1<<X )

🔥비트마스크는 STL의 bitset으로 쉽게 사용할 수 있다!

순열

1 ~ N 까지로 이루어진 수열

크기는 항상 N이 되어야 하고, 겹치는 숫자가 존재하지 않음

크기가 N인 순열은 총 N!개가 존재한다

N = 3인 경우에 사전순은

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

다음 순열

순열을 사전순으로 나열했을 때, 사전순으로 다음에 오는 순열과 이전에 오는 순열을 찾는 방법

C++ STL에 next_permutation 과 prev_permutation 이 존재!

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    
    vector<int> v(n);
    for(int i=0; i<n; i++){
        v[i] = i+1;
    }
    
    do{
        for(int i=0; i<n; i++){
            cout << v[i] << ' ';
        }
        cout << endl;
    }while(next_permutation(v.begin(), v.end()));
}