[자료구조] 동적배열 (Dynamic Array)

 배열이란 같은 종류의 데이터들 일렬로 저장하는 자료구조이다. 

배열에 저장된 각 데이터들은 번호(index)를 가지고 있다.

하지만 이러한 배열만으로는 비효율적이거나 한계가 있는 작업이 있기 때문에 동적배열이나 연결 리스트 등과 같은

자료 구조를 만들어 사용한다. 

(동적배열이든 연결 리스트든 모두 기본적으로 배열을 이용하여 만들어낸 자료구조이다.)

동적배열(Dynamic Array) 이란?

 

 동적 배열이란 크기가 고정되지 않은 배열을 의미한다. (이름 그대로 단순하다!)

보통 우리가 흔히 말하는 배열은 동적(Dynamic)의 반대인 정적(Static) 즉, 정적배열을 의미한다. 정적배열은 크기가 고정되어 있어 데이터를 크기 만큼만 저장할 수 있다.

대표적으로 C++ 의 vector 나 자바의의 ArrayList 등이 있다.

동적배열이 필요한 이유

 동적배열은 이름에서 나타나듯이 배열의 크기를 동적으로 늘려서 사용하고 싶을 때 필요하다. (이유도 단순하다!)

배열은 크기가 고정해야 되기 때문에 이를 해결하기 위해 동적배열이 고안된 것이다.

처음부터 자신이 사용할 배열의 크기를 알면 좋겠지만 크기를 너무 크게 잡으면 메모리가 낭비되고, 그렇다고 크기를 작게 잡으면 매번 배열을 새로 만들어서 기존의 배열을 옮겨 담아야 해서 번거롭다.

동적배열의 시간복잡도

1. 특정 위치의 데이터를 반환하거나 변경하는 작업을 시간복잡도 O(1) 에 처리할 수 있다. 

(배열과 공통)

동적배열은 배열을 이용하여 구현되어 있기 때문에 데이터들이 메모리의 연속된 위치에 저장되어 있고, 각 데이터들은 번호(Index)를 가지고 있다. 그래서 특정 위치의 데이터를 호출하거나 변경하는 O(1)에 처리할 수 있다.

2. 배열의 크기를 변경하는 resize() 연산을 시간복잡도 O(N) 에 처리할 수 있다.

resize() 연산은 새로운 배열을 만들어 기존 배열의 데이터를 복사하는 작업이기 때문에 기존 배열의 크기에 비례하여 시간이 소요된다. 그렇기 때문에 resize() 연산은 O(N)에 처리 된다.

3. 데이터를 배열의 맨 끝에 추가하는 append() 연산을 시간복잡도 O(1)에 처리할 수 있다.

동적배열의 append() 연산이 O(1)에 처리 될 수 있는 것은 동적배열의 재할당 전략 덕분이다. 

동적배열의 재할당 전략은 새로운 배열의 크기를 기존 배열의 크기를 2배 만큼 늘리는 것이다.

예를들자면 동적배열은 1 -> 2 -> 4 -> 8 -> 16 순으로 메모리 크기를 늘려 가는 것이다.

만약에 append() 연산 마다 새로운 배열의 크기를 기존 보다 1 씩 늘려 데이터를 저장하면 매번 resize() 연산을 해야하기 때문에 

append() 연산의 시간복잡도가 O(N)이 되어 선형이 되버린다. 

그래서 아래 그림과 같이 메모리에서 할당받은 크기(capacity) 만큼 데이터 수(size) 가 채워졌을 때 기존 배열 크기 보다 2배 만큼의 크기를 메모리에서 할당받아서 저장 공간을 넉넉하게 만든다. 그러면 그 다음부터 append() 할 때 데이터를 빈 공간에 순서대로 채워넣으면 되기 때문에 append()을 O(1)에 처리 할 수 있는 것이다.

그런데 여기서 두가지 의문점이 생긴다. 

첫번째 . 

   결국은 배열이 꽉 찼을 때 append()를 하면 resize() 를 해야하는데 어떻게 append() 의 시간복잡도가 O(1)이 되는걸까? 

두번째.

   그리고 왜 새 배열의 크기를 기존 배열의 크기 보다 2배를 늘리는 것일까?

두 의문점에 대한 답은 append()의 평균 수행시간에 있다. 

먼저 기존 배열이 꽉 찼을 때 append()를 하면 resize() 를 해야하기 때문에 그 순간은 시간복잡도가 O(N)이 된다. 

하지만 시간복잡도를 평균적으로 보면 한번 씩 resize()를 한다고 해도 append() 의 시간복잡도는 O(1) 이 된다.

또한 이때 새 배열의 크기를 기존 배열의 크기 보다 2배씩 늘려야 append()의 평균 수행시간이 O(1) 이 된다.

예를들어 배열을 재할당할 때 크기를 상수만큼 늘린다고 가정해보자.

K = resize() 호출 수 (재할당 횟수)

M = 재할당하는 배열의 크기 

N = append() 호출 수 ( 저장할 데이터 개수)

처음에 빈 배열을 만들어서 데이터를 N개 만큼 추가 한다( append()를 N번 호출한다. )

기존 배열의 공간이 가득차면 resize() 를 호출해야하고 새 배열의 크기는 기존배열 보다 M 만큼 늘어나기 때문에

resize() 호출수(K) =   이 된다. 

즉, 데이터를 1,000(N) 개를 넣을 때 배열의 재할당 크기를 10(M) 이라고 하면

  해서 재할당(K)은 100번 일어난다. 

(데이터를 10개 넣고나면 배열이 가득 차서 배열의 크기를 새로 늘려줘야 하기 때문)

여기서 M 은 상수 이기 때문에 N 이 커질수록 M 값이 미치는 영향은 작아진다.

따라서 resize() 의 시간복잡도(K)는 O(N) 이 된다. 

( M이 10이든 100이든 상수는 결국 시간복잡도에 영향을 주지 못한다. ) 

배열을 재할당 할 때 마다 새 배열에 복사되는 데이터의 수는 각 M개, 2M개,  ,  개 이다.

N개의 데이터를 넣으면서 복사되는 데이터의 수를 모두 더하면  (1+2+3++K)M 이므로

 이 된다.

즉, N번의 append() 를 수행하는 데에는 수행시간이 총   만큼 소요되고 이를 N 으로 나누어서 평균을 내면 O(N) 이 되어 append() 평균 수행시간은 O(N) 이 되버린다.

하지만 배열의 크기를 기존 배열 크기의 2배씩 늘리게 되면 

배열을 재할당 할 때 마다 새 배열에 복사되는 데이터의 수는 각 1개, 2개, 4개, 8개,  ,  개 이다.

N개의 데이터를 넣으면서 복사되는 데이터의 수를 모두 더하면 1+2+4+8+  + 이므로

등비수열의 합 공식 에 따라 이 된다. 

( 1 은  이기 때문에 K번 재할당 했으면 마지막은 K-1 번째가 된다. )

그림으로 이해해보자면 배열의 크기가 2배씩 증가하기 때문에 마지막인 1 번째 부터 K-2 번째 까지의 합이 K-1 번째 값과 

거의 같다. 

K-1 번째 resize() 의 시간복잡도는 O(N) 일 것이기 때문에 결국은 1 번째 부터 K-1 번째 까지 데이터를 복사한 수행시간은

기껏 해야 O(2N) 일 것이고 결국 append()의 총 수행시간은 O(N) 이 된다.

따라서 배열의 크기가 2배씩 증가할 때 append()의 평균수행 시간은 O(N)을 N으로 나눈 O(1)이라고 할 수 있다.