경험의 기록

비트 연산자 종류

비트연산자 설명
& 비트 단위 AND 연산 ( 비트가 모두 1이면 1 반환 )
| 비트 단위 OR 연산 ( 비트중 하나이상 1이면 1 반환 )
^ 비트 단위 XOR 연산 ( 비트가 서로 다르면 1 반환 )
~ 비트 단위 NOR 연산 ( 0 -> 1, 1 -> 0 반환 )
<< 비트 Left Shift 연산 ( 비트를 왼쪽으로 이동 )
>> 비트 Right Shift 연산 ( 비트를 오른쪽으로 이동 )

위 비트 연산자들을 이용하여

쉽게 집합의 부분집합을 구할 수 있다.

 

부분 집합의 수

{1, 2, 3}

집합이 존재한다고 치면, 부분 집합의 개수는

1 포함여부 (2) , 2 포함여부 (2), 3 포함여부 (2) => 2*2*2 = 8개 이다. (공집합 포함)

 

직접 나열해보면 {}, {1}, {1,2}, {1,3}, {2}, {2,3}, {3}, {1,2,3} 으로 8개인 것을 확인할 수 있다. 

즉 원소의 개수가 n이라면 집합의 부분집합 수는 2의 n승이다.

 

이것을 비트 연산자로

1 << n

으로 나타낼 수 있다.

예를 들어 위에서 사용한 집합에서 n은 3

 

1을 이진수로 나타냈을 때

0 0 0 1

n(3) 만큼 왼쪽으로 비트를 이동시키면

1 0 0 0

1000 으로 8이 되는 것을 확인할 수 있다.

 

 

부분 집합 구하기

public class Solution {
	
    public static void main(String[] args) throws IOException{
    	int[] arr = new int[]{1,2,3};
		int n = arr.length;
		
		System.out.println(1 << n);
		
		for(int i = 0; i < (1<<n); i++) {
			for(int j = 0; j < n; j++) {
				if((i & (1<<j)) != 0) {
					System.out.print(arr[j] + ", ");
				}
			}
			System.out.println();
		}
    }
}

위와 같이 0 ~ 7 ( 0~부분집합수-1) 까지 내부 원소들을 & 연산하여 포함되있을 때 전부 출력함으로써

쉽게 부분집합을 생성할 수 있다.

 

백준 1182. 부분수열의 합

문제 : https://www.acmicpc.net/problem/1182

 

1182번: 부분수열의 합

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

// [백준] 1182. 부분수열의 합 (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {

    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    	StringTokenizer st = new StringTokenizer(br.readLine());
    	int n = Integer.parseInt(st.nextToken());
    	int s = Integer.parseInt(st.nextToken());
    	int[] arr = new int[n];
    	int result = 0;

    	// 배열 입력
    	st = new StringTokenizer(br.readLine());
    	for(int i = 0; i < n; i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}

    	// 부분 집합 전부 구하기
    	int sum = 0;
    	for(int i = 1; i < (1 << n); i++) {
    		sum = 0;
    		for(int j = 0; j < n; j++) {
    			if( (i & (1 << j)) != 0) {
    				sum += arr[j]; // 부분 집합의 합			
    			}
    		}

    		// 합이 s일 경우
    		if(sum == s) {
    			result++;
    		}
    	}

    	System.out.println(result);
    }
}

이제 위 내용을 바탕으로

부분수열의 합을 구할 수 있다.

반응형

공유하기

facebook twitter kakaoTalk kakaostory naver band
loading