[코딩테스트] 브루트 포스(비트마스크)
reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.
비트마스크
- 비트(bit)연산을 이용해 부분 집합 표현
- 비트는 0과 1로 구성, 연산자 &(and), ｜(or), ~(not), ^(xor)
- A가 0011 B가 0101
- ~A 1100
- A & B 0001 (둘 다 1일때만 1)
- A ｜ B 0111 (둘 중 하나가 1이면 1)
- A ^ B 0110 (두개가 다르면 1)
- 두 수 A와 B를 비트 연산 하는 경우엔 가장 뒤의 자리부터 하나씩 연산 수행됨
- not 연산의 경우엔 자료형에 따라 결과가 달라진다.
- A = 83 = 1010011₂
- ~A = 10101100₂ (8비트 자료형일 경우)
- ~A = 11111111 11111111 11111111 10101100₂ (32비트 자료형일 경우)
- unsigned, signed에 따라 보여지는 값이 다르다.
- shift left(«)와 shift right(») 연산
- A « B (A를 왼쪽으로 B비트만큼 민다)
- 1 « 1 = 2 (10₂) , 1 « 2 = 4 (100₂)
- 즉 « 는 A x 2^B
- A » B (A를 오른쪽으로 B비트만큼 민다)
- 10(1010₂) » 1 = 5(101₂)
- 즉 » 는 A / 2^B
- (A+B) / 2 는 (A+B) » 1 로 쓸 수 있다.
- 비트마스크 : 정수로 집합을 나타내는 것
- 집합은 중복되는 수가 없다. 없으면 0 있으면 1
- {1,3,4,5,9} = 1000111010₂ = 570 = 2^1 + 2^3 + 2^4 + 2^5 + 2^9
- 비트마스크의 장점
- 공간을 적게 사용(정수 1개)
- 정수 ex) A[ {1,3,4,5,99} ]를 A[570]으로 나타낼 수 있다.
- 집합 연산의 시간복잡도 O(1)
- 비트마스크의 단점
- 정수이다. 32비트는 0~31, 64비트엔 0~63까지만 저장 가능하다. 적은 갯수를 저장하는 집합에만 사용할 수 있다.
- 비트마스크의 조건
- 범위가 있다 0~(N-1)까지 N개의 정수로 이루어진 집합
- 1부터 N까지 정수로 이루어진 집합 사용은 공간이 2배 더 필요
- 비트마스크는 집합이기에 필요한 연산 세가지가 있다. 1. 검사 2. 추가 3. 삭제
- 검사
- 0이 포함되어 있는지 검사 = 570 & 2^0 = 570 & (1«0) = 0
- 3이 포함되어 있는지 검사 = 570 & (1«3) = 8
- 즉 S에 X가 있는지 검사 = S & (1 « X) = 0이면 없음, (1 « X)면 있다
- 또는 (S » X) & 1 = 0이면 없음 1이면 있음
왜냐하면 S » X의 0번째 비트 = S의 X번째 비트이기 때문이다
- 추가
- 1 추가하기 = 570 ｜ 2¹ = 570 ｜ (1«1) = 570 (1000111010₂)
- 2 추가하기 = 570 ｜ 2² = 570 ｜ (1«2) = 574 (1000111110₂)
- S에 X를 추가 = S의 X번째 비트를 1로 변경(or 사용) = S ｜ (1 « X)
- 제거
- 3 제거하기 = 570 & ~(1«3) = 562 (1000110010₂)
- S에 X를 제거 = S & ~(1 « X)
- 토글연산(0은 1, 1은 0으로 만드는 연산)
- 570 ^ 2³ = 570 ^ (1«3) = 562 (1000110010₂)
- S ^ (1 « X)
현재 집합이 S일 때
- i를 검사 : S & (1 « X)
- i를 추가 : S ｜ (1 « X)
- i를 제거 : S & ~(1 « X)
- i를 토글 : S ^ (1 « X)
- 전체 집합 (1 « N) - 1
- 비트마스크에 N개의 수를 저장하는 거면 0부터 n-1까지 넣는 거니까
- 공집합 0
- 비트 연산을 사용할 땐 연산자 우선 순위를 생각해야 한다.
- 1 « N - 1 은 1 « (N - 1) 로 계산된다. 언어마다 우선 순위가 다른데, 비트연산은 괄호를 꼭 활용해서 정확한 계산 결과가 나오게 하자.
- 배열 사용하는 게 더 편하지만, 비트마스크를 사용하는 이유는 집합을 배열의 인덱스로 표현할 수 있기 때문. 상태 다이나믹을 할 때 자주 사용하게 됨.
- 함수(옵션1, 옵션2, 옵션3) 이런 boolean 옵션 3개가 있을 때 옵션 4,5,6,7로 늘어나면 저 모든 함수를 바꿔줘야 한다. 그런데 함수 만들 때 비트마스크를 사용했다면 별도 처리없이 추가 가능하다.
집합(11723번)
https://www.acmicpc.net/problem/11723
문제
- 비어있는 공집합 S가 주어졌을 때, 연산 수행하는 프로그램 작성
- 1 ≤ M ≤ 3,000,000
풀이
- 1~20까지 배열 = 비트마스크로 풀려면 0~19로 변경
- 완전 비트마스크를 위한 문제같다…
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String args[]) throws NumberFormatException, IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int m = Integer.valueOf(bf.readLine());
int s = 0;
StringBuilder sb = new StringBuilder(); //출력이 많으니 sout보다 StringBuilder 이용
while(m-->0) { //m개만큼 연산이 주어지니까
String[] ch = bf.readLine().split(" ");
if(ch[0].equals("add")) {
int num = Integer.valueOf(ch[1])-1; // -1 해주는 이유는 비트마스크 범위가 0~(N-1)니까
s = s | (1<<num);
}
if(ch[0].equals("remove")) {
int num = Integer.valueOf(ch[1])-1;
s = s & ~(1<<num);
}
if(ch[0].equals("check")) {
int num = Integer.valueOf(ch[1])-1;
if((s & (1<<num))!=0) {
sb.append("1\n");
} else {
sb.append("0\n");
}
}
if(ch[0].equals("toggle")) {
int num = Integer.valueOf(ch[1])-1;
s = s ^ (1<<num);
}
if(ch[0].equals("all")) {
s = (1<<20)-1; //{1, 2, ..., 20}
}
if (ch[0].equals("empty")) {
s = 0;
}
}
System.out.println(sb);
}
}
부분수열의 합(1182번)
https://www.acmicpc.net/problem/1182
문제
- 서로 다른 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 문제
- 1 ≤ N ≤ 20
풀이
- 재귀로 푼다면 각각 기준으로 포함하는 경우 / 포함하지 않는 경우를 이용해서 구현
- N개의 정수로 이루어진 수열의 모든 부분수열 갯수 구하기 = 2ⁿ-1가지 (크기가 양수인 부분수열을 구하는게 문제조건이니까)
-
O(2ⁿ x N) = 전체부분수열 x 합을 구하는데 걸리는 시간 = 1048576 * 20 OK!
import java.util.*; public class Main { public static void main(String args[]) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int s = sc.nextInt(); int[] a = new int[n]; for(int i=0; i<n; i++) { a[i] = sc.nextInt(); } int ans = 0; //i가 곧 비트마스크, 1~n-1까지의 비트마스크를 나타냄(0은 공집합이니 제외), 즉 i의 값이 부분집합을 나타낸다. for(int i=1; i<(1<<n); i++) { int sum = 0; //여기부터 합을 구해주면 된다 for(int k=0; k<n; k++) { //비트마스크 i에 k가 들어있는지 검사하고, 들어있으면 합 구하고 아니면 넘긴다 //k는 0~n-1까지 돌며 i(부분집합)의 어떤 index 원소를 가지는지 검사한다. if((i & (1<<k)) != 0) { //자바는 if문에서 비트계산 boolean 형식으로만 리턴한다 sum += a[k]; } } if(sum==s) { ans += 1; } } System.out.println(ans); } }
스타트와 링크(14889번)
https://www.acmicpc.net/problem/14889
문제
- N명을 N/2명씩 두 팀으로 나누려고 한다 (4 ≤ N ≤ 20, N은 짝수)
- 두 팀의 능력치를 구한 다음 차이의 최소값을 구하는 문제
- S[i][j] = i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치
- 팀의 능력치 : 팀에 속한 모든 쌍의 S[i][j]의 합
풀이
- N명을 두팀으로 나눠서 비트마스크로 풀기 가능. 0번,1번으로 팀 나눠줄 수 있으니까
- 0 ~ (1 « N)까지 모든 방법 살펴보며 0번팀, 1번팀으로 나눠주고 N/2인지 확인하고 차이 최소값 구하기
- 옛날에 풀었던 문제인데 비트마스크로도 풀 수 있음
종이조각(14391번)
https://www.acmicpc.net/problem/14391
문제
- N x M 크기의 종이를 조각으로 잘라서 합의 최대값을 구하는 문제(1 ≤ N, M ≤ 4)
풀이
- 조각은 1 X k 의 형태, 한쪽이 1이면 됨
- 어떻게 종이조각을 자르는 게 합이 최대가 될까? 1x4는 4자리 정수, 3자리보다 크다
- 수를 가장 길게 만드는게 정답. 하지만 0이 있을 때 이 방법이 통하지 않는다. 따라서 브루트포스로 풀어야 함.
- 가로조각, 세로조각으로 나뉘기 때문에 비트마스크 사용 가능. 가로0, 세로1로 이루어진 nm개의 칸. nm = 4x4 = 16자리의 비트마스크로 가능
- 어떻게 가로로 나누지? 세개, 두개와 하나, 하나와 두개… 수를 나눌 때 원래 수보다 커지는 경우는 없다. 무조건 세개 칸이 연속된다고 봐주면 된다.
- 비트마스크를 이용! NM자리의 비트마스크 = A[i][j] = ixM+j
- 수의 합을 구하기 (각각 행,열에 대해 얼마나 연속되는지)
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] a = new int[n][m];
for(int i=0; i<n; i++) {
String s = sc.next();
for(int j=0; j<m; j++) {
a[i][j] = s.charAt(j) - '0';
}
}
int ans = 0;
// 0 가로, 1 세로
for(int s=0; s<(1<<(n*m)); s++) {
int sum = 0;
//가로 행 연속 알아보기
for(int i=0; i<n; i++) {
int cur = 0;
for(int j=0; j<m; j++) {
int k = i*m+j;
if((s&(1<<k)) == 0) { //가로가 연속으로 이어질 경우
cur = cur*10 + a[i][j]; // 3 + 2 면 32가 되어야 하니까
} else {
//가로가 끊긴 경우 (다음 세로인 경우)
sum += cur;
cur = 0;
}
}
sum += cur; //마지막 행이 가로로 끝났을 경우 더하지 못하고 끝나니까 덧셈처리
}
// 세로 열 연속 알아보기
for(int j=0; j<m; j++) {
int cur = 0;
for (int i=0; i<n; i++) {
int k = i*m+j;
if((s&(1<<k)) != 0) {
cur = cur*10 + a[i][j];
} else {
sum += cur;
cur = 0;
}
}
sum += cur;
}
ans = Math.max(ans, sum);
}
System.out.println(ans);
}
}
댓글남기기