때로 브루트포스에서 경우의 수 (부분집합)를 따지는 상황이 왕왕 발생한다.
그런 상황에서 요긴하게 쓰이는 bitmask로 경우의 수 따지기, 유용한 상황 처리에 대해서 정리하려고 한다.
비트마스크(Bitmask)는?
이진수로 표현된 비트들의 집합으로, 각 비트가 특정 상태를 나타냅니다. 비트마스크를 사용하면 집합의 부분집합을 효과적으로 나타낼 수 있고, 이를 활용하여 경우의 수를 따질 수 있습니다.
기본적인 사용법
public class BitmaskExample {
public static void main(String[] args) {
int n = 3; // 비트 수
int total = 1 << n; // 총 경우의 수: 2^n
for (int i = 0; i < total; i++) {
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) > 0) {
// j번째 비트가 1인 경우의 처리
System.out.print(1);
} else {
// j번째 비트가 0인 경우의 처리
System.out.print(0);
}
}
System.out.println(); // 한 줄 출력 후 개행
}
}
}1.각 비트를 사용, 사용X의 상태로 생각 :
예를들어 int[] A = {1,2,3} 이라면 123의 부분집합을 구하여 문제에서 주어진 경우의 수를 따질 수 있다.
-> 예를 들어 3개의 비트를 사용한다면, 000,001,010,011,100,101,110,111 과 같이 2^3 = 8가지의 상태를 나타낼 수 있다.
2. 비트 연산을 통한 조합 :
비트 연산을 사용해 특정 경우가 사용되고 있는지, 내가 원하는 비트가 켜져 있는지 체크하여 경우의 수를 고려할 수 있다.
-> & (AND), | (OR), ^(XOR) , ~ (NOT) 연산을 사용한다.
예시
괄호 추가하기 : https://www.acmicpc.net/problem/16637
괄호 추가하기의 문제로 3+87-92 식의 수식이 주어지면 연속된 괄호 없이 모든 괄호를 치는 '경우의 수' 를 따져서 최대 계산 값을 따지는 문제이다.
이 문제에서는 괄호가 연속으로 쳐지면 안된다. 따라서 우리는 비트마스크를 사용하여 괄호를 적용할 위치의 부분집합을 나타내고, 이를 통해 가능한 모든 경우의 수를 구하게 된다.
다음과 같은 경우를 예로 들어보겠습니다:
- (3+8)(7-9)2 의 경우는 가능
- ((3+8)7)-92 의 경우 불가능. 중첩 괄호 X
int cnt = 수식의 수 4
//(+ , *, -, * ) 의 부분집합들로 모든 경우의 수를 찾는다.
for (int bit = 0; bit < (1 << cnt); bit++) {
boolean ok = true;
//각 경우마다 내부에서 0,1,2,3번째 개체가 들어갔나 체크하기 위해 반복한다.
for(int i = 0; i < m - 1; i++) {
//지금 부분집합 (bit) 에서 지금과 다음 수식에 괄호가 함께 쓰이면 패스한다.
if((bit & (1 << i)) > 0 && (bit & (1 << (i + 1))) > 0) {
ok = false;
break;
}
}
if(!ok) continue;
//하고 싶은 작업
}Java 코드에서는 먼저 수식의 개수를 기반으로 부분집합을 나타내는 bit를 설정합니다.
이후 모든 부분집합에 대해, 연속된 두 수식에 동시에 괄호가 적용되어 있는지 검사합니다.
이 경우, 괄호가 연속해서 적용되어 있으므로 해당 부분집합은 배제하고, 그렇지 않은 경우에만 계산을 진행하게 됩니다.
이 방법을 통해 연속된 괄호 없이 모든 괄호를 적용할 수 있는 경우의 수를 구할 수 있습니다.