[알고리즘] [8] 부분 집합

1. 부분 집합

• 집합에 포함된 원소들을 순서 없이 택하는 것
• 집합에서 최적의 부분 집합을 찾는 알고리즘이 많다.
  >> ex. 배낭 (knapsack)
• 재귀로 부분 집합을 생성할 수 있다.

import java.util.Scanner;

public class PowerSetTest {
	static int n, input[];
	static boolean isSelected[];
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		
		input = new int[n];
		
		isSelected = new boolean[n];
		
		for (int i = 0; i < n; i++) {
			input[i] = sc.nextInt();
		}
		generateSubSet(0);
	}
	
	private 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);
		
	}
}

 

2. 비트 연산

연산자	기능
&	비트 단위 AND 연산
|	비트 단위 OR 연산
^	비트 단위 XOR 연산 (같으면 0, 다르면 1)
~	단항 연산자로서 피연산자의 모든 비트를 반전
<<	피연산자의 비트 열을 왼쪽으로 이동
>>	피연산자의 비트 열을 오른쪽으로 이동

* 중요 연산자

• &과 <<를 같이 사용하는 경우, 기존 상태 비트열 중 내가 원하는 비트 자리의 상태를 확인할 수 있다.
• |과 <<를 같이 사용하는 경우, 기존 상태 비트열에 내가 원하는 비트 자리 상태를 추가 (set)한다.

---

3. 바이너리 카운팅 (Binary Counting)

• 원소 수에 해당하는 N개의 비트열을 이용하여 n번째 비트열이 1이면 그 원소를 포함하는 것으로 판단한다.