[알고리즘] 바이너리 카운팅(Binary Counting)-부분 집합

바이너리 카운팅(Binary Counting)이란?

원소 수에 해당하는 N개의 비트열을 이용한다. n번째 비트값이 1이면 n번째 원소카 포함 되었음을 의미한다. 이는 부분 집합(개수가 정해져 있지 않은 조합)을 구하는 문제에서 활용된다.

구현 코드

# 바이너리 카운팅
arr = [3,6,7,1,5,4]
n = len(arr)

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

💡유사 문제

바이너리 카운팅처럼 각 원소가 포함되는지 아닌지 여부를 배열에 표시하여 부분 집합을 나타내면 효율적으로 문제를 해결할 수 있다.

# power=[50,40,99,5,25,6,37]
       # a ,b ,c ,d ,e ,f ,g

# 서바이벌 게임
# a ~ g 를 두팀으로 나누어서 게임을 하고자 합니다.
# 두 팀으로 나누었을 때, 두 팀의 전투력 차이가 최소를 구하시오.
# 모든 선수는 경기에 참가를 하며, 팀 인원은 자유입니다. (1인팀도 가능)

power=[50,40,99,5,25,6,37] # 전력을 나타내는 배열
check=[0]*7 # 팀에 포함 여부를 0과 1로 나타냄
Min=21e8

def dfs(start,level,sum): # level은 뽑은 사람의 수
    global Min,power
    # 아래의 과정을 재귀 돌 때 마다 매번 확인(팀 인원이 정해져 있지 않으니까)
    against = 0 # 상대 팀의 전력을 더해줄 변수
    for i in range(7):
        if check[i] == 0:
            against+=power[i]
    gap = abs(sum - against) # 우리 팀 전력 - 상대팀 전력의 절댓값
    Min = min(Min,gap)

    if level==6: # 6인 팀(우리), 1인팀(상대)일 때 리턴
        return

    for i in range(start,7):
        check[i] = 1 # i를 우리팀으로 뽑음
        dfs(i+1,level+1,sum+power[i]) # 뽑은 사람을 제외하고(중족 제외) 그 뒤에서
                                      # 더 뽑을 경우를 위해 재귀 돌림
        check[i] = 0 # 원상 복구

dfs(0,0,0) # start,level,sum
print(Min)

• 백준 스타트와 링크도 비슷한 유형의 문제다.