CS/자료구조

[자료구조] 동적 배열

tkxx_ls 2024. 5. 30. 17:11

먼저 배열에 대해 알아보겠습니다.

배열

배열이란 일반적으로 정적 배열을 말합니다. 동일한 타입의 데이터를 하나의 변수에 저장하고, 

인덱스를 사용하여 개별적으로 접근할 수 있게 하는 데이터 구조입니다. 

배열은 고정된 크기를 가지며, 각 요소는 인덱스를 통해 접근할 수 있습니다. 

배열의 인덱스는 보통 0부터 시작하여, 마지막 요소는 배열의 크기-1까지 이어집니다.

 

특징

  • 배열은 선언할 때 크기가 고정되며, 이후 크기를 변경할 수 없습니다.
  • 배열에 저장되는 모든 요소는 동일한 데이터 타입을 가져야 합니다.
  • 배열의 각 요소는 인덱스를 통해 접근할 수 있으며, 인덱스는 0부터 시작합니다.
  • 배열은 메모리에서 연속적인 공간에 저장됩니다.
  • 주어진 위치의 원소를 반환하거나 변경할 때 O(1)에 할 수 있습니다.

 

동적 배열

배열의 큰 단점인 처음에 배열의 크기를 지정하면 그 이상의 데이터를 삽입할 수 없다는 것입니다.

이 문제를 해결하기 위해 고안된 것이 자료의 개수가 변함에 따라

크기가 동적으로 바뀌도록 하는 동적 배열입니다.

 

특징

  • 요소가 추가되거나 삭제될 때 배열의 크기를 자동으로 조정합니다.
  • 요소의 삽입과 삭제가 용이합니다
  • 배열 요소에 인덱스를 통해 접근할 수 있습니다.
  • 구현할 때 내부적으로 항상 정적 배열로 구현됩니다.
  • 원소를 배열의 끝에 추가할 때 상수 시간이 걸립니다.

 

동적 배열은 정적 배열로 구현됩니다. 따라서 동적 배열의 크기가 바뀌어야 할 때,

새 배열을 선언한 후, 새 배열에 원소들을 복사한 후, 새 배열을 참조하도록 합니다.

따라서 배열의 크기를 바꿀 때 배열의 크기에 비례하는 시간이 걸립니다. ( O(n) )

따라서 동적 배열은 size와 capacity를 가집니다.

배열의 크기가 커질 때를 대비하여 미리 여유분의 메모리를 가집니다.

 

동적 배열의 특징 중에 append 연산을 할 때 상수 시간이 걸린다고 했는데

capacity까지는 상수 시간만에 append 연산을 할 수 있지만,

capacity까지 다 채웠을 경우 재할당을 해야 하기 때문에 O(n), 즉 선형 시간이 걸리게 됩니다.

 

선형 시간이 걸리는 것을 상수 시간으로 시간복잡도를 낮추는 전략을 사용합니다.

 

동적 배열의 재할당

append 연산을 할 때 선형 시간이 걸리는 것은 재할당 할 때만 일어납니다.

이렇게 호출할 때마다 실행시간이 달라지는 함수의 시간복잡도를 계산하는 방법은

해당 함수를 여러번 실행시킨 후, 실행시간의 평균을 내는 것입니다. (분할 상환 분석)

 

재할당할 때, 배열의 크기를 M 만큼 늘린다고 가정하겠습니다.

1만 개의 데이터를 순서대로 삽입할 때, M의 크기가 100이라고 가정하면 재할당은 99번 일어납니다.

그럼 데이터 복사는 100 + 200 + … + 9900 = 495000번 일어나게 됩니다.

그럼 M의 크기를 3000이라고 가정하게 되면, 10개의 데이터만 삽입하게 되어도

3000의 메모리를 할당해야 하므로 메모리 낭비를 하게 됩니다.

 

시간복잡도를 계산해보겠습니다.

빈 배열에서 N번 삽입하면 재할당 수 k는 N/M만큼 일어납니다.

이때 재할당 할 때마다 데이터를 복사해야 하므로

M + 2M + … + KM = ((K + 1) k / 2) M = O(N2)입니다.

그럼 한 번의 append 연산에는 O(N)이 걸리게 됩니다.

 

따라서 재할당할 때 배열의 크기를 선형적으로 늘리지 않고 지수적으로 늘립니다.

지수적으로 늘리게 된다면 다음과 같습니다.

재할당 시점 1 2 4 8 16 32 … 2048 4096 8192
새 배열의 크기 2 4 8 16 32 64 … 4096 8192 16384

 

데이터 복사의 수는 1+ 2 + 4 + …  +8192 = 16383번 일어나게 됩니다.

선형적으로 늘렸을 때와 비교하면 매우 작습니다.

지수적으로 늘렸을 때의 시간 복잡도를 계산하면 다음과 같습니다.

따라서 한 번의 append 연산의 시간복잡도는 3n / n = O(1)이 걸리게 됩니다.

 

지수적으로 늘리지 않더라도 배열의 크기에 비례하게 재할당하면

시간복잡도가 줄어들게 됩니다.

 

마무리

동적 배열을 사용할 때, 배열에 삽입할 원소의 개수를 미리 알고 있다면,

미리 capacity를 원소의 개수만큼 늘려, 재할당을 하지 않도록 합니다.

c++ vector에는 reserve(), Java ArrayList에는 ensureCapacity()를 사용하여

capacity를 늘릴 수 있습니다.