2. Array 배열

배열

배열

배열 : 일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조

 

아래의 예는 6개의 변수를 사용해야 하는 경우, 이를 배열로 바꾸어 사용하는 것이다.

Num0 = 0
Num1 = 1
Num2 = 2
Num3 = 3
Num4 = 4
Num5 = 5

Num = [0, 1, 2, 3, 4, 5]

 

배열의 필요성

프로그램 내에서 여러 개의 변수가 필요할 때, 일일이 다른 변수명을 이용하여 자료에 접근하는 것은 매우 비효율적일 수 있다.

배열을 사용하면 하나의 선언을 통해서 둘 이상의 변수를 선언할 수 있다.

단순히 다수의 변수를 선언을 의미하는 것이 아니라, 다수의 변수로는 하기 힘든 작업을 배열을 활용해 쉽게 할 수 있다.

 

1차원 배열

1차원 배열의 선언

별도의 선언 방법이 없으면 변수에 처음 값을 할당할 때 생성

이름 : 프로그램에서 사용할 배열의 이름

Arr = list() Arr = () (1차원 배열 선언의 예)

Arr = [1, 2, 3] Arr = [0] * 10

 

1차원 배열의 접근

Arr[0] = 10 : 배열 Arr의 0번 원소에 10을 저장

Arr[idx] = 20 : 배열 Arr의 idx번 원소에 20을 저장

 

알고리즘의 성능 분석 필요

• 많은 문제에서 성능 분석의 기준으로 알고리즘의 작업량을 비교한다.

 

시간 복잡도(Time Complexity)

측정 방법

• 실제 걸리는 시간을 측정
• 실행되는 명령문의 개수를 계산

시간 복잡도 ≓ 빅-오(O) 표기법

 

빅-오 표기법 (Big-Oh Notation)

시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시

계수(Coefficient)는 생략하여 표시

 

ex)

O(3n + 2) = O(3n) = O(n)

O(2n² + 10n + 100) = O(n²)

O(4) = O(1)

: 최고차항만 선택, 계수 제거

n개의 데이터를 입력 받아 저장한 후 각 데이터에 1씩 증가시킨 후 각 데이터를 화면에 출력하는 알고리즘의 시간 복잡도? → O(n)

 

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차원 배열의 접근

배열 순회

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

 

행 우선 순회

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

for i in range(n):
        for j in range(m):
                Array[i][j]  # 필요한 연산 수행

 

열 우선 순회

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

for j in range(n):
        for i in range(m):
                Array[i][j]  # 필요한 연산 수행

 

지그재그 순회

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

for i in range(n):
		for j in range(m):
				Array[i][j + (m-1-2*j) * (i%2)]  # 필요한 연산 수행

 

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

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

arr[0...N-1][0...N-1] # NxN 배열
di[] <- [0, 0, -1, 1] # 좌우상하
dj[] <- [-1, 1, 0, 0] 
for i in range(N): # 1 -> N-1
        for j in range(M): # 1 -> N-2 :
                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])

# 1칸이 아닌, d칸 이동하고 싶으면
# ni = i + di[k] * d
# nj = j + dj[k] * d

전치행렬

# 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 < g :
            arr[i][j], arr[j][i] = arr[j][i], arr[i][j]