[자료구조] 배열 - 동적 배열, 정적 배열

Python/알고리즘

AI 꿈나무 2021. 2. 10. 16:43

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다.

배열

배열은 값 또는 변수 엘리먼트의 집합으로 구성된 구조로 하나 이상의 인덱스 또는 키로 식별됩니다.

자료구조는 크게 메모리 공간 기반의 연속 방식과 포인터 기반의 연결 방식으로 나뉩니다.

배열은 연속 방식의 가장 기본이 되는 자료형 입니다.

연결 방식의 가장 기본이 되는 자료형은 연결 리스트 입니다.

추상 자료형의 실제 구변 대부분은 배열 또는 연결 리스트를 기반으로 합니다. 예를 들어 스택은 연결 리스트로 구현하고, 큐는 배열로 구현하는 식 입니다. 물론 반대의 경우도 가능합니다.

배열의 장점으로는 어느 위치에나 O(1)에 조회가 가능하다는 장점이 있습니다.

C언어에서의 배열은 크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형을 말합니다.

크기가 고정되어 있으며, 한번 생성한 배열은 크기를 변경하는 것이 불가능합니다. 이를 정적 배열이라고 합니다.

배열은 고정된 크기만큼의 연속된 메모리 할당입니다.

그러나 실제 데이터에서는 전체 크기를 가늠하기 힘들 때가 만습니다. 너무 작은 영역을 할당하여 모자라거나, 너무 많은 영역을 할당하여 낭비될 때도 있습니다.

이러한 문제를 해결하기 위해 크기를 지정하지 않고 자동으로 리사이징하는 배열인 동적 배열이 등장했습니다.

파이썬에서는 리스트가 동적 배열 자료형입니다.

동적 배열은 크기를 지정하지 않고 자동으로 리사이징하는 배열입니다.

동적 배열의 원리는 간단합니다.

미리 초깃값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 꽉 채워지면, 늘려주고 모두 복사하는 방식입니다.

대개는 더블링(Doubling)이라 하여 2배씩 늘려주게 되는데, 모든 언어가 항상 그런 것은 아니며 각 언어마나 늘려가는 비율은 상이합니다.

배열 크기의 재할당 비율을 그로스 팩터(Growth Factor), 성장 인자라고 합니다.

파이썬의 그로스 팩터는 초반에는 2배씩 늘려 가지만, 전체적으로 약 1.125배 입니다.

파이썬의 동적 배열 자료형인 리스트에 아이템을 삽입할 때, 동적 배열의 용량이 꽉 차게 되면 크기를 늘려나갑니다.

이처럼 동적 배열은 정적 배열과 달리 크기를 지정할 필요가 없어 매우 편리하게 활용할 수 있으며, 조회 또한 기존의 배열과 동일하게 O(1)에 가능합니다.

그러나 공간이 차게되면, 새로운 메모리 공간에 더 큰 크기의 배열을 할당하고 기존 데이터를 복사하는 작업이 필요하므로 O(n)의 비용이 발생합니다.