[알고리즘] 6. 부분집합

1. 부분 집합 합 문제

• 유한 개의 정수로 이루어진 집합이 있을 때, 이 집합의 부분집합 중에서 조건에 맞는 경우를 찾는 문제

1. 완전검색 기법으로 부분집합 합 문제 풀기

→ 우선 집합의 모든 부분 집합을 생성한 후에 각 부분집합의 합을 계산

1. 주어진 집합의 부분집합을 생성하는 방법 알아보기

• 부분집합의 수

1. 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2n제곱
2. 이는 각 원소를 부분집합에 포함시키거나, 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같음

2. 부분 집합 확인 및 생성

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 l in range(2):
					bit[3] = l
					print_subset(bit)

def print_subset(bit):
    for i in range(4):
        if bit[i]: # if i가 0이 아니면
            print(arr[i], end = ' ')
    print(bit)

arr = [7, 5, 8, 1]
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 l in range(3):
                bit[3] = l
                print_subset(bit)

3. 비트 연산

• 비트 연산자
• & : 비트 단위로 AND 연산
• | : 비트 단위로 OR 연산
• << : 피연산자의 비트 열을 왼쪽으로 이동

• : 피연산자의 비트 열을 오른쪽으로 이동

**** << 연산자 활용**

→ 1<<2 : 2n제곱, 즉 원소가 n개일 경우의 모든 부분집합의 수를 의미

**** & 연산자 활용**

→ i&(1<<j) : i의 j번쨰 비트가 1인지 아닌지를 검사

** 비트 연산으로 부분집합을 생성하는 법

arr = [3,6,7,1,5,4]

n = len(arr) # n : 원소의 개수

for i in range(1<<n): # 1<<n : 부분 집합의 개수
	for j in range(n): #원소의 수만큼 비트를 비교함
		if i & (1<<j) : # i의 j번 비트가 1인 경우
			print(arr[j], end=", ")
	print()
print()