2차원 배열 순회, 부분 집합(비트 연산)

박성재·2021년 2월 16일

알고리즘 파이썬

알고리즘 공부

목록 보기

8/9

배너: godori님이 만드신 배너 메이커 활용

2차원 배열 접근

변수 선언 및 초기화 (m x n 행렬 정의)

m, n = 3, 4
arr2d = [[0] * n for _ in range(m)]

0 0 0 0
0 0 0 0
0 0 0 0

행 우선 순회

cnt = 1
# i 행의 좌표, j 열의 좌표
for i in range(len(arr2d)):
    for j in range(len(arr2d[0])):
        arr2d[i][j] = cnt
        cnt += 1

1 2 3 4
5 6 7 8
9 10 11 12

열 우선 순회

cnt = 1
for j in range(len(arr2d[0])):
    for i in range(len(arr2d)):
        arr2d[i][j] = cnt
        cnt += 1

1 4 7 10
2 5 8 11
3 6 9 12

지그재그 순회

# cnt = 1
# for i in range(len(arr2d)):
#     for j in range(len(arr2d[0])):
#         if i % 2:
#             arr2d[i][len(arr2d[0])-1-j] = cnt
#         else:
#             arr2d[i][j] = cnt
#         cnt +=1

cnt = 1
for i in range(len(arr2d)):
    for j in range(len(arr2d[0])):
    	# 행에 따라서 열에 다르게 접근
        arr2d[i][j + (len(arr2d[0])-1-2*j) * (i%2)] = cnt
        cnt += 1

1 2 3 4
8 7 6 5
9 10 11 12

델타를 이용한 2차원 배열 탐색 (달팽이)

# 우하좌상 순서 델타
dr = [0, 1, 0, -1] # 행 델타
dc = [1, 0, -1, 0] # 열 델타

cnt = 1
r, c = 0, 0
d = 0
for i in range(len(arr2d)):
    for j in range(len(arr2d[0])):
        arr2d[r][c] = cnt
        r += dr[d]
        c += dc[d]
        # 범위를 벗어나거나 이미 방문했다면
        if not (0 <= r < len(arr2d) and 0 <= c < len(arr2d[0])) or arr2d[r][c] != 0:
            # 뒤로 한 칸 이동
            r -= dr[d]
            c -= dc[d]
            # 방향 틀기
            d = (d+1) % 4
            # 한 칸 이동
            r += dr[d]
            c += dc[d]
        cnt += 1

1 2 3 4
10 11 12 5
9 8 7 6

행렬 전치

# i: 행의 좌표, len(arr)
# j: 열의 좌표, len(arr[0])
arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

1 2 3
4 5 6
7 8 9

for i in range(3):
    for j in range(3):
        # 대각 기준으로 위 쪽 위치에서만 대칭인 요소와 swap
        # 대각 기준으로 반대편에서도 swap을 해주면 결국 처음과 같아지기 때문
        if i < j:
            arr[i][j], arr[j][i] = arr[j][i], arr[i][j]

1 4 7
2 5 8
3 6 9

부분집합 합 문제(완전 검색)

유한한 수의 정수로 이루어진 집합이 있을 때, 이 집합의 부분집합 중에서 그 집합의 원소를 모두 더한 값이 0이 되는 경우가 있는지를 알아내는 문제
예를 들어, \scriptsize[-3, 5, -6, -2]이라는 집합이 있을 때, [-3, 5, -2]은 이 집합의 부분집합이면서 (-3) + (5) + (-2) = 0 이므로 이 경우 답은 참이 된다.

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

부분집합의 수: 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 ${2^n}$ 개다.

arr = [-3, 5, -6, -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
                subset = [arr[n] for n in range(len(bit)) if bit[n] == 1]
                print(subset, end=' ')

[][-2] [-6][-6, -2] [5][5, -2] [5, -6][5, -6, -2] [-3][-3, -2] [-3, -6][-3, -6, -2] [-3, 5][-3, 5, -2] [-3, 5, -6][-3, 5, -6, -2]

위와 같은 방식으로 코드를 작성할 수 있겠지만, 원소의 개수가 늘어나는 만큼 for 문이 중첩되어 원소의 개수가 유동적인 경우 코드 작성이 어렵다.

비트 연산

비트 연산자

&: 비트 단위로 AND 연산을 한다.

4 & 6 = 4
4 $\scriptsize{(100_2)}$ & 6 $\scriptsize{(110_2)}$ = 4 $\scriptsize{(100_2)}$

|: 비트 단위로 OR 연산을 한다.

4 | 6 = 6
4 $\scriptsize{(100_2)}$ | 6 $\scriptsize{(110_2)}$ = 6 $\scriptsize{(110_2)}$

<<: 피연산자의 비트 열을 왼쪽으로 이동시킨다.

5 << 1 = 10
5 $\scriptsize{(101_2)}$ << 1 = 10 $\scriptsize{(1010_2)}$

>>: 피연산자의 비트 열을 오른쪽으로 이동시킨다.

8 >> 1 = 4
8 $\scriptsize{(1000_2)}$ >> 1 = 4 $\scriptsize{(100_2)}$

a << b 연산은 a라는 숫자에 2를 b번 곱해준 결과와 같다.
따라서1 << n은 ${2^n}$ , 즉 원소가 n개일 경우의 모든 부분집합의 수를 의미한다.

i & (1<<j) 연산은 i의 j번째 비트가 1인지 아닌지를 리턴한다.

12 & (1<<2) = 4
12 $\scriptsize{(1100_2)}$ & (1<<2) $\scriptsize{(0100_2)}$ = 4
12 & (1<<1) = 0
12 $\scriptsize{(1100_2)}$ & (1<<1) $\scriptsize{(0010_2)}$ = 0

비트 연산 이용 완전탐색 코드

비트 연산자를 이용하면 다음과 같이 부분집합을 보다 간결하게 생성할 수 있다.

arr = [4, 2, 1, 3, 5]

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

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

[], [4], [2], [4, 2], [1], [4, 1], [2, 1], [4, 2, 1], [3], [4, 3], [2, 3], [4, 2, 3], [1, 3], [4, 1, 3], [2, 1, 3], [4, 2, 1, 3], [5], [4, 5], [2, 5], [4, 2, 5], [1, 5], [4, 1, 5], [2, 1, 5], [4, 2, 1, 5], [3, 5], [4, 3, 5], [2, 3, 5], [4, 2, 3, 5], [1, 3, 5], [4, 1, 3, 5], [2, 1, 3, 5], [4, 2, 1, 3, 5],

부분집합 합 문제 해결

arr = [-3, 5, -6, -2]

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

for i in range(1<<n): # 부분 집합의 개수만큼 돌면서
    subset = []
    for j in range(n): # 원소의 수만큼 비트를 비교한다
        if i & (1<<j): # i의 j번째 비트가 1이면 j번째 원소를 부분집합에 추
            subset.append(arr[j])
    # 부분집합의 합이 0이고 공집합이 아니면 참
    if sum(subset) == 0 and len(subset) != 0:
        print('참')
        break
        
# 모든 부분집합을 확인했는데도 break 되지 않았다면 거짓
else:
    print('거짓')