[Python] 2차원 배열 - 연산자, 부분집합

• 비트 연산자
  • & : 비트 단위로 AND 연산을 한다.
  • | : 비트 단위로 OR 연산을 한다.
  • << : 피연산자의 비트 열을 왼쪽으로 이동시킨다.
  • >> : 피연산자의 비트 열을 오른쪽으로 이동시킨다.
• << 연산자
  • 1<<n : 2^n 즉, 원소가 n개일 경우의 모든 부분집합의 수를 의미한다.

          ex) 1<<4 가 True면 10000(2)이므로 16, 2^4 = 16

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

# (1<<j)는 j번째 비트만 1

if i&(1<<j):
    print('i의 j번째 비트가 1')
else:
    print('i의 j번째 비트가 0')
    
    
# i가 5라면, 101(2)이므로
# 1<<0 : True
# 1<<1 : False
# 1<<2 : True

 

• 부분집합 생성하는 법

1.

arr = [1,2,3,4]
bit = [0]*4
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] = l      # 3번째 원소
                # 비트 배열을 한 번 채우고 난 후
                for p in range(4):
                    # 부분집합 구하기
                    if bit[p]:
                        print(arr[p], end=' ')
                print()

부분집합

 

2.

arr = [1,2,3,4]
n = len(arr)
for i in range(1<<n): # 1<<n : 부분 집합의 개수
    for j in range(n): # 원소의 수만큼 비트를 비교하기
        if i&(1<<j): 
            # i의 j번 비트가 1인 경우
            # ex)
            # i == 5 == 101(2)이므로
            # 1<<0 : True
            # 1<<1 : False
            # 1<<2 : True 
            print(arr[j], end=' ')
    print()

 

부분집합

 

• 부분 집합 예제(부분집합의 원소의 합이 10이 되는 부분집합 구하기)

1.

# 부분집합의 합이 10
arr = [1,2,3,4,5,6,7,8,9]
N = len(arr)

for i in range(1<<N):
    # 부분집합의 합
    sum_sub = 0
    # 부분집합
    subset = []
    for j in range(N):
        if i&(1<<j):
            sum_sub += arr[j]
            subset += [arr[j]]
    # 부분집합의 원소의 합이 10인가
    if sum_sub == 10:
        print(subset)

원소 합이 10인 부분집합

2. 재귀

# 부분집합의 합이 10
arr = [1,2,3,4,5,6,7,8,9]
N = len(arr)

# 재귀로 풀기
# idx번째 요소가 부분집합에 포함되는지 결정
#selected[] : 각 요소가 부분집합에 포함되는지 표시하는 배열

def solve(idx, selected):
    if idx == N: # 모든 요소(0~N~1번요소까지) 다 결정
        # print(selected)
        sum_sub = 0
        subset = []
        for i in range(N):
            if selected[i]:
                sum_sub += arr[i]
                subset.append((arr[i]))
        if sum_sub == 10:
            print(subset,end=' ')
            print()
        return
        
    # 우리가 해볼 수 있는 모든 경우의 수 고려
    
    # idx 번째 요소를 부분집합에 포함
    selected[idx] = 1
    solve(idx + 1,selected)
    
    # idx 번째 요소를 부분집합에 포함 X
    selected[idx] = 0
    solve(idx + 1, selected)

print(solve(0,[0]*N))