[Java] 부분집합

 

종류	설명	기호	시간 복잡도
순열	N개의 원소 중 R개의 원소로 순서를 가진 부분집합을 만드는 경우의 수	nPr	O(N!)
조합	N개의 원소 중 R개의 원소로 부분집합을 만드는 경우의 수	nCr	O(n! /( r! x (n-r)!))
부분집합	N개의 원소로 부분집합을 만드는 모든 경우의 수	nHr	O(2^N)

 

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

 

• 멱집합 (Power set)
  • 주어진 집합의 모든 부분 집합들로 구성된 집합

 

원소들의 그룹에서 최적의 부분 집합을 찾는 문제가 많다.

 

[알고리즘] 5215. 햄버거 다이어트

(knapsack - 햄버거 다이어트)

 

---

1. 반복문

for i in 1 -> 0
    selected[1] <- i
    for j in 1 -> 0
        selected[2] <- j
        for k in 1 -> 0
            selected[3] <- k
            for m int 1 -> 3
                if selected[m] == 1 then
                    print m            

---

2. 재귀 함수

input[]
isSelected[]

generateSubset(cnt)
    if(cnt == N)
        for m int 1 -> N
            if selected[m] == 1 then
                print m
    else
        isSelected[cnt] <- true
        generateSubset(cnt + 1)
        isSelected[cnt] <- false
        generateSubset(cnt + 1)

import java.util.Scanner;

// N개의 원소를입력받아 가능한 모든 부분집합 생성
// 1<=N<=10
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);

        sc.close();
    }

    private static void generateSubSet(int depth) {
        // 완성
        if(depth == N) {
            StringBuffer sb = new StringBuffer();
            for(int i=0; i<N; i++) {
                sb.append(isSelected[i] ? input[i] : "X").append("  ");
            }
            System.out.println(sb);
            return;
        }

        isSelected[depth] = true; // 포함
        generateSubSet(depth + 1);
        isSelected[depth] = false; // 미포함
        generateSubSet(depth + 1);
    }

}

N개의 원소를 입력받아 가능한 모든 부분집합 생성하는 코드.

 

---

3. 부분집합의 합

import java.util.Scanner;

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

    static int N, target, input[];
    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);

        sc.close();
    }

    private static void generateSubSet(int depth, int sum) {

        if(depth == N) { // 부분집합의 합이 목표합인지 확인
            if(sum!=target) return;
            StringBuffer sb = new StringBuffer();
            for(int i=0; i<N; i++) {
                if(isSelected[i]) sb.append(input[i]).append(" ");
            }
            System.out.println(sb);
            return;
        }

        isSelected[depth] = true;
        generateSubSet(depth + 1, sum + input[depth]);
        isSelected[depth] = false;
        generateSubSet(depth + 1, sum);
    }

}

N개의 원소를 입력받고 모든 원소의 합이 목표합과 같은 부분집합을 찾는 코드.

 

3040번: 백설 공주와 일곱 난쟁이

 

---

4. 바이너리 카운팅

 

가. 비트 연산

연산자	기능
&	비트 AND 연산자. 두 비트가 모두 1이면 1을 반환하고, 그렇지 않으면 0을 반환한다.
^	비트 XOR 연산자. 두 비트가 서로 다르면 1을 반환하고, 같으면 0을 반환한다.
~	비트 NOT 연산자. 비트를 반전시킨다. 0은 1로, 1은 0으로 변환된다.
<<	왼쪽 시프트 연산자. 비트를 왼쪽으로 지정된 수만큼 이동시킨다.
>>	부호 있는 오른쪽 시프트 연산자. 비트를 오른쪽으로 지정된 수만큼 이동시킨다.
>>>	부호 없는 오른쪽 시프트 연산자. 비트를 오른쪽으로 지정된 수만큼 이동시킨다.

 

• 1<<n : 최하위 1비트를 오른쪽에서 n번 떨어진 위치로 옮긴다.
• value & 1<<n : value에서 n번째 비트의 값을 거져오는 방법. (마스크 오프)
• value | 1<<n : value에서 n번째 비트의 값을 1로 설정하는 방법. (마스크 온)

 

비트 하나는 2가지 상태를 표현할 수 있다.

 

이러한 특성을 활용해서 방문 여부, 선택 여부를 저장하기 위해서 사용할 수 있다.

 

공간복잡도 측면에서 압도적으로 유리하다.

 

시간복잡도 측면에서는 불리할 수 있다.

 

대략 27개 이하(2^27 = 연산 1억 = 1초) + 공간복잡도가 중요한 문제 → 비트마스킹.

(참고로 알파벳 개수가 26개다.)

 

[알고리즘] 11723. 집합

(비트마스킹 활용 기초)

---

나. 바이너리 카운팅

 

원소 수에 해당하는 N개의 비트열을 이용한다.

 

n번째 비트값이 1이면 n번째 원소가 포함되었음을 의미.

 

int arr[] = {3, 6, 7, 1, 5, 4};
int n = arr.length;

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();
    }
}

가지치기를 효율적으로 할 수 있다면 재귀 함수로 구현하는 것이 더 빠를 수 있다.

 

---