[코테]11-브루트 포스(비트마스크)

7770 단어 CodingTestCodingTest

비트 연산

  • 비트는 0과 1 밖에 없음, &(and), |(or) , ~(not) , ^(xor)

A=27=11011
A=83=1010011

  • not연산의 경우에는 자료형에 다라 결과가 달라진다.

  • 또한 unsigned, signed에 따라서 보여지는 값은 다르다.

  • shift left(<<)

  • shift right(>>)

  • A<<B (A를 왼쪽으로 B비트만큼 민다)

ㅋㅋㅋㅋ이거 학교 다닐 때 배웠던거네,, 기억이 새록새록ㅜ

  • A<<B는 A * 2^B와 같다
  • A>>B는 A / 2^B와 같다.
  • (A+B) / 2 는 (A+B)>>1로 쓸 수 있다.

비트마스크

  • 정수로 집합을 나타낼 수 있다.
    { 1, 3, 4, 5, 9 } = 2^1 + 2^3 + 2^4 + 2^5 + 2^9
    -> 다섯개의 집합이 있다고 가정.

  • 집합은 중복되는 수가 없다. 없으면 0 있으면 1로 봄.

  • 100011010(2) 으로 표현하는 것.

  • 장점
    1) 공간을 적게 사용한다. -> 정수 1개를 이용해서 표현할 수 있음.
    2) 정수
    3) 복잡도가 O(1) - 검사, 추가, 삭제

만약에 {1,100} = 2^100 + 2^1 이 되면 2^100의 숫자가 너무 크니까 잘 사용 안함.

보통 0부터 N-1까지 정수로 이루어진 집합을 나타낼 때 사용.
1부터 N까지 정수로 이루어진 집합을 사용하는 건 공간이 2배 더 필요하다.
또, 각종 연산을 조금 변형해서 사용해야 한다.
따라서, 0부터 N-1까지로 변형해서 사용하는게 더 좋음.

ex) {1,3,4,5,9} = 570

  • 2가 포함되어 있는지 검사
    해당 숫자를 이진수로 바꾸고 1<<2랑 and연산을 해서 결과값을 보면됨.

  • 비트마스크 S에 X가 있는지 검사?
    S & (1<<X) = 0이면 없음, 0이 아니고 그 (1<<X)의 값이 나오면 있음.

또 다른 방법,

  • ( S >> X ) & 1 이 0인지 1인지 검사해줌
  • S >> X의 0번째 비트 = S의 X번째 비트.
  • 추가하는 연산
    S에 X를 추가 = S의 X번째 비트를 1로 변경
    OR연산을 사용해주면 됨
  • S | (1<<X)
  • 제거하는 연산
    S에서 X를 제거 = 해당 비트를 0으로 만들어주어야 함.
  • 3을 제거하려면
    그 지우려는 부분만 0으로 만들고 나머지는 다 1로 하고 & 연산을 수행함.
  • 없는 수를 지워도 마찬가지로 0이 나옴 왜냐면 원래 0이였으니까 (AND연산이기 때문)

S & ~(1<<X)

토글연산 (0->1) (1->0)
이것도 논리회로 전공수업때 들었던 것,, 기억이 새록새록

  • N개의 수를 저장 : 0~ N-1까지
  • 전체 집합
    (1 << N) -1
  • 공집합
    0

현재 집합이 S일 때

  • i를 추가
    S | ( 1 << i )
  • i를 검사
    S & ( 1 << i )
  • i를 제거
    S & ~( 1 << i )
  • i를 토글
    S ^ ( 1 << i )
  • 비트연산을 사용할 때는 연산자 우선 순위를 생각해야함.
  • 1 << N -1 은 (1<<N)-1일까? 아니면 1<<(N-1)일까?
  • 정답은 1<<(N-1)임.
  • 괄호로 원하는 연산을 묶어주는게 좋은 방법임.

집합

  • 1~20까지 사용하는 것으로 되어있는데 0~19로 사용해주어야함.
  • 물론 배열을 사용하는 것이 더욱 편리하지만, 비트마스크를 사용하는 이유는 집합을 배열의 인덱스로 표현할 수 있기 때문이다.
  • 상태 다이나믹을 할 때 자주 사용하게 된다.
  • 재귀 , 브루트 포스 둘다 사용가능.
  • 단점. 정수.. (장점도 정수라며..)
    => 정수는 32비트, 64비트 주로 사용. 32비트는 0~31 / 64비트에는 0~63까지만 저장.
    적은 개수의 집합에서만 사용하는 것이 좋음.

또 언제 사용?

  • 함수 ( 옵션 1, 옵션 2, 옵션 3)이 있을 때 나중에 옵션 4, 옵션 5, 옵션 6을 추가해야함.
    근데 이 때 옵션을 비트마스크를 이용하면 별도의 처리 없이 추가하면 됨.
  • 집합 문제는 완전 비트마스크 기본문제인 것 같다..
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 br = new BufferedReader(new InputStreamReader(System.in));
		
		StringBuilder sb = new StringBuilder();
		
		int m= Integer.parseInt(br.readLine());
		int s= 0;
		
		while(m-->0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String op= st.nextToken();
			int num;
			
			switch(op) {
            //여기서 num에 -1을 해주는 것은 아까 위에 설명했던 것임.
            // 0~19
			case "add" :
				num=Integer.parseInt(st.nextToken())-1;
				s |= (1<<num);
				break;
			case "remove" :
				num=Integer.parseInt(st.nextToken())-1;
				s = s & ~(1<<num);
				break;
			case "check":
				num=Integer.parseInt(st.nextToken())-1;
				if((s & (1<<num))!= 0) {
					sb.append("1\n");
				}else {
					sb.append("0\n");
				}
				break;
			case "toggle":
				num=Integer.parseInt(st.nextToken())-1;
				s ^= (1<< num);
				break;
			case "all":
				s |= (~0);
				break;
			case "empty":
				s &= 0;
				break;
			}
		}
		System.out.println(sb);
		
	}
}

부분수열의 합

서로 다른 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 문제 (1<=N<=20)

  • N개의 정수로 이루어진 부분수열의 개수를 구하면 됨.

  • 부분 수열의 개수 = 2^N-1

  • 각 부분 수열을 만들고 합을 만듬.

  • (2^N) * N

  • 전체 집합 = (1<<N)-1

  • 크기가 0인 부분수열은 제외.

  • 집합에 무엇이 포함되어 있는지 확인

for(int i=1;i< (1<<n); i++){
for(int k=0; k<n; k++){
if( i&(1<<k) )
}
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 res=0;
		for(int i=1;i< (1<<n);i++) {
			int sum=0;
			for(int j=0;j<n;j++) {
				if( (i&(1<<j)) !=0 )
					sum += a[j];
			}
			if(sum==s) {
				res+=1;
			}
		}
		System.out.println(res);
	}
}

스타트와 링크

~~이거 예전에 풀었던 것임,,, ~~

종이 조각

N * M크기의 종이를 조각으로 잘라서 합의 최대값을 구하는 문제(1<=N, M<=4)

  • 가장 먼저 생각해보아야 하는 것은 ?
    어떻게 종이를 조각으로 자르는 것이 합이 최대가 될 것인가,,
    4개의 조각으로 나누는게 제일 클 것임.
    근데 0이 있을 때를 생각해야함.
  • 브루트 포스로 가능한 모든 방법으로 종이 조각을 나누어 보아야 함.
  • 2개로 나누어 지는 것이 가로조각과 세로조각임.
  • 가로는 0, 세로는 1로 표현한다면 0과 1로 이루어진 NM개의 칸으로 볼 수 있음.
  • NM= 44= 16자리의 비트마스크로 이용하면 됨.

어떤 수를 나누었을 때 ? 원래 수보다 더 커지는 경우는 없음.
각각의 칸에서 가로인지 세로인지 정하면 됨.

1) NM자리의 비트마스크. 모든 방법의 수를 만들어봄
i * m + j를 이용.
2) 수의 합을 구해주면 됨.
각각의 행에 대해서 얼마나 연속되는지, 각각의 열에 대해서 얼마나 연속되는지를 구함.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 str= sc.next();
			for(int j=0;j<m;j++) {
				a[i][j] = str.charAt(j)-'0';
				//문자인 숫자를 원래 숫자로 바꾸려면 문자0을 빼주면 됨.
			}
		}
		
		int res=0;
		
		for(int s=0;s< (1<<(n*m));s++) {
			int sum=0;
			for(int i=0;i<n;i++) {
				int cal=0;
				for(int j=0;j<m;j++) {
					int k=i*m +j;
					if( (s&(1<<k))==0 ) {
						cal = cal * 10 + a[i][j];
						//기존의 숫자 32에 5를 추가하면 32*10 + 5 이런식으로 함.
					}else {
						sum += cal;
						cal =0;
					}
				}
				sum += cal;
			}
			
			for(int j=0;j<m;j++) {
				int cal=0;
				for(int i=0;i<n;i++) {
					int k= i*m+j;
					if( (s&(1<<k))!=0 ) {
						cal = cal*10 + a[i][j];
					}else {
						sum+= cal;
						cal=0;
					}
				}
				sum += cal;
			}
			res = Math.max(res, sum);
		}
		System.out.println(res);
		
	}
}

최백준 선생님의 코딩테스트 기초 강의를 보고 작성한 글입니다.

[Redux] 스토어에서 컴포넌트로 상태값 가져오기 (connect, bindActionCreators, map..ToProps)
TIL Redux

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage