2차원 배열

2차원 배열의 선언

• 2차원 배열 : 1차원 List를 묶어놓은 List
• 2차원 이상의 다차원 List는 차원에 따라 Index를 선언
• 2차원 List의 선언 : 세로길이(행의 개수), 가로길이(열의 개수)를 필요로 함
• Python 에서는 데이터 초기화를 통해 변수선언과 초기화가 가능
• 선언 예시)
  arr = [[0, 1, 2, 3], [4, 5, 6, 7]] (2행 4열의 2차원 List)

[참고]

• 2차원 배열을 input 값으로 받을 때:

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]

ㄴ 리스트 컴프리헨션 사용

배열 순회

• n x m 배열의 n * m 개의 모든 원소를 빠짐없이 조사하는 방법

행 우선 순회

# i 행의 좌표
# j 열의 좌표
for i in range(n):
	for j in range(m):
    	f(array[i][j]) # 필요한 연산 수행

열 우선 순회

# i 행의 좌표
# j 열의 좌표
for j in range(m):
	for i in range(n):
    	f(array[i][j]) # 필요한 연산 수행

지그재그 순회

# i 행의 좌표
# j 열의 좌표

for i in range(n)
	for j in range(m)
    	f(array[i][j + (m - 1 - 2 * j) * (i % 2)])

ㄴ (i % 2) : i가 홀수일 때만 적용, m - 1 - j - j : 크기보다 1 작은 값(m - 1) - j(앞의 j값 상쇄) -j

델타를 이용한 2차 배열 탐색 **

• 2차 배열의 한 좌표에서 4방향의 인접 배열 요소를 탐색하는 방법

• 인덱스 (i, j)인 칸의 상하좌우 칸 (ni, nj)
  

• 코드로 표현

arr[0...N-1][0...N-1] # NxN 배열
di[] <- [0, 1, 0, -1]
dj[] <- [1, 0, -1, 0]
for i: 0 -> N-1
	for j: 0 -> N-1
    	for k in range(4)
        	ni <- i + di[k]
            nj <- j + dj[k]
            if 0 <= ni < N and 0 <= nj < N # 유효한 인덱스면
            	f(arr[ni][nj])

전치 행렬

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

for i in range(3):
    for j in range(3):
        if i < j:
            arr[i][j], arr[j][i] = arr[j][i], arr[i][j]

부분집합 합

부분집합의 수

• 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개 이다.
• 이는 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다.
• 예)
  

비트 연산자

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

<< 연산자

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

& 연산자

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

부분집합을 생성하는 방법

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()