[DS] Array

Array는 가장 기본이 되는 자료구조로 Static Array와 Dynamic Array로 나눌 수 있습니다.

Static Array

: n개의 원소를 지닌 고정된 크기의 컨테이너로 [0, n-1]까지 인덱스화 되어 있다. 일반적으로 우리가 흔히 아는 메모리의 일정 부분을 할당한다고 보면 된다.

*인덱스화가 되어 있다는 말은 인덱스라는 숫자로 컨테이너의 각 슬롯에 접근할 수 있다는 뜻이다.

컴퓨터에서 이루어지는 계산, 모니터출력, 게임등 모든 행위는 연산이며, 이러한 연산을 위해서는 메모리와 CPU가 필요하다. 그렇기 때문에 메모리를 할당받는 Array 자료구조는 기초가 되는 자료구조라고 할 수 있다.

<출처: GeeksforGeeks>

Dynamic Array

: Static Array가 n으로 고정된 크기의 컨테이너였다면, Dynamic Array는 크기가 정해져있지 않고 런타임 사용량에 따라 크기가 유동적으로 변하는 Array이다.

일반적으로 먼저 2개의 슬롯을 배정해주고 초과할 때마다 기존 슬롯 수의 2배를 새로 배정한다. 즉 6개의 원소를 삽입한다고 했을 때 2개에서 4개로 4개에서 8개로 늘어난 후 6개 슬롯을 채우고 2개의 빈 공간이 생기게 된다. 마찬가지로 삭제시에도 줄어든다.

기본 연산자에 따른 시간 복잡도는 다음과 같다.

	Static Array	Dynamic Array
접근(Access)	O(1)	O(1)
탐색(Search)	O(n)	O(n)
삽입(Insert)	x	O(n)
첨가(Append)	x	O(1)
삭제(Deletion)	x	O(n)

*Static Array는 고정값 컨테이너이기 때문에 삽입,첨가,삭제는 불가능하다. 수정은 접근과 같다고 보면 된다.

만약 Array가 크기 순으로 "정렬"되어 있다고 한다면 시간복잡도를 개선할 수 있다. 정렬에 관해서는 다양한 알고리즘이 존재하고 알고리즘 별로 시간복잡도가 다르기 때문에 이번 경우에 대해서는 삽입과 동시에 정렬을 한다고 가정하자.

그럴 경우 삽입, 첨가, 삭제는 모두 모든 원소들을 재정렬해야하기 때문에 O(n)을 가지게 된다. 예를 들어, array에 3을 삽입하고 1을 삽입할 경우 3을 1번 인덱스로 미루고 0번 인덱스에 1을 넣어야 한다. 하지만 접근의 경우 _정렬된 _Array에 한해 이진탐색을 수행함으로써 수행시간을 획기적으로 줄일 수 있다. 이진탐색의 기본 코드는 다음과 같다.

// input: a[0,...,n], x
// output: index of x (-1 if not found)

left = 0;
right = n-1;
while (left < right) {
    mid = (left+right) / 2;
    if (a[mid] < x){
        left = mid + 1;
    } else right = mid;
    if ((left==right) && (a[left] == x){
        return left;
    } else return -1;
}

핵심은 중간값을 기준으로 반으로 줄여가면서 탐색을 하기 때문에 모든 원소들을 탐색하지 않는다. 즉, sublinear하다. 이진탐색의 시간복잡도는 O(logn)으로 이진탐색 수행 시 접근시간을 O(logn)으로 줄일 수 있다.