부분집합, 비트연산, 바이너리 카운팅

1. 부분집합

  1) 부분집합이란?

    - 집합에 포함된 원소들을 선택하는 것.

    - 다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분 집합을 찾는 것

    - 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개 이다.

 

---

 

2. 부분집합의 합 구하기(재귀)

public static void generateSubSet(int cnt) {

		// 기저 조건
		if (cnt == N) {
			for (int i = 0; i < N; i++) {
				System.out.print((isSelected[i] ? input[i] : "X") + "\t");
			}
			System.out.println();
			return;
		}

		// 유도 파트
		isSelected[cnt] = true; // 부분집합에 포함
		generateSubSet(cnt + 1);
		isSelected[cnt] = false; // 부분집합에 비포함
		generateSubSet(cnt + 1);
	}

package com.algo.day3;

import java.util.Scanner;

// N개의 원소를 입력받아 가능한 모든 부분집합 생성
// 1<=N<=10
public class PowerSetSumTest {

	static int N, input[], target;
	static boolean isSelected[];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		target = sc.nextInt();
		input = new int[N];
		isSelected = new boolean[N];

		for (int i = 0; i < N; i++) {
			input[i] = sc.nextInt();
		}

		generateSubSet(0, 0);
	}

	public static void generateSubSet(int cnt, int sum) { // sum : 기존 부분집합의 구성요소들의 합
		
		// 기저 조건
		if (cnt == N) { // 모든 원소가 고려되었다면 부분집합을 구성하는 원소들의 합이 목표합이 되는지 체크
			if (sum == target) {
				for (int i = 0; i < N; i++) {
					if(isSelected[i]) System.out.print(input[i] + "\t");
				}
				System.out.println();
			}
			return;
		}

		// 유도 파트
		isSelected[cnt] = true; // 부분집합에 포함
		generateSubSet(cnt + 1, sum + input[cnt]);
		isSelected[cnt] = false; // 부분집합에 비포함
		generateSubSet(cnt + 1, sum);
	}
}

 

---

 

 

3. 비트 연산

  1) 비트 연산자

    - shift 연산은 이동 시 <<는 * 2^n, >>는 % 2^n

    - <<, & : 기존 상태 비트열중 내가 원하는 비트자리 상태 확인

    - <<, | : 기존 상태 비트열중 내가 원하는 비트자리 상태 Set

 

---

 

4. 바이너리 카운팅

package com.algo.day3;

import java.util.Scanner;

public class BinaryCountingTest {

	static int[] numbers;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		numbers = new int[N];
		for (int i = 0; i < N; i++) {
			numbers[i] = sc.nextInt();
		}
		subset(N);
	}

	public static void subset(int n) {
		// n의 경우의 수 구하기 2^n
		for (int flag = 0, caseCount = 1 << n; flag < caseCount; ++flag) {
			for (int i = 0; i < n; i++) { // 하나의 경우의 수에 대한 각자리의 비트 체크
				if ((flag & 1 << i) != 0) {
					System.out.print(numbers[i] + "\t");
				}
			}
			System.out.println();
		}
	}

}