알고리즘 배열의 기본 개념

자료구조는 크게

1. 메모리 공간 기반의 연속 (contiguous)방식
2. 포인터 기반의 연결 (link)방식

으로 나뉜다

 

배열은 이중에서 연속 방식의 가장 기본이 되는 자료형이다

↔ 연결방식의 가장 기본이 되는 자료형은 ‘연결 리스트’가 있다

배열을 C언어 기준으로 설명해드리자면, 크기를 지정하고 해당 크기만큼 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형을 말한다.

크기가 정해져 있으며, 한번 생성한 배열은 크기를 변경하는 것이 불가능 하다

int arr[5] = {4, 7, 29, 0, 1};

반응형

물리 메모리, 즉 실제 메모리에는 이 배열 요소의 값들이 순서대로 배치된다

과거에는 16비트 컴퓨터 시절에 int는 2바이트였지만,

현대 32비트 이상의 시스템에는 int가 일반적으로 4바이트이다.

무엇보다 배열은 어느 위치에서나 O(1) 복잡도로 조회가 가능하다는 장점이 있다

배열 base주소에서 + index*자료형_사이즈

를 해주면 바로 주소를 찾을 수 있기 때문이다

하지만 고정된 크기 만큼의 연속된 메모리 할당이기 때문에 실제 데이터에서는 전체 크기를 가늠하기 힘들 때가 많다. 때로는 너무 작은 영역을 할당하여 모자라거나, 때로는 너무 많은 영역을 할당하여 낭비될 때도 있다

그래서 미리 크기를 지정하지 않고 자동으로 조절할 수 있게 리사이징(resizing)되는 배열인 동적 배열이 등장했다

728x90

동적 배열

---

대부분의 프로그래밍 언어는 동적 배열을 지원하며, 자바에서는 ArrayList, C++에서는 std::Vector가 대표적인 동적 배열 자료형이다. 코테에 자주 쓰이는 파이썬에서는 리스트가 바로 동적 배열 자료형이다. 대부분의 동적 프로그래밍 언어 (Dynamic Programming Language)들은 아예 정적 배열 자체가 없다. 파이썬도 정적 배열은 따로 없다

동적 배열의 원리는 간단하다. 미리 최대값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 꽉 채워지면, 늘려주고 모두 복사하는 식이다. 이 과정을 더블링 (doubling)이라 하여 말 그대로 2배씩 늘려주는 것이다. 하지만 모든 언어가 다 2배 늘어나는 것은 아니고 비율은 상이하다.

파이썬은 더블링 Growth Factor 마져도 Dynamic 하게 감소하도록 설계되어있는데, 평균적으로 약 1.125배로 늘어난다.

그러나 단점은, 더블링이 필요할 만큼 공간이 차게 되면, 위 그림처럼, 새로운 메모리 공간에 더 큰 크기의 배열을 할당하고 기존 데이터를 복사하는 작업이 필요하므로 O(n) 비용이 발생한다. 즉 최악의 경우 삽입시 O(n)이 되지만 자주 일어나는 일은 아니므로 분할 상환 분석에 따른 입력 시간 (Amortized Insertion Time)은 여전히 O(1)이다