알고리즘 - 부분 집합

완전검색 기법으로 모든 부분집합 합 문제를 풀기 위해서는, 우선 집합의 모든 부분집합을 생성한 후에 각 부분집합의 합을 계산해야 한다. 어떻게 계산할 수 있을까? 

 

부분 집합의 생성

• 부분 집합의 수를 우선 구해보자
• 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개이다.
• 이는 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다.
• 예) {1, 2, 3, 4} -> 2 * 2 * 2 * 2 = 16가지

 

1. 각 원소가 부분집합에 포함되었는지를 loop를 이용하여 확인하고 부분집합을 생성해보자

bit = [0, 0, 0, 0]
for i in range(2):
	bit[0] = i					# 0번째 원소
    for j in range(2):
    	bit[1] = j				# 1번째 원소
        for k in range(2):
        	bit[2] = k			# 2번째 원소
            for l in range(2):
            	bit[3] = 1		# 3번째 원소
                print_subset(bit)		# 생성된 부분집합 출력

 

 비트 연산자

•  & : 비트 단위로 AND 연산을 한다.
•  | : 비트 단위로 OR 연산을 한다.
•  << : 피연산자의 비트 열을 왼쪽으로 이동시킨다.
•  >> : 피연산자의 비트 열을 오른쪽으로 이동시킨다.

 << 연산자

• 1 << n : 2^n 즉, 원소가 n개일 경우의 모든 부분집합의 수를 의미한다.

& 연산자

• 1 & (1<<j) : i의 j번째 비트가 1인지 아닌지를 검사한다.

이를 이용해서 보다 간결하게 부분집합을 생성해보자. -  binary counting

• 원소 수에 해당하는 N개의 비트열을 이용
• n번째 비트값이 1이면 n번째 원소가 포함되었음을 의미

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=", ") 	# j번 원소 출력
    print()
print()

 

하지만 비트연산을 이용하면 시간이 좀 더 오래걸린다는 것을 볼 수 있다.

다만, 착각하면 안되는 것이 비트 연산은 부분집합을 제외한 다른 수의 연산에서는 메모리, 시간적으로 효율이 아주 좋다.

 

 

반복문, 재귀로도 부분집합을 구할 수 있으므로 코드보고 따라 해보자!!

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

subsets = [[]]

for num in arr:
  size = len(subsets)
  for y in range(size):
    subsets.append(subsets[y]+[num])
print(subsets)

 

 

간단하게 완전검색 해를 구하기 위한 방법 중 부분집합에 대해 알아보았다.

다음 글에서는 완전검색이 아닌 다른 검색들에 대해 배워보자!!