동적 배열 : expand 연산을 이해하는 것이 핵심이다.

 보통 Dynamic array, 동적 배열이라고 하면 크기가 변하는 배열을 의미합니다. c++의 STL에서는 vector가, 그리고 Java에서는 ArrayList가 있어요. 그런데, push_back이나 add를 100만번, 200만번을 해도, 실제로는 그렇게 오래 걸리지 않는 듯 싶습니다. 이는 왜 그럴까요?

 

 

---

 ArrayList와 vector는 다음 두 함수가 있습니다. size와 capacity. 이 둘의 차이를 이해하기 전에, 배열에 원소를 추가할 때 어떤 식으로 처리해야 좋은지 생각해 보도록 합시다. 추가할 공간이 많이 남아 있습니다.

 

 

 예를 들자면, 이 경우, 추가할 공간이 2개나 더 있습니다. 4 뒤에 추가해도 되는 상황입니다. 그러면, push_back이나 add가 호출이 되었을 때, 4 뒤에 넣어버리면 될 겁니다.

 

 

 문제는 동적 배열이 꽉 찼을 때, 그러니까 할당된 공간만 가지고는 더 이상 추가가 안 되는 경우입니다.

 

 

 그러면, 새로운 공간을 할당하고, 기존에 있는 내용은 새 공간에 모두 복사를 해야 할 겁니다. 그 다음에, 기존에 있었던 공간은 delete나 free 등으로 해제를 해야 할 겁니다. 기존에 있었던 내용의 크기를 prev, 새 공간의 크기를 cur라고 한다면, 이 일련의 작업을 수행하기 위해서는 2prev + cur 만큼 걸릴 겁니다.

 

 

 일단, 공간을 할당하는데 cur만큼 걸렸습니다. 그리고, 내용을 새 배열에 옮겨 담습니다.

 

 

 그러면, 기존 공간을 해제하고, 새로운 원소를 뒤에 추가할 수 있을 겁니다. 그런데 이런 식으로 1개씩만 늘려 나가는 경우에는, 그 다음에 또 push_back 연산이 들어온 경우에, 또 expand를 해야 합니다.

 

 

 이런 식으로 처리하다 보면, 뒤에다 추가하는 연산이 O(n)만큼 걸리지 않을까요? 이러한 비효율을 줄이기 위해서, x배율로 확장하는 트릭을 쓰는데요. arrayList는 1.5배로 늘리고, vector는 2배로 늘립니다. 예를 들어 x가 2였다고 해 봅시다. 현재 할당된 용량이 4였고, 실제로 있는 원소의 갯수가 4였습니다. 이 때, expand 없이 동적 배열에 추가가 되지는 못할 겁니다.

 

 

 확장이 될 때, 새로운 배열은 5가 아닌 기존 배열의 크기 4에서 2배가 뻥튀기가 된 8이 됩니다. 그렇게 된다면, 동적 배열의 size가 100만이 넘어가기 위해서, 단 19 ~ 20번 정도만 expand를 하면 됩니다. 이것이 효율을 결정짓는 엄청난 요소인 셈이죠. 이렇게 확장이 될 때, x배율로 늘려버리면, 뒤에다 추가하는 연산이 O(n)이 아닌 O(1)인데요. 이는 상환 복잡도 분석으로 보일 수 있습니다.

 

 이러한 루틴을 이해하신다면 size랑 capacity의 차이 또한 이해를 하실 수 있습니다. 전자는 그냥 배열 안에 있는 원소의 갯수라면, 후자는 실제로 넣을 수 있는 원소의 최대 갯수를 뜻한다고 보시면 됩니다.

 

 

 그러면 이러한 경우에 size()와 capacity()는 각각 어느 값을 리턴할까요? 배열 내에 있는 원소는 3개이고, 실제로 4개만큼 들어갈 수 있기 때문에 각각 3, 4를 리턴합니다.

 

 

---

 그러면 이 자료구조를 사용하면, 삽입, 삭제, 랜덤 접근, 검색 등의 연산 복잡도가 어떻게 될까요? 배열과 똑같다고 생각하시면 좋습니다. 먼저 insert는 뒤에 추가하는 것이 아니고서는 O(n)입니다.

 

 

 만약에 맨 앞에 7을  추가한다면, 2, 4, 3이 뒤로 밀릴 겁니다. 밀리는 원소 갯수가 3입니다. 만약에 size()가 10만이였다면, 밀리는 갯수가 10만일 겁니다. n개 였다면 n이였을 겁니다. 즉, 최악의 경우에 n개만큼 밀어내기 때문에, O(n)입니다. 물론, 공간이 부족하면 그 전에 expand가 들어가는데, 이 친구는 O(1)이기 때문에 무시됩니다.

 

 

 삭제는 어떨까요? 맨 앞의 것을 delete 하는 경우, 뒤에 있는 나머지 원소들을 끌어와야 합니다. 따라서 O(n)입니다.

 

 

 어떠한 원소가 있는지 탐색하는 건 어떨까요? 정렬이 되어 있지 않다면, 9를 찾기 위해서 끝까지 가 보아야 할 겁니다. 물론, sorting이 되어 있는 상태라면 다릅니다. 이진 탐색으로 찾아내면 되거든요. 그렇지 않다면 O(n)입니다.

 

 

 x번째에 있는 원소를 빠르게 찾을 수 있습니다. 이를 random access라고 하는데 O(1)입니다. 배열은 메모리 상에 연속적으로 저장이 됩니다. 따라서, 배열의 시작 주소와 원소 하나당 메모리에서 차지하고 있는 space만 알면 쉽게 계산할 수 있습니다.

 

 배열의 장점인 random access가 빠르다는 것을 동적 배열 또한 가지고 있는 셈입니다. 정리하면 dynamic array는 크기가 동적으로 변할 수 있다는 것 말고는 정적인 배열과 다를 바가 없습니다. 그리고, push_back이나 add가 효율적으로 수행되게 하기 위해서, 확장할 때 x배율로 늘린다. 정도만 알아두시면 면접에서도 크게 문제 없으리라 생각됩니다.