배열 (Array)

배열이란?

배열은 데이터를 메모리에 연속으로 넣어두는 형태다. 맨 첫번째 칸의 주소만 가지고 있으면 그 다음 칸의 주소도 바로 알 수 있기 때문에 주소로 바로 접근해 빠르게 읽을 수 있다.

 

배열을 할당할 때는 arr = a[8] 처럼 메모리에게 '얼마만큼' 연속적으로 차지할지 알려줘야 한다. 일부 프로그래밍 언어에서는 길이를 알려주지 않아도 내부적으로 알아서 할당해주고 확장한다.

데이터 접근 시에는 주소를 쓰지 않고 arr[1] 처럼 인덱스라는 0부터 시작되는 숫자를 사용한다. 배열의 이름이 첫번째 주소를 가지고 있고, 칸마다 +1 되는 인덱스를 이용해 다음 주소를 알아내는 것이다. 인덱스는 0부터 시작하기 때문에 length - 1 까지다.

배열의 연산

READ

인덱스를 이용하면 RAM에 바로 접근해 읽을 수 있다. array[n] 의 값을 찾아가기 위해 단순 덧셈 연산(+n)만 실행하므로 O(1) 의 시간복잡도를 가진다.

 

SEARCH

특정 값이 어디에 있는지 알아내려면 배열 공간을 탐색해야 한다. 탐색 알고리즘은 다양하게 있는데, 제일 간단한건 Linear Search 와 Binary Search 다.

 

Linear Search

첫번째 칸부터 한칸 한칸 탐색하는 방법이다. 찾는 값이 첫번째에 있다면 한 번의 단계만 거치면 되지만, 제일 마지막 칸에 있다면 최대 길이만큼의 단계를 거쳐야 하므로 O(n) 의 시간복잡도를 가진다.

 

Binary Search

이미 정렬되어 있는 배열의 중간 값을 선택해 검색 값보다 작다면 왼쪽의 중간값, 크다면 오른쪽의 중간값을 비교해 나가며 검색하는 방법이다. 단계를 거칠 수록 해야되는 작업이 반절로 줄어드니 O(log n) 의 시간복잡도를 가진다.

 

INSERT

배열은 미리 공간을 확보하기 때문에 제한적인 공간 안에서 insert 작업이 이루어진다. 배열에 빈 공간이 있고 맨 마지막에 넣으면 되는 경우에는 끝에 바로 붙이면 된다. 맨 끝의 인덱스는 배열의 길이로 쉽게 알아낼 수 있으니 수월한 작업이다.

 

배열에 빈 공간이 있지만 처음이나 중간에 넣어야 한다면, 자리를 마련하기 위해 뒤쪽 데이터를 한칸 씩 끝으로 이동시켜야 한다. 최악의 경우 첫 번째 칸에 넣을 때 데이터를 전부 한칸씩 이동시키는 경우이므로 O(n) 의 시간복잡도를 가진다.

 

자동으로 확장시켜주지 않는 프로그래밍 언어에서는 배열에 빈 공간이 없는 경우, 더 긴 새로운 배열을 만들어 복사한 다음에 데이터를 넣어야 한다. 기존에 쓰던 공간은 메모리에게 안 쓴다고 알려주어야 하는데, 내부에서 안 쓰는 메모리 공간을 자동으로 처리해주는 언어도 있고 개발자가 직접 메모리 정리 함수를 이용해 처리해주는 언어도 있다.

 

DELETE

배열은 메모리 공간을 미리 확보해 놓는데, 중간에 빈 공간이 생기면 공간을 비효율적으로 쓰게 되니 빈공간이 생기지 않게 관리를 해주어야 한다. 배열 끝의 데이터를 삭제하는건 간단하다. 중간에 빈 공간이 안 생기니 그냥 삭제하면 된다.

 

배열의 처음이나 중간의 데이터를 삭제해야 한다면 삭제 후에 생기는 빈공간을 채우기 위해 뒤쪽 데이터들을 하나하나 이동시켜야 한다. 최악의 경우 첫 번째 칸의 데이터를 지웠을 때 데이터를 전부 한칸씩 이동시키는 경우이므로 O(n) 의 시간복잡도를 가진다.

 

 

정리

배열은 인덱스를 이용해 RAM 에 바로 접근할 수 있어서 READ는 정말 빠르다.

 

그런데 공간을 미리 확보해야 하고, 중간에 빈 공간이 생기지 않게 관리해줘야 하므로 DELETE, INSERT 속도는 상대적으로 느리다. 그러니 배열의 맨 끝에서만 READ, DELETE 작업을 하는 경우에 쓰는 게 가장 좋다.

 

또 배열은 대부분의 프로그래밍 언어에 기본적으로 내장되어 있는 자료구조다. 내부적으로 다양한 연산을 제공해주니 해당 언어의 문서를 살펴보면 좋다. 배열을 이용해 다른 자료구조를 만들기도 한다.