알고리즘의 기본적인 스킬을 다룹니다.

이번 포스트에서는 알고리즘의 스킬 중 부분집합(Subset)에 대해서 알아 보려고 합니다.
목차는 다음과 같습니다.

1. 배열체크로 부분집합 구하기
2. 비트마스크로 부분집합 구하기
3. 관련 알고리즘 문제


Subset 배열체크

부분집합이라는 단어는 고등학생때 많이 들어봤던 것 같습니다.
일단 부분집합에 대해서 간단하게 알아 보도록 하죠.
원소의 개수가 N일때, 부분집합의 개수는 2^N 입니다.

어떻게 그럴까요?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
원소의 개수가 {1, 2} 라고할 때, 다음과 같이 부분 집합이 나올 수 있습니다.
∅
1
2
1, 2

총 개수 : 4개


원소의 개수가 {1, 2, 3} 라고할 때, 다음과 같이 부분 집합이 나올 수 있습니다.
∅
1
2
3
1, 2
1, 3
2, 3
1, 2, 3

총 개수 : 8개

그렇다면 이제 코드로 한번 작성해서 확인해 보도록 하겠습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.Scanner;

public class Subset_Visit {
    static int N, totalCnt; // 원소의 개수, 총 경우의 수
    static int[] inputs;
    static boolean[] visit;

    public static void main(String[] args) {
        // 부분 집합을 구하기 위해서 원소 입력
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        inputs = new int[N];
        visit = new boolean[N];
        for (int i = 0; i < N; i++) {
            inputs[i] = sc.nextInt();
        }

        // 부분집합 시작
        getSubset(0);

        // 출력
        System.out.println("총 경우의 수 : " +  totalCnt);
    }

    private static void getSubset(int cnt) {
        // cnt가 원소의 개수만큼 돌았다면
        if(cnt == N){
            totalCnt++;
            for (int i = 0; i < N; i++) {
                // 선택된 배열과 선택되지 않은 배열 출력
                System.out.print((visit[i] ? inputs[i] : "X") + "\t");
            }
            System.out.println();
            return;
        }

        // 현재 원소를 선택하고 다음
        visit[cnt] = true;
        getSubset(cnt+1);

        // 현재 원소를 선택하지 않고 다음
        visit[cnt] = false;
        getSubset(cnt+1);
    }
}

위 코드를 실행해보면 아래와 같은 결과를 얻을 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
4
1 2 3 4
1	2	3	4	
1	2	3	X	
1	2	X	4	
1	2	X	X	
1	X	3	4	
1	X	3	X	
1	X	X	4	
1	X	X	X	
X	2	3	4	
X	2	3	X	
X	2	X	4	
X	2	X	X	
X	X	3	4	
X	X	3	X	
X	X	X	4	
X	X	X	X	
총 경우의 수 : 16



Subset 비트마스킹

위에서 봤던 방문배열을 사용하게 되면 원소의 개수가 커졌을 때, 메모리 사용량이 많이 들어갈 수 있습니다.
이번에는 비트마스킹을 이용해서 부분집합을 구해 보도록 하겠습니다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.Scanner;

public class Subset_Bitmask {
    static int N; // 원소의 개수
    static int[] inputs;

    public static void main(String[] args) {
        // 부분 집합을 구하기 위해서 원소 입력
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        inputs = new int[N];
        for (int i = 0; i < N; i++) {
            inputs[i] = sc.nextInt();
        }

        // 부분집합 시작
        getSubset(1 << N);

        // 출력
        System.out.println("총 경우의 수 : " +  (1 << N));
    }

    private static void getSubset(int cnt) {
        for (int flag = 0; flag < cnt; flag++) {
            // 0, 1, 2 ... flag 비트열 별로 원소 수만큼 각 자리 비트를 확인
            for (int i = 0; i < N; i++) {
                System.out.print((((flag & (1 << i)) != 0) ? inputs[i] : "X") + "\t");
            }
            System.out.println();
        }
    }
}

위 코드의 실행 원리를 예시를 들며 설명 하겠습니다.

2개의 원소가 있다고 가정하면 총 경우의 수는 4.
8을 Binary로 표현하면 1 0 0 이며, 4번을 돌며 각자리 입력 받은 원소의 개수만큼 비트 이동을 합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
flag -> 0 = 0 0 일때
i -> 0 = (1 << 0) = 01,      flag & i => 0
i -> 1 = (1 << 1) = 10,      flag & i => 0

따라서 X, X 로 표현 됩니다.


flag -> 1 = 0 1 일때
i -> 0 = (1 << 0) = 01,      flag & i => 1
i -> 1 = (1 << 1) = 10,      flag & i => 0

따라서 1, X 로 표현 됩니다.


flag -> 2 = 1 0 일때
i -> 0 = (1 << 0) = 01,      flag & i => 0
i -> 1 = (1 << 1) = 10,      flag & i => 1

따라서 X, 1 로 표현 됩니다.


flag -> 3 = 1 1 일때
i -> 0 = (1 << 0) = 01,      flag & i => 1
i -> 1 = (1 << 1) = 10,      flag & i => 1

따라서 1, 2 로 표현 됩니다.

위 코드를 실행해보면 아래처럼 결과가 나오는 것을 확인 할 수 있습니다.

1
2
3
4
5
6
7
2
1 2
X	X	
1	X	
X	2	
1	2	
총 경우의 수 : 4



이렇게 부분집합에 대해서 알아 보았습니다.
그럼 관련 알고리즘 문제 링크를 걸어드리며 마무리 짓도록 하겠습니다. 감사합니다.😁

관련 알고리즘 문제

  부분수열의 합