부분 집합 알고리즘(Subset)과 예제

포스팅에서 다룰 주제는 부분 집합 알고리즘입니다. 부분 집합(PowerSet, SubSet)의 개념과 루프를 이용하는 법과 비트 연산자를 이용하는 2가지 방법으로 부분 집합의 알고리즘 구현, 부분 집합의 개수 구하는 법과 공식, 부분 집합의 합 구하기 알고리즘 문제까지 알아보겠습니다.

 

부분 집합이란?

부분 집합 A는 모든 원소가 집합 B에도 속하는 집합입니다.

예를 들면 집합 A = {2, 4}는 집합 B = {2, 4, 6}의 부분 집합입니다.

 

집합의 부분 집합의 총 개수

• 집합의 원소의 개수가 n개일 때, 공집합을 포함한 부분 집합의 개수는 2ⁿ 개입니다.
• 각 원소를 부분 집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같습니다.
  ex) {1, 2, 3, 4} > 2 x 2 x 2 x 2 = 2⁴ = 16 개

 

부분 집합 알고리즘

1. Loop를 이용하여 부분 집합을 생성하는 방법

• bit 리스트 - 대상 리스트의 각 원소를 포함할지 말지 결정하는 리스트 (0=미포함, 1=포함)
• 첫번째 for 문 - 0번째 원소를 보여줄 지 말 지 2(2¹)가지 조합 생성
  [0] / [1] -> { }, {1}
• 두번째 for 문 - 1번째 원소를 보여줄 지 말 지 4(2²)가지 조합 생성
  [0, 0] / [0, 1] -> { }, {2}  /  [1, 0] / [1, 1] > {1}, {1, 2}

bit = [0, 0]
for i in range(2):
    bit[0] = i          # 0번째 원소
    for j in range(2):
        bit[1] = j      # 1번째 원소
        print(bit)      # 부분 집합 출력

 

2. 비트 연산자를 이용하여 부분 집합을 생성하는 방법

• 비트 연산자 - 0과 1로 이루어진 이진수에 대한 연산을 수행하는 연산자
• << 연산자 - 피연산자의 비트 열을 왼쪽으로 이동시킴
  1 << n : 2ⁿ -> 원소가 n개일 경우 모든 부분 집합의 개수
• & 연산자 - 비트 단위로 AND 연산을 함
  i & (1<<j) : 1 -> i에서 j번 째 비트가 1인지 아닌지를 리턴함

1. 부분 집합의 개수만큼 반복
2. 원소의 수만큼 비트를 비교하여 원소의 포함 여부 판단
3. i의 j번째 비트가 1이면 j번째 원소 출력

set = [2, 7, 1, 4]
n = len(set)  # n: 원소의 개수

for i in range(1 << n):
    for j in range(n):
        if i & (1 << j):
            print(set[j], end=", ")
    print()

 

부분 집합의 합 구하기 문제

부분집합 합 알고리즘 예제입니다.

[Python] SW Expert Academy - 4837. 부분집합의 합

[Python] SW Expert Academy - 4837. 부분집합의 합

---

이번 포스팅에서는 파이썬으로 Subset 부분 집합 알고리즘 구현 방법 2가지, Powerset 부분 집합의 개수, 부분 집합의 합 구하기 문제까지 python으로 구현해 보았습니다.