[알고리즘] 부분 수열 (w/ 비트 마스크) - 파이썬

🔹 부분 수열 (Subsequence)

부분 수열은 원 수열의 일부 항을 따서 새로 만든 수열이다. (알고리즘 문제를 풀기 위한 수준까지 생각한다)

예를들면,
[1, 2, 3]의 모든 부분 수열은 [ ], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3] 이다.

 

🔹 부분 수열 만들기

• 완전 검색 기법으로 부분집합을 구한다.

사용된 비트마스크

연산자	의미	적용	적용 의미
<<	피연산자의 비트 열을 왼쪽으로 이동시킨다.	1 << n	비트를 십진수로 나타내면 2n 즉, 원소가 n개일 경우의 모든 부분집합 수
&	AND 연산을 한다.	i & (1 << j)	i의 j번째 비트가 둘다 1이면 리턴

파이썬 코드

def subsequence(arr):
    n = len(arr) # 원소의 개수
    result_list = [] # 생성된 부분 수열 저장
    for i in range(1 << n): # 부분 수열 개수
        subset = [] # 부분수열 담기 위함
        for j in range(n): # 원소의 수만큼 비트를 비교함
            if i & (1 << j):
                subset.append(arr[j]) # 부분 수열 만들기
        result_list.append(subset)
    return result_list

sample_list = [1, 2, 3]

subsequence_list = subsequence(sample_list)
print(subsequence_list) 
# [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

 

🔹 부분 수열 문제 풀기 (BOJ 1182)

보통 부분집합 전체를 구하기 보다는, 특정 조건을 만족하는 부분집합을 구하는 문제가 출제된다.

BOJ 1182 문제는 합이 s가 된는 부분집합 수를 요구한다. 

따라서 위 코드에서 구해진 부분집합을 조건문으로 확인하여 알맞는 결과를 이용할 수 있다. 

n, s = map(int, input().split()) # 리스트 정수의 개수, 부분 수열의 합
arr = list(map(int, input().split())) # 리스트

cnt = 0 # 조건에 맞는 경우 카운트
for i in range(1 << n):
    subset = []
    for j in range(n):
        if i & (1 << j):
            subset.append(arr[j])
    if sum(subset) == s:
        cnt += 1
if s == 0: # s가 0일경우 공집합을 포함하기때문에, 이 경우를 제외한다.
    cnt -= 1
print(cnt)