부분 집합 이론 정리

문제

A,B,C 로 구성할 수 있는 부분집합을 모두 구하시오.

해결 방법

부분집합의 모든 경우의 수가 2^(원소의 개수) 인 것은 학교에서 배우는 내용이다.

코딩 문제에서도 부분집합과 순열, 조합의 경우 해당 개념을 사용하는데, 그 이유는 다음 사진과 같다.

A,B,C를 각각 on off 개념으로 1,0 으로 나타낼 수 있다.

즉, 파이썬에서는 for i in range(2**3) 으로 모든 부분집합을 구할 수 있는 것이다.

예시 코드

비트를 사용하여 부분집합을 구하는 예시입니다.

# 비트를 활용한 부분집합 구하기
letters = ['a', 'b', 'c']

for i in range(1 << len(letters)):  # 총 2³, 8개의 경우의 수 체크
    selected = []
    for j in range(len(letters)): # 각각 비트를 한칸씩 옮기며 대조
        if i & (1 << j):  # 1칸씩 왼쪽으로 옮겨가며 총 3칸을 대조해본다.
            selected.append(letters[j]) # 대조 결과가 성공이라면 selected에 append!

    print(selected)

# []                | => (i = 0) => 0 0 0 => 공집합
# ['a']             | => (i = 1) => 0 0 1 => (j = 0)에서 걸려 'a'가 뽑힘
# ['b']             | => (i = 2) => 0 1 0
# ['a', 'b']        | => (i = 3) => 0 1 1
# ['c']             | => (i = 4) => 1 0 0 => (j = 2)에서 걸려 'c'가 뽑힘
# ['a', 'c']        | => (i = 5) => 1 0 1
# ['b', 'c']        | => (i = 6) => 1 1 0
# ['a', 'b', 'c']   | => (i = 7) => 1 1 1