[Algorithm 이론] 2차원 List | (ft. 초기화 선언, 입력받기, 인덱싱, 순회, 이웃 탐색, 전치 행렬)


 








2차원 List 기초 정리 (초기화 선언, 입력받기, 인덱싱, 순회, 이웃 탐색, 전치 행렬);


Algorithm

2차원 List

  • 1차원 List를 묶어놓은 List
  • 2차원 이상의 다차원 List는 차원에 따라 Index를 선언
  • 2차원 List의 선언: 세로길이(row 개수), 가로길이(col 개수) 를 필요로 함
# 2행 4열의 2차원 List 
arr = [[0,1,2,3], 
				[4,5,6,7]]

# Shape 
| 0 | 1 | 2 | 3 |
| 4 | 5 | 6 | 7 |

List 초기화 (ft. Python)

(방법1) 직접 나열

(방법2) 반복되는 원소는 곱셈연산을 통해 표현; (시퀀스 형태의 자료형은 전부 가능함)

(방법3) List Comprehension

# === 1차원 리스트 초기화 === # 

arr = [0,1,2,3,4,5]
arr = [0] * 5   # [0,0,0,0,0]
arr = [i for i in range(2,9) if i%2==0]   #[2,4,6,8]


# === 2차원 리스트 초기화 === # 
brr = [[1,2,3], [1,2,3], [1,2,3]]
brr = [[1,2,3]]*3    # [[1,2,3], [1,2,3], [1,2,3]]
brr = [[1,2,3] for i in range(3)] # [[1,2,3], [1,2,3], [1,2,3]]
brr = [[i,j] for i in range(3) for j in range(2)] 
											# [[0,0],[0,1],[1,0],[1,1],[2,0],[2,1]]

2차원 List 입력 받기

# === 입력 받을 데이터 === #  
3 4     # data shape 
0 1 0 0 # data 
0 0 0 0 
0 0 1 0
  • 첫째 줄에 nn행 mm열
  • 둘째 줄부터 n×mn\times m 의 행렬 데이터가 주어질 경우 입력을 받는 방법

(ex1) 행 축별로 입력

# === 데이터 형태 입력 === # 
n, m = map(int, input().split()) 

# === 데이터 입력 === # 
data = [0 for _ in range(n)] # 행 개수 
														 # [0] * n 

for i in range(n): # 행 별로 값 입력
    data[i] = list(map(int, input().split()))

(ex2) .append() 메소드 사용

# === 데이터 형태 입력 === # 
n, m = map(int, input().split()) 

# === 데이터 입력 === # 
data = [] 

for i in range(n): 
    data.append(list(map(int, input().split())))

(ex3) List comprehension 활용

# === 데이터 형태 입력 === # 
n, m = map(int, input().split()) 

# === 데이터 입력 === # 
data = [list(map(int, input().split())) for _ in range(n)]

2차원 List에서 원하는 데이터의 위치 찾기

# === 입력 받을 데이터 === #  
3 4     # data shape 
0 1 0 0 # data 
0 0 0 0 
0 0 1 0
  • 1 이 입력된 (행, 열) 위치 찾기

(sol)

# === 데이터 형태 입력 === # 
n, m = map(int, input().split()) 

# === 데이터 입력 === # 
data = [list(map(int, input().split())) for _ in range(n)]

# === 위치 찾기 === # 
location = [(i, j) for i in range(n) for j in range(m) if data[i][j]==1]

2차원 List 순회 (Iteration)

“n×mn \times m List의 n∗mn*m 개의 모든 원소를 빠짐없이 조사하는 방법”

[종류]

  • 행 우선 순회
  • 열 우선 순회
  • 지그재그(zig-zag) 순회

행 우선 순회

“List의 행을 우선으로 List의 원소를 조사하는 방법”

[----------------->]
[----------------->]
[----------------->]


arr=[[0,1,2,3],
		 [4,5,6,7],
		 [8,9,10,11]]

for i in range(len(arr)):  # 행 개수 
    for j in range(len(arr[i])): 
        print(f"{arr[i][j]}")

열 우선 순회

“List의 열부터 먼저 조사하는 방법”

|   |   |   |
|   |   |   |
|   |   |   |
v   v   v   v


arr=[[0,1,2,3],
		 [4,5,6,7],
		 [8,9,10,11]]

for j in range(len(arr[0])): # 열 개수
    for i in range(len(arr)): 
        print(f"{arr[i][j]}")

지그재그 순회

“List의 행을 좌우로 조사하는 방법”

[----------------->]   # 순방향 
[<-----------------]   # 역방향 
[----------------->]   # 순방향 


arr=[[0,1,2,3],
		 [4,5,6,7],
		 [8,9,10,11]]

n = len(arr)    # 행 길이 
m = len(arr[0]) # 열 길이

for i in range(len(arr)):
    for j in range(len(arr[0])): 
        item = arr[i][j+(m-2*j-1)*(i%2)]
        print(f"{item}")
  • 순방향 ⇒ arr[i][j]
  • 역방향 ⇒ arr[i][ j + (m-2*j-1) ]
  • selector ⇒ (i%2)

※ 인덱스 값을 내림차순으로 나타내는 함수 (짝수 번째 행에서, y=1y=1):

idx = −j+m−1-j+m-1

m=4m=4 일 때

  • j=0j=0 ⇒ idx=3
  • j=1j=1 ⇒ idx=2
  • j=2j=2 ⇒ idx=1
  • j=3j=3 ⇒ idx=0

※ 인덱스 값을 오름차순으로 나타내는 함수 (홀수 번째 행에서, y=0y=0):

idx = jj

  • j=0j=0 ⇒ idx=0
  • j=1j=1 ⇒ idx=1
  • j=2j=2 ⇒ idx=2
  • j=3j=3 ⇒ idx=3

※ 위의 두 수식을 하나로 표현 하면?

idx = j+(m−2j−1)yj + (m-2j-1)y

  • y=0y=0 ⇒ idx = jj
  • y=1y=1 ⇒ idx = m−j−1m-j-1

델타(Δ\Delta)를 이용한 2차 List 탐색

“2차 List의 한 좌표에서 (상하좌우)네 방향의 인접 List 요소를 탐색할 때 사용하는 방법

  • 델타 값은 한 좌표에서 네 방향의 좌표와 x,yx, y 의 차이를 저장한 List로 구현
  • 델타 값을 이용하여 특정 원소의 상하좌우에 위치한 원소에 접근할 수 있음

(Tip) 이차원 List의 가장자리(edge) 원소들은 상하좌우 네 방향에 원소가 존재하지 않을 경우가 있으므로, Index를 체크하거나 Index의 범위를 제한해야 함


EXAMPLE: 델타(Δ\Delta)를 이용한 2차 List 탐색

arr = [ [1,2,3,4],
        [5,6,7,8],
        [9,10,11,12]]

dy = [-1,1,0,0] # 상하
dx = [0,0,-1,1] # 좌우 

# === 탐색 시작 === # 
for y in range(len(arr)):
    for x in range(len(arr[y])):
        print(f"neighbors of {arr[y][x]} @ point ({y},{x})")

        for i in range(4): # 상하좌우 
            X = x + dx[i]
            Y = y + dy[i]
            
            if (Y<0 or X<0) or (Y>=len(arr) or X>=len(arr[y])): # 범위제한 
                continue

            print(f"{arr[Y][X]} @ ({Y},{X})")


# === output === # 
neighbors of 1 @ point (0,0)
5 @ (1,0)
2 @ (0,1)
neighbors of 2 @ point (0,1)
6 @ (1,1)
1 @ (0,0)
3 @ (0,2)
neighbors of 3 @ point (0,2)
7 @ (1,2)
2 @ (0,1)
4 @ (0,3)
neighbors of 4 @ point (0,3)
8 @ (1,3)
3 @ (0,2)
neighbors of 5 @ point (1,0)
1 @ (0,0)
9 @ (2,0)
6 @ (1,1)
neighbors of 6 @ point (1,1)
2 @ (0,1)
10 @ (2,1)
5 @ (1,0)
7 @ (1,2)
neighbors of 7 @ point (1,2)
3 @ (0,2)
11 @ (2,2)
6 @ (1,1)
8 @ (1,3)
neighbors of 8 @ point (1,3)
4 @ (0,3)
12 @ (2,3)
7 @ (1,2)
neighbors of 9 @ point (2,0)
5 @ (1,0)
10 @ (2,1)
neighbors of 10 @ point (2,1)
6 @ (1,1)
9 @ (2,0)
11 @ (2,2)
neighbors of 11 @ point (2,2)
7 @ (1,2)
10 @ (2,1)
12 @ (2,3)
neighbors of 12 @ point (2,3)
8 @ (1,3)
11 @ (2,2)

전치 행렬 (Transpose)

“행과 열의 값이 반대인 행렬을 의미”

arr[i][j] ⇒ arr[j][i]

arr = [ [1,2,3],
        [4,5,6],
        [7,8,9],]

for i in range(len(arr)): # 행 좌표
    for j in range(len(arr[i])): # 열 좌표
        
        if i < j : 
            arr[i][j], arr[j][i] = arr[j][i], arr[i][j] # swap           

print(f"{arr}")


# === output === # 
[[1, 4, 7], [2, 5, 8], [3, 6, 9]]

(Tip) 모든 좌표에 대해 행과 영의 값을 바꾸면 본래의 모습으로 되돌아오기 때문에 주의하기

  • 즉, i<ji < j 조건을 붙여서 이 문제를 해결함

zip(iterable*)

“동일한 개수로 이루어진 자료형들을 묶어 주는 역할을 하는 함수”

Untitled

  • 동일한 길이의 리스트
  • zip() 함수에 입력 ⇒ 각 리스트를 슬라이스(slice)하여 Tuple 객체로 묶어줌

(ex1) 기본 예시

alpha = ['a', 'b', 'c']
index = [1, 2, 3]

alpha_index = list(zip(alpha, index))
print(f"{alpha_index}")

# === output === # 
[('a', 1), ('b', 2), ('c', 3)]

(ex2) 행별로 묶기

arr = [[1,2,3], 
        [4,5,6], 
        [7,8,9]]

result = list(zip(*arr))

print(f"{result}")

# === output === # 
[(1, 4, 7), (2, 5, 8), (3, 6, 9)]
  • 위의 방법을 통해 전치 행렬(transpose matrix)을 쉽게 구할 수 있음
  • 즉, zip(*matrix) ⇒ 전치 행렬

(덧) (ex2)를 시각화하면

zip(*arr) 는 아래와 같음: 
zip( [1,2,3], [4,5,6], [7,8,9]) 

즉, zip( [1,2,3], 
		[4,5,6], 
		[7,8,9])  

# == Tuple로 묶어서 반환 == # 
(1,4,7), (2,5,8), (3,6,9)

Summary

  • 2차원 List 선언 및 초기화 방법
  • 2차원 List 입력 받기
  • List indexing
  • 2차원 List 순회(iteration)
  • 델타(Δ\Delta) 값을 이용한 이웃 요소 탐색
  • 전치 행렬 만드는 방법

Reference

[1] https://swexpertacademy.com/main/main.do

위치: 대한민국 서울특별시

댓글

댓글 쓰기

이 블로그의 인기 게시물

[DL for CV] Down-Sampling (Encoding)

이미지
  Down-sampling (Encoding)  [DL for CV] Down-Sampling (Encoding) ( source ) Downsampling 은 신호처리(signal processing)에서 사용되는 용어로 sample의 개수를 줄이는 처리 과정을 말한다 . 딥러닝에서는 인코딩(Encoding)과정에서 feature의 개수를 줄이는 처리과정 이라 볼 수 있다. feature 개수를 줄이면 이를 다룰 파라미터도 줄어들기 때문에 차원이 축소되는 효과 를 얻을 수 있다. 이는 곳 overfitting을 방지 하는 효과로 이어진다. 딥러닝 모델 아키텍처에서 사용되는 몇 가지 대표적인 Downsampling 방식을 정리한다. Pooling - 대표값 구하기 커널 영역(kernel scope)에 포함된 data 중에서 대표 값 하나를 샘플링하는 처리 방식 이다. 대표 값을 얻는 방식은 따르는 규칙에 따라 다르다; Max Pooling, Average Pooling, Global Average Pooling, and etc. 보통 Average pooling 보다는 Max pooling을 더 많이 사용한다. Average pooling의 경우 산술평균의 특성 을 가지기 때문에 필연적으로 발생하는 문제 가 있다 . 즉, 신호의 분산이 클 경우 대표 값과 실제 두드러지는 값과의 차이가 커진다 . 반면, Max pooling 연산이 좀더 간단하고 두드러지는 신호를 잘 전달할 수 있기 때문에 더 자주 사용된다. 때문에 논문과 교재에서 별도의 언급이 없이 Pooling layer를 언급한다면 Max pooling 이라 생각하면 된다. (장점) Pooling은 학습 가능한 파라미터 (learnable parameters)가 없기 때문에 kernel size를 키워도 차원의 저주를 피할 수 있는 방법중 하나다. t...
Read more »