제가 수학 전공은 아니기 때문에 집합, 부분집합에 관한 기본적인 수학적 지식은 넘기고 설명을 하겠습니다.
부분집합은 어떤 집합에 속한 원소들로만 이루어진 집합입니다.
멱집합은 어떤 집합에서 만들 수 있는 모든 부분집합들을 모은 집합입니다.
보통 부분집합을 응용하는 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)
