Kwangmin Kim - Data Structure (2) Array

1 배열의 개요

정의: 배열 (Array)

배열은 동일한 타입의 데이터를 메모리상에 연속적으로 저장하는 자료구조다.

인덱스(0-based)로 임의 접근: \(O(1)\)
삽입/삭제(중간): 뒤 원소를 밀거나 당겨야 하므로 \(O(N)\)
Python의 list는 동적 배열로, 내부적으로 크기가 자동 조정된다

가장 기본적인 자료구조다.
여러 개의 변수를 담는 공간으로 이해할 수 있다.
data가 연속적으로 들어가는 형태여서 배열은 인덱스(index)가 존재하며, 인덱스는 0부터 시작한다.
특정한 인덱스에 직접적으로 접근 가능하여 수행 시간은 빠른 속도인 \(O(1)\) 이다.

2 왜 필요한가

인덱스를 통한 임의 접근이 \(O(1)\) 에 가능하여 조회가 빠르다.
캐시 메모리 히트율이 높아 연속 접근 성능이 우수하다.
수치 계산, 이미지 처리, 행렬 연산 등 데이터 과학 분야의 핵심 자료구조다.
정적 크기를 사전에 알고 있는 경우 메모리를 효율적으로 사용할 수 있다.

3 배열의 특징

컴퓨터의 메인 메모리에서 배열의 공간은 연속적으로 할당된다.
장점: Cache memory(속도면에서, \(RAM<Cache<CPU\), 공간면에서, \(CPU<RAM<Cache\), CPU옆에 위치) 히트(RAM에 있는 data를 Cache에 일부 옮기는 현상) 가능성이 높으며, 조회가 빠르다. 배열 같은 경우는 공간적으로 또는 연속적으로 붙어 있기때문에 cache memory 묶어서 옮길 수 있다.
- Cache Hit: 원하는 data가 Cache Memory존재하는 것을 의미.
- 특정 index에 접근하는 속도가 매우 빠르다, \(O(1)\).
단점: 배열의 크기를 미리 지정해야 하는 것이 일반적이므로, 데이터의 추가 및 삭제에 한계가 있다.

직관적 이해: 배열은 번호가 붙은 사물함 줄과 같다. 7번 사물함을 열려면 번호만 알면 바로 찾아가면 된다 — 이것이 \(O(1)\) 접근이다. 반면 중간에 새 사물함을 끼워 넣으려면 뒤의 사물함을 모두 한 칸씩 밀어야 한다 — 이것이 삽입의 \(O(N)\) 이유다.

메모리 구조 (연속 할당):

인덱스:  [0]  [1]  [2]  [3]  [4]
값:      [10] [20] [30] [40] [50]
주소:   1000 1004 1008 1012 1016  ← 4바이트(int) 간격으로 연속 배치
                                    arr[2] → 1000 + 2×4 = 1008 (즉시 계산)

연속 배치 덕분에 CPU가 배열 데이터를 캐시 메모리에 묶어서 올릴 수 있어 연속 순회 성능이 뛰어나다.

4 연결리스트 (LINKED LIST)

컴퓨터의 메인 메모리(RAM)상에서 주소가 연속적이지 않다.
배열과 다르게 크기가 정해져 있지 않고, 리스트의 크기는 동적으로 변경 가능하다.
장점: 포인터(pointer)를 통해 다음 데이터의 위치를 가리킨다는 점에서 삽입과 삭제가 간편하다.
단점: 원소를 검색할 때는 포인터가 앞에서부터 원소를 찾아야 하므로, 데이터 검색 속도가 느리다.

5 파이썬의 리스트 (list) 자료형

파이썬의 리스트(List) 자료형

파이썬에서는 리스트 자료형을 제공한다. (컴퓨터 공학에서의 연결 리스트와는 다른 의미)
일반적인 프로그래밍 언어에서의 배열로 이해할 수 있다. 그러므로, 파이썬의 리스트는 배열이라고 생각해야한다.
- 파이썬의 리스트는 배열처럼 임의의 인덱스를 이용해 직접적인 접근이 가능하다.
파이썬의 리스트 자료형은 동적 배열이다.
- append를 이용해 데이터를 삽입할 때 배열의 용량이 가득 차면, 자동으로 크기를 증가시킨다.
내부적으로 포인터(pointer)를 사용하여, 연결 리스트의 장점도 가지고 있다.
배열(array) 혹은 스택(stack)의 기능이 필요할 때 리스트 자료형을 그대로 사용할 수 있다.
큐(queue)의 기능을 제공하지 못한다. (비효율적)

6 리스트 컴프리헨션 (List Comprehension)

파이썬에서는 임의의 크기를 가지는 배열을 만들 수 있다.
일반적으로 리스트를 초기화할 때 리스트 컴프리헨션(list comprehension)이 자주 사용된다. (매우 편리)
크기가 N인 1차원 배열을 만드는 방법은 다음과 같다.

아래 코드는 파이썬에서 1차원 및 2차원 배열을 리스트 컴프리헨션으로 초기화하는 방법을 보여준다.

#| message: false
#| code-fold: true

# [0, 0, 0, 0, 0]
n = 5
arr = [0] * n
print(arr)

# [0, 1, 2, 3, 4]
n = 5
arr = [i for i in range(n)]
print(arr)
# 출력:
# [0, 0, 0, 0, 0]
# [0, 1, 2, 3, 4]

크기가 \(N \times M\) 인 2차원 리스트(배열) 만들기 1
- 2차원 배열이 필요할 때는 다음과 같이 초기화한다.

#| message: false
#| code-fold: true

n = 3
m = 5
arr = [[0] * m for i in range(n)]
print(arr)
# 출력: [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

크기가 \(N \times M\) 인 2차원 리스트(배열) 만들기 2

#| message: false
#| code-fold: true

n = 3
m = 5
arr = [[i * m + j for j in range(m)] for i in range(n)]
print(arr)
# 출력: [[0, 1, 2, 3, 4], [5, 6, 7, 8, 9], [10, 11, 12, 13, 14]]

7 배열을 초기화할 때 유의할 점

리스트는 기본적으로 메모리 주소를 반환한다.
따라서 단순히 [[0]∗m]∗n 형태로 배열을 초기화하면 안 된다.
이렇게 초기화를 하게 되면, n개의 [0]∗m 리스트는 모두 같은 객체로 인식된다.
다시 말해, 같은 메모리를(동일한 리스트를) 가리키는 n개의 원소를 담는 리스트가 된다.
2차원 배열을 초기화할 때는 리스트 컴프리헨션을 이용하는 것이 일반적이다.

#| message: false
#| code-fold: true

n = 3
m = 5
arr1 = [[0] * m] * n # 잘못된 방식
arr2 = [[0] * m for i in range(n)] # 옳은 방식

arr1[1][3] = 7
arr2[1][3] = 7

print(arr1)
print(arr2)
# 출력:
# [[0, 0, 0, 7, 0], [0, 0, 0, 7, 0], [0, 0, 0, 7, 0]]
# [[0, 0, 0, 0, 0], [0, 0, 0, 7, 0], [0, 0, 0, 0, 0]]

#| echo: false
#| message: false
#| code-fold: true

from IPython.display import display, Markdown
n = 3
m = 5
arr1 = [[0] * m] * n # 잘못된 방식
arr2 = [[0] * m for i in range(n)] # 옳은 방식

arr1[1][3] = 7
arr2[1][3] = 7

display(Markdown("""
위의 결과를 보면, 잘못된 방식으로 초기화된 배열 `arr1`은 {arr1}와 같이 7의 삽입이 모든 행에 걸쳐서 적용됐다. 반면에, 올바른 방식으로 초기화된 `arr2`는 {arr2}는 의도된 대로 하나의 element가 [1][3] index에 삽입이 된 것을 볼 수 있다.
""".format(arr1 = arr1, arr2 = arr2)))
# 출력: (Markdown 렌더링) arr1=[[0,0,0,7,0],[0,0,0,7,0],[0,0,0,7,0]], arr2=[[0,0,0,0,0],[0,0,0,7,0],[0,0,0,0,0]] 설명 텍스트

8 배열 직접 초기화

자신이 원하는 임의의 값을 넣어 곧바로 사용할 수 있다.

#| message: false
#| code-fold: true

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8]
print(arr)
# 출력: [0, 1, 2, 3, 4, 5, 6, 7, 8]

핵심 포인트

[0] * n은 O(n) 시간으로 배열을 생성하지만, 2차원에서는 얕은 복사 문제가 발생한다.
2차원 배열은 반드시 리스트 컴프리헨션 [[0]*m for _ in range(n)]을 사용한다.
[[0]*m] * n은 같은 리스트 객체를 n번 참조하므로 한 행 수정 시 모든 행이 바뀐다.

9 응용 분야

이미지 처리: 픽셀 데이터를 2차원 배열(행렬)로 표현하고 NumPy로 연산한다.
딥러닝 텐서: 가중치 행렬이 배열 구조로 GPU 메모리에 적재된다.
정렬 알고리즘: 퀵정렬, 병합정렬 등 대부분의 정렬이 배열을 대상으로 동작한다.
슬라이딩 윈도우: 시계열 데이터에서 고정 크기 구간을 배열로 관리한다.
룩업 테이블(Lookup Table): 사전 계산된 값을 배열에 저장해 \(O(1)\) 조회를 구현한다.