내일은 알고리즘

오랜만에 다시 쓰는 알고리즘 글입니다.

오늘은 부분집합을 만드는 법에 대해 알아보겠습니다.

제가 수학 전공은 아니기 때문에 집합, 부분집합에 관한 기본적인 수학적 지식은 넘기고 설명을 하겠습니다.

부분집합은 어떤 집합에 속한 원소들로만 이루어진 집합입니다.

멱집합은 어떤 집합에서 만들 수 있는 모든 부분집합들을 모은 집합입니다.

보통 부분집합을 응용하는 PS는 이런 멱집합을 구하고 풀이하는 경우가 많습니다.

N개의 원소를 가진 집합의 부분집합의 개수는 2^N개입니다.

부분집합을 만들 때 집합의 어떤 원소를 넣던가 넣지 않던가 두 가지 선택이 가능하고 이런 원소가 N개 있으므로 2^N개의 부분집합이 생기는 것도 당연할 겁니다.

멱집합을 만드는 코드도 이 아이디어를 이용해서 진행합니다.

1~6까지의 숫자를 가진 집합이 있다고 생각해 봅시다.

이 집합의 부분집합으로 하나의 원소를 가진 부분집합 {1}, 여러 원소를 가진 부분집합 {1,2,3}, 공집합 { }, 집합 전체와 같은  {1,2,3,4,5,6}등 여러 종류가 있을 겁니다.

위에서 얻은 아이디어대로 하나의 원소를 넣고 빼는 두 가지 경우를 체크하며 부분집합을 만들어 봅시다.

6개의 원소가 있는 집합이지만 첫 번째 원소 1만 가졌다고 생각해 봅시다.

이 집합의 부분집합은 1이 들어있거나 안 들어있는 두 가지 경우로 나뉩니다.

이 두가지 경우에 대해 우리는 {1}과 { }라는 두 개의 부분집합을 만들 수 있습니다.

두 번째 원소 2를 더해 생각해볼까요?

1과 2 두 개의 원소를 가진 집합의 부분집합은 앞에서 구한 부분집합들에 2가 들어가거나 안 들어가는 두 가지 경우로 생각할 수 있습니다.

즉 우리는 {1,2} {1}, {2}, { }라는 4개의 부분집합을 얻을 수 있습니다.

집합의 원소가 늘어날 때마다 부분집합의 개수는 2배로 늘어나는 것이죠.

3을 포함시켜 {1,2,3}이라는 집합의 부분집합을 구해본다면 앞에서 구한 {1,2} {1}, {2}, { } 4개의 부분집합에 3이 들어가거나 안 들어가는 두 가지 경우로 {1,2,3} {1,3}, {2,3}, {3}, {1,2} {1}, {2}, { } 8개의 부분집합을 만들 수 있을 겁니다.

이렇게 구한 모든 부분집합의 집합을 멱집합이라고 부릅니다.

이 진행과정을 Java와 Python 두 개로 구현해 보았습니다.

부분집합, 조합, 순열 등의 개념을 응용하는 문제는 무척 많기 때문에 익숙해지시면 유용하게 쓰실 수 있습니다.

Java

public class algo_01_subset {
	static int[] number = {1,2,3,4,5,6};
	static int size = 6;
	public static void main(String[] args) {
		makeSubset(0, new boolean[size]);
	}
	
	public static void makeSubset(int idx, boolean[] used) {
		if(idx == size) {
			printSubset(used);
			return;
		}
		
		used[idx] = false;
		makeSubset(idx+1, used);
		used[idx] = true;
		makeSubset(idx+1, used);
	}
	
	public static void printSubset(boolean[] used) {
		StringBuilder sb = new StringBuilder();
		sb.append("{ ");
		for(int i = 0; i < size; i++) {
			if(used[i]) {
				sb.append(number[i]).append(" ");
			}
		}
		sb.append("}");
		
		System.out.println(sb.toString());
	}
}

Python

def makeSubset(idx, used):
    global size
    if(idx == size):
        printSubset(used)
        return
    
    used[idx] = False
    makeSubset(idx+1, used)
    used[idx] = True
    makeSubset(idx+1, used)

def printSubset(used):
    global size
    global number
    msg = "{ "
    for i in range(0,size):
        if(used[i]):
            msg += str(number[i])
            msg += " "
    msg += "}"
    print(msg)

number = [1,2,3,4,5,6]
size = 6

makeSubset(0, [False]*size)