![[Algorithm] 2차원 배열](/_next/image?url=https%3A%2F%2Fblog.huns.site%2Fimgs%2Fthumbnails%2Fblog%2Fposts%2Fcomputer-science%2Falgorithm.png&w=1200&q=75)
TOC
2차원 배열
- 1차원 list를 묶어놓은 list
- 2차원 이상의 다차원 list는 차원에 따라 index를 선언
- Python에서는 데이터 초기화를 통해 변수선언과 초기화 가능
2차원 배열 input 처리
3
1 2 3
4 5 6
7 8 9
입력이 각 행마다 들어오고 열끼리는 공백으로 구분되어 있는 경우
N = int(input)
arr = [list(map(int, input().split())) for _ in range(N)]
.split()을 이용해 공백을 기준으로 항목을 잘라내고, 필요하다면 이를 정수형으로 변환한다.
3
123
456
789
입력이 각 행마다 들어오고 열끼리 공백이 없는 경우
N = int(input())
arr = [list(map(int, input())) for _ in range(N)]
공백이 없고 숫자처럼 보이지만 문자열이므로, map(int, txt)를 통해서 하나하나 떼어내서 정수형으로 하나씩 리스트에 저장할 수 있다.
list comprehension을 사용하는 이유
Q. 그냥 [[0]*3]*4` 처럼 하면 되는 거 아닌가요?
arr = [[0]*3]*4
print(arr)
# [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
arr[0][1] = 1
print(arr)
# [[0, 1, 0], [0, 1, 0], [0, 1, 0], [0, 1, 0]]
얕은 복사이기 때문에 arr[0][1]을 바꾸면 arr[0][1]을 참조하는 arr[1][1] ~ arr[3][1] 까지의 값도 모두 바뀌므로 옳은 방법이 아니다.
2차원 배열의 순회
- n*m 배열의 모든 원소를 빠짐없이 조사하는 방법
- 2중 for문에 대한 이해 필요
행 우선 순회
# i : 행의 좌표
# j : 열의 좌표
for i in range(n):
for j in range(m):
Array[i][j] # 필요한 연산 수행
열 우선 순회
# i : 행의 좌표
# j : 열의 좌표
for j in range(m):
for i in range(n):
Array[i][j] # 필요한 연산 수행
지그재그 순회
# i : 행의 좌표
# j : 열의 좌표
for i in range(n):
for j in range(m):
Array[i][j + (m-1-2*j)*(i%2)] # 필요한 연산 수행
짝수행(i%2==0)일 때는 for j:0 -> m-1까지, 홀수행(i%2==1)일 때는 j: m-1 -> 0까지
짝수행일 때는 정상적으로 A[i][j]를 가져야 하지만, 홀수행일 때는 A[i][m-1-j]의 인덱스로 j가 증가함에 따라 하나씩 줄어들어야 한다.
이때 i%2에 따라 이 둘이 서로 공존해야 하므로, A[i][m-1-j]를 A[i][j + (m-1-j)-j*(i%2)] 로 변환한 것이다. 짝수행일 때는 i가 짝수여서 i%2는 0이므로 뒤의 복잡한 수식을 모두 제거한 A[i][j]가 되고, 홀수행일 때는 i%2가 1이어서 뒤의 식을 앞의 j와 더해 A[i][m-1-j]가 되겠다.
델타를 이용한 2차 배열 탐색
- 2차 배열의 한 좌표에서 4방향의 인접 배열 요소를 탐색하는 방법
- 인접한 요소의 값을 읽어와서 동일한 작업을 반복적으로 수행할 때 적용
- 가독성, 수정, 디버깅에 용이
# N x N 배열
arr[0...N-1][0...N-1]
di[] ← [0, 0, -1, 1] # 좌우상하
dj[] ← [-1, 1, 0, 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): # 유효한 인덱스면
test(arr[ni][nj])
가장 내부 반복을 진행하면서 k가 0, 1, 2, 3으로 바뀌는데, k의 증가에 따라 di[k]와 dj[k]의 증감을 이용해 기준값에 대해 좌표를 이동시키는 것
또는 우하좌상을 0, 1, 2, 3 으로 하여 처리할 수도 있다.
# N x M 배열
arr[0...N-1][0...M-1]
di = [0, 1, 0, -1]
dj = [1, 0, -1, 0]
# 정석
arr = [[1,2,3],[4,5,6],[7,8,9]]
N = 3
for i in range(N):
for j in range(N):
for k in range(4):
ni = i + di[k]
nj = j + dj[k]
if (0 <= ni < N) and (0 <= nj < N): # 유효한 인덱스면
print(arr[ni][nj])
# 또 다른 방법
arr = [[1,2,3],[4,5,6],[7,8,9]]
N = 3
for i in range(N):
for j in range(N):
for di, dj in [(0,1), (1,0), (0, -1), (-1, 0)]:
ni = i + di
nj = j + dj
if (0 <= ni < N) and (0 <= nj < N): # 유효한 인덱스면
print(arr[ni][nj])
print()
물론 개인 기호에 따라 순서는 바꿔도 된다. i와 j의 증감을 확인하는 것은 테이블을 그려서 결정하는 것이 헷갈리지 않는다.
델타를 이용한 예제
5x5 2차 배열에 무작위로 25개의 숫자로 초기화한 후 25개의 각 요소에 대해서 그 요소와 이웃한 요소와의 차의 절대값을 구한다. 25개 요소에 대해서 모두 조사하여 총합을 구한다. 벽에 있는 요소는 이웃한 요소가 없을 수 있음을 주의한다.
arr = [[1,2,3,4,5],
[6,7,8,9,10],
[11,12,13,14,15],
[16,17,18,19,20],
[21,22,23,24,25]] # 5x5 행렬
di = [-1, 0, 1, 0]
dj = [0, 1, 0, -1]
for i in range(5):
for j in range(5):
sum_v = 0
for k in range(4):
ni = i + di[k]
nj = j + dj[k]
if (0<=ni<5) and (0<=nj<5):
k = arr[i][j] - arr[ni][nj]
k = k if arr[i][j] > arr[ni][nj] else -k
sum_v += k
이렇게 벡터에 의해 이동한 행과 열의 인덱스가 최초의 2차원 배열의 인덱스 범위인 0부터 4(5-1) 사이에 위치하는지 조건문으로 한 번 확인하는 것이다. 이 과정이 없으면 경계 부분의 벡터를 적용한 인덱스의 위치에서 IndexError가 발생할 수 있다.
전치 행렬
# i : 행의 개수, len(arr)
# j : 열의 개수, len(arr[0])
arr = [[1,2,3],[4,5,6],[7,8,9]] # 3x3 행렬
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]
열 인덱스가 행 인덱스보다 크다면 대각선을 기준으로 상대되는 인덱스의 값과 바꾼다. pythonic하게!
하지만 이 방법은 모든 항목을 모두 돌아야하기 때문에 N의 크기가 커지면 효율이 떨어진다.
# r : 행의 좌표, len(arr)
# c : 열의 좌표, len(arr[0])
arr = [[1,2,3,4,5],
[6,7,8,9,10],
[11,12,13,14,15],
[16,17,18,19,20],
[21,22,23,24,25]] # 5x5 행렬
N = 5
for r in range(N-1):
for c in range(r+1, N):
arr[r][c], arr[c][r] = arr[c][r], arr[r][c]
이를 조합에도 활용할 수 있다.
arr = 'abcd'
N = len(arr)
for i in range(N-2):
for j in range(i+1, N-1):
for k in range(j+1, N):
print(arr[i], arr[j], arr[k])
