부분집합

부분집합과 조합

부분집합(subset)이란 모든 원소가 다른 집합에 포함되는 집합을 말합니다.
예를들어 1, 2 는 모든 원소가 1, 2, 3 에 포함되므로 1, 2, 3 의 부분집합이 됩니다.

모두 알다시피 집합은 간단히 다음과 같은 특징을 가집니다.

1. 집합의 원소들은 중복되지 않는다.
2. 집합은 순서에 따른 구분을 가지지 않는다.

위와 같은 특징 때문에 집합에서 부분집합을 구한다는 것은 조합을 구하는 것이라고 할 수 있습니다.
집합의 원소의 총 개수가 n개라고 할 떄 r개의 원소를 가지는 부분집합의 수는 따라서 $nCr$ 과 같습니다.

멱집합

멱집합이란 집합의 모든 부분집합을 모아놓은 집합을 말하며 영어로는 power set 이라고 합니다.
집합이 n개의 원소를 가질 때 멱집합은 $2^n$개입니다.

예를 들어, {1, 2, 3} 이라는 집합이 있을 때 멱집합은 다음과 같습니다.

1. $\emptyset$
2. 1
3. 2
4. 3
5. 1, 2
6. 1, 3
7. 2, 3
8. 1, 2, 3

멱집합을 구하는 알고리즘은 재귀를 사용하여 간단하게 구현할 수 있습니다.
아이디어는 다음과 같습니다.

1. 재귀함수를 사용하여 매 반복마다 하나씩 원소를 순회한다.
2. 매 반복시기마다 집합의 해당 원소를 부분집합에 포함시킬지, 포함하지 않을지 선택하여 분기를 나눈다.
3. 매 선택마다 count를 증가시켜 모든 원소의 순회가 끝난 것인지 판단하고, 끝났다면 포함시킨 원소들만 출력한다.

위 아이디어를 바탕으로 간단히 작성한 예제코드는 아래와 같습니다.

public class Test {
    public static void main(String[] args) {
        int[] input = new int[]{1, 2, 3}; // 전체 집합
        powerSet(input, new boolean[input.length], 0);
    }
    
    // 멱집합
    // input: 입력받은 집합
    // isSelected: 부분집합에서 원소의 선택 여부 기록
    // count: 집합의 index 확인
    public static void powerSet(int[] input, boolean[] isSelected, int count) {
        if (count == input.length) {
            // 모든 선택이 끝난 경우 출력
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < input.length; i++) {
                if (isSelected[i])
                    sb.append(input[i]).append(" ");
            }
            if (sb.length() == 0)
                System.out.println("empty"); // 공집합
            else
                System.out.println(sb);
            return;
        }
        
        // 현재 원소를 부분집합으로 선택
        isSelected[count] = true;
        powerSet(input, isSelected, count + 1);

        // 현재 원소를 부분집합으로 선택하지 않음
        isSelected[count] = false;
        powerSet(input, isSelected, count + 1);
    }
}

위 코드는 아래와 같이 출력됩니다.

1 2 3
1 2
1 3
1
2 3
2
3
empty

정리

• 멱집합을 구하거나, 멱집합의 개수를 필요로 할 때 위 알고리즘을 사용하면 유용합니다.
• 공집합을 포함하게 되므로, 공집합인 경우가 필요없다면 반드시 예외처리를 해주어야 합니다.
• 각 원소마다 분기점을 나누기 때문에 $O(2^n)$의 시간복잡도를 가지게 됩니다.
  따라서 n이 큰 경우에는 시간초과가 나지 않도록 적절히 가지치기를 하는 것이 좋겠습니다.

연습문제

• 백준 - 부분수열의 합