Week2

Bitmask

Bitmask란 완전 탐색으로 문제를 해결할 때 사용하는 방법으로 순열을 이용한 접근과 유사합니다. Bitmask는 정수를 이용하여 배열과 같이 표현하는 방법으로 일종의 자료구조입니다. 컴퓨터에서는 숫자를 이진수로 저장한다는 원리를 이용한 것입니다. 아무래도 Bit를 이용하는 자료구조이기 때문에 true(1), false(0)만 저장할 수 있습니다. Bitmask를 이용한 완전 탐색은 O(2^n)의 시간복잡도를 가집니다. Bitmask는 bitwise 연산을 이용하여 배열처럼 사용합니다.

bitwise 연산

OR(|), AND(&), XOR(^), NOT(~), SHIFT(<<, >>)

자주 사용하는 연산

• 𝑖번째 비트 켜기 𝑥 = 𝑥 | (1 ≪ 𝑖)
• 𝑖번째 비트 끄기 𝑥 = 𝑥 & ~(1 ≪ 𝑖 )
• 𝑖번째 비트 토글 𝑥 = 𝑥 ^ (1 ≪ 𝑖)
• 𝑖번째 비트가 켜져있는지 확인 𝑖𝑓(𝑥 & 1 ≪ 𝑖 )
• 켜져있는 최하위 비트 받아오기 𝑏 = (𝑥 & −𝑥 )
• 어떤 값이 -1이 아닌지 확인 𝑖𝑓(~𝑥)
• 두 집합의 교집합 𝑈 = 𝐴 & 𝐵
• 두 집합의 합집합 𝑈 = 𝐴 | 𝐵
• 두 집합의 합집합 - 교집합 𝑈 = 𝐴^𝐵
• 하위 𝑁개의 비트를 모두 켜기 𝑥 = (1 ≪ 𝑛) − 1
• 비트를 모두 끄기 𝑥 = 0

백준 1182번 Bitmask 이용 풀이

#include <iostream>
#include <vector>

using namespace std;

int N, S, ans;

int main() {
	cin >> N >> S;

	vector<int> v(N);

	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}

	for (int i = (1 << N) - 1; i > 0; i--) { // n개의 비트를 다 켜고 1을 빼면서 순열처럼 모든 경우 방문
		int sum = 0;
		for (int j = 0; j < N; j++) {
			if (i & (1 << j)) { // j번째 비트가 켜져있는지 확인
				sum += v[j];
			}
		}
		if (sum == S) {
			ans++;
		}
	}

	cout << ans;

	return 0;
}

Backtracking

Backtracking은 완전 탐색과 매우 유사하게 구현하지만 효율적인 계산을 위해 가지치기 수행합니다. 이 백트래킹은 현재 상태에서 절대로 답이 될 수 없는 경우 탐색을 중단합니다. 백트래킹은 일반적으로 시간복잡도를 계산하기가 어렵습니다.