부분집합

안녕하세요 : ) 오늘은 부분집합에 대해 알아보겠습니다.

 

1. 부분집합의 합 문제

유한 개의 정수로 이루어진 집합이 있을 때, 부분집합 중에서 집합의 원소를 모두 더한 값이 0이 되는 경우가 있는지를 알아내는 문제.

완전검색기법으로 부분 집합 합 문제를 풀기 위해서는 먼저 모든 부분집합들을 만든 후 각 부분집합의 합을 계산한다.

각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다. 

따라서 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개이다.

 

bit=[0,0,0,0]
for i in range(2):
  bit[0]=i
  for j in range(2):
    bit[1]=j
    for k in range(2):
      bit[2]=k
      for m in range(2):
        bit[3]=m
        print(bit)

 

 

# 출력결과        
[0, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 1, 0]
[0, 0, 1, 1]
[0, 1, 0, 0]
[0, 1, 0, 1]
[0, 1, 1, 0]
[0, 1, 1, 1]
[1, 0, 0, 0]
[1, 0, 0, 1]
[1, 0, 1, 0]
[1, 0, 1, 1]
[1, 1, 0, 0]
[1, 1, 0, 1]
[1, 1, 1, 0]
[1, 1, 1, 1]

 

for문으로 부분집합을 생성하였다.

bit 리스트는 각 원소를 포함할지 말지를 정하는 리스트이다.

0과 1로 이루어지고 1일때가 원소를 포함한다.

 

2. 비트 연산자

이진수에 대한 연산을 수행하는 연산자이다.

&	비트 단위로 AND연산을 함
|	비트 단위로 OR연산을 함
<<	피연산자의 비트열을 왼쪽으로 이동시킴
>>	피연산자의 비트열을 오른쪽으로 이동시킴

 

arr=[1,2,3,4,5,6]
n=len(arr)    #n은 arr의 원소개수

for i in range(1<<n):   # 1<<n:부분집합의 개수
  for j in range(n):    # 원소의 수만큼 비트를 비교
    if i&(1<<j):        # i의 j번째 비트가 1이면 j번째 원소 출력
      print(arr[j], end=',')
  print()

위의 코드는 비트 연산자를 이용한 부분집합을 구하는 코드이다.

<<연산자는 모든 부분집합의 수를 구할 때도 쓰인다는 것을 알 수 있다.

각 부분집합의 비트를 arr의 길이만큼 반복하면서 비교한다. 

if i&(1<<j)는 방금 본 비트리스트의 개념을 생각하면 이해하기 쉽다.

 

#include<stdio.h>

int main() {
    int i, j;
    int arr[] = { -7, -3, -2, 5, 8 };
    int n = sizeof(arr) / sizeof(arr[0]);       // n: 원소의 개수
    int sum;

    int ret = 0;
    for (i = 1; i < (1 << (n)); i++) {      // 1<<n : 부분집합의 개수
        sum = 0;
        for (j = 0; j < n; j++) {   // 원소의 수만큼 비트 비교
            if (i & (1 << j))  // i의 j번째 비트가 1이면 j번째 원소 출력
            {
                sum += arr[j];
            }
        }
        if (sum == 0)
        {
            ret = 1;
            break;
    }
    }
    printf("%s\n", ret ? "True" : "False");
}

// by SW expert academy

 

부분집합의 합이 0이 되는 경우 True

 

 

참고하면 좋은 곳 👉

https://itzjamie96.github.io/2020/10/15/python-bitwise-powersets/

[Python] 비트연산자로 부분집합 구하기 - Code with Jamie