배열

이번 시간에는 자료구조의 기본인 '배열'을 이해하고 배우는 시간을 갖도록 하겠습니다. 하지만 기본적으로 파이썬에는 배열과 100% 상응하는 자료형은 없습니다. 변수를 선언할 때 자료형을 따로 명시하지 않고, 고정된 크기만큼 정보를 담을 수 있는 자료형도 없기 때문입니다. 대신 어떤 자료형이든 제한 없이 여러 개 담을 수 있는 리스트(List)가 있습니다. Python에서 사용하는 리스트 자료구조는 Array List로 구현되어 있습니다. 

Array list

배열을 기반으로 구성된 list 자료구조 입니다. 이 Array list는 static array로 구현할 수 있고, dynamic array로 구현할 수도 있습니다. 

Static Array

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

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

int arr[5] = {3, 7, 4, 2, 6} // size가 5인 int형 배열 선언

위의 예시에서는 배열의 size를 5로 정했기 때문에 int형 데이터(4 byte) 5개를 연속적으로 저장할 메모리 공간인 20 Byte를 미리 할당을 받습니다. 이처럼 고정된 size를 갖게 되기 때문에 static array라고 합니다. 

Random Access

메모리에 저장된 데이터에 접근하려면 주소값을 알아야 합니다. 배열변수는 자신이 할당받은 메모리의 첫 번째 주소값을 가리킵니다. 배열은 연속적/순차적으로 저장되어 있기 때문에 첫 주소값만 알고 있다면 어떤 index에도 즉시 접근이 가능합니다. 이를 direct access 또는 random access라고 합니다. 

Dynamic Array

• static array에서 발생할 수 있는 메모리 비효율 문제를 해결할 수 있는 방법이 바로 dynamic array입니다. 선언 이후에 size를 변경할 수 없는 정적배열(Static Array)과 다르게 동적배열(Dynamic Array)는 size를 늘릴 수 있습니다. 즉 Resize 가능

일반적으로 2배 resize합니다. 출처: 개발남노씨

동적배열(dynamic array)은 배열의 크기(size)를 변경(resizing)할 수 있는 배열입니다. fixed-size인 Static Array의 한계점을 보안하고자 고안되었습니다. 동적배열에 데이터를 계속 추가하다가 기존에 할당된 size를 초과하게 되면, size를 늘린 배열을 새로 선언하고 그곳으로 모든 데이터를 옮깁니다. 그리고 기존의 배열은 메모리에서 삭제합니다. 이 과정을 resize라고 합니다. resize를 한칸씩 늘린다면 비효율적이므로 일반적으로 2배 큰 크기로 resize 합니다. 이를 더블링(Doubling)이라고 합니다. resize 덕분에 데이터를 추가 저장할 수 있게 됩니다.

선언시에 배열의 크기를 정하지 않아도 되기 때문에 코딩테스트에서 dynamic array를 자주 사용하게 됩니다. Python에서는 list 자료형을 통해 dynamic array을 이미 잘 구현해 두었기 때문에 직접 구현할 필요 없이 사용할 수 있습니다.

즉 문제에서 배열을 사용해야 하는 경우에는 list를 선언하여 사용하면 됩니다. 우리가 익혀야 할 것은 list의 연산(operation)들과 시간복잡도 입니다.

출처: 개발남노씨