Python 자료구조

배열 Array

• 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조
• python에서는 list 타입이 배열 기능을 제공

배열은 왜 필요할까?

• 같은 종류의 데이터를 효율적으로 관리하기 위해
• 같은 종류의 데이터를 순차적으로 저장
• 인덱스를 통한 빠른 접근 가능

Static Array

• 고정된 저장 공간(fixed-size)
• 순차적인 데이터 저장(order)

  선언시에 size를 정하여 해당 size만큼의 연속된 메모리를 할당 받아 data를 연속적/순차적으로 저장하는 자료구조

한계

데이터의 갯수가 정해져 있는 경우에는 static array를 사용하는 것이 매우 효율적이다. 하지만 선언시에 정한 size보다 더 많은 데이터를 저장해야 하는 경우 공간이 남아있지 않아서 문제가 발생할 수 있다. 그렇다고 매번 크기가 엄청 큰 배열을 선언한다면 그만큼 메모리 비효율이 발생한다.

Dynamic Array

동적배열(Dynamic Array)은 배열의 크기(size)를 변경(resize)할 수 있는 배열이다. fixed-szie 인 Static Array의 한계점을 보안하고자 고안되었다, 동적 배열에 데이터를 계속 추가하다가 기존에 할당 된 size를 초과하게 되면, size를 늘린 배열을 새로 선언하고 그곳으로 모든 데이터를 옮긴다. 그리고 기존의 배열은 메모리에서 삭제(free)하며 이 과정을 resize라 한다.

• resize를 한칸 씩 늘린다면 비효율적이라 기존 size의 두배 크기로 늘리며 이를 더블링(Doubling)라고 한다.

사용방법

Python에서는 list자료형을 통해 dynamic array을 이미 잘 구현해 두었기 때문에 직접 구현할 필요는 없다.
즉, 우리가 배워야하는 것은 list의 연산들과 시간 복잡도 이다.

시간복잡도

	Static Array	Dynamic Array
access/update	O(1)	O(1)
inset_back	O(1)	amortizedO(1)
delete_back	O(1)	O(1)
inset_at	O(n)	O(n)
delete_at	O(n)	O(n)

List array

# 1차원배열
array = [1,2,3,4,5]
array
>> [1,2,3,4,5]

# 2차원 배열
array = [[1,2,3],[4,5,6],[7,8,9]]
array
>>> [[1,2,3],[4,5,6],[7,8,9]]