배열 시리즈 중 4번째 글입니다.
- 배열에 대해 알아봅시다. 링크
- row major와 column major에 대해 알아봅시다. 링크
- 배열 주요 연산 시간복잡도를 대해 알아봅시다. 링크
- dynamic array에 대해 알아봅시다. [현재글]
이 글에서는 자료구조 동적배열에 대해 알아보겠습니다.
1칸씩 확장하기
정적 배열이란, 크기가 정해진 배열을 말합니다. 반면, 동적 배열은 크기가 변하는 것을 의미합니다. 그러면, 아래 연산이 추가됩니다.
- 배열의 크기를 증가시키는 grow
이 연산에 대해서 깊게 파헤쳐 보겠습니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/dy_ar1.png)
먼저 크기가 4인 배열이 있어요. 배열의 맨 뒤에 추가하는 것은 O(1)이라고 했어요. 그런데, 크기가 4인 배열이 꽉 찼기 때문에, 더 이상 추가할 수 없어요. 공간을 확장해야 겠지요. 하나 늘려보겠습니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/dy_ar2.png)
5를 추가하기 위해, 길이가 5인 배열을 만듭니다. 그리고, 길이가 4인 배열에 있었던 원소들을 모두 복사합니다. 다음에 길이 4인 배열을 버립니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/dy_ar3.png)
길이 5짜리 배열에 추가하려니, 공간이 없어요. 그렇기 때문에 공간 6짜리 배열을 만듭니다. 다음에, 길이 5짜리 배열에 있던 것을 복사합니다. 그 다음에 길이 5인 배열을 버립니다. 이렇게 grow를 할 때, 1개씩 확장하면 굉장히 비효율적으로 동작합니다.
길이 n짜리 배열을 1칸만 확장하는 경우
- 길이 n+1의 새로운 배열을 만듭니다.
- 길이 n에 있는 원소 n개를 새로운 배열에 복사합니다.
- 새로운 배열의 n+1번째 위치에 새로운 원소를 추가합니다.
- 길이 n의 배열을 버립니다.
1칸씩 확장할 때 마다 비효율의 끝을 달리게 됩니다.
k 배 만큼의 공간을 추가로 확장하기
대신에, k배 만큼의 공간을 추가로 grow가 될 때 마다 확장하게 할 수 있습니다. 기존 배열 대비, 확장된 배열이 x배율이 되었을 때, 이 x를 grow rate라고 합니다. 예를 들어, 크기가 4인 배열이 확장될 때, 1배 만큼의 공간을 추가로 확장해서 8이 되는 식입니다. 이 때, grow rate는 2가 되겠네요. 8을 4로 나누면 2이기 때문입니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/dy_ar4.png)
크기가 n인 배열이 있습니다. n+1번째 원소를 추가하려고 하는 데 공간이 없어요.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/dy_ar5.png)
기존 배열보다 kn개의 원소를 더 담을 수 있는 배열을 만듭니다. 그리고, n+1번째 위치에 n+1을 추가합니다. 여기까지 보면 1개씩 확장할 때와 별 다를 것이 없어 보여요. 오히려 더 비효율적인 거 같습니다. 중요한 것은 n+kn번째 원소가 추가될 때 arr이 확장이 되지 않는다는 것입니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/dy_ar10.png)
배열이 한 번 확장되었습니다.
- 크기가 n + kn인 배열이 새로 생성되었습니다.
- 원소 n개를 복사했습니다.
- 크기가 n인 배열이 버려집니다.
그리고, kn개의 원소를 추가할 때까지 확장이 되지 않았습니다. 오로지 뒤에 추가하는 비용만 있을 뿐입니다. 뒤에 원소를 추가할 때 마다 발생하는 비용을 계산해 봅시다. 이 3개의 비용을 kn으로 나눠 볼까요?
- 평균적으로 크기가 1 + 1/k 인 배열을 생성하였습니다.
- 평균적으로 1/k개의 원소를 복사했습니다.
- 평균적으로 크기가 1/k 인 배열이 버려집니다.
k는 적당히 큰 실수이기 때문에, 이 3개의 비용이 상수에 가깝게 됩니다.
Java의 ArrayList
이제 동적 배열을 쓰는 ArrayList를 간단하게 보도록 합시다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/dy_ar6.png)
grow 메서드는 원소를 추가하는 과정에서 공간이 부족하면 아래와 같은 일을 합니다.
- 새로운 배열을 만듭니다.
- 기존 배열의 원소들을 새로운 배열에 복사합니다.
여기서 6번째 줄을 봅시다. oldCapacity >> 1 이 부분입니다. 이는, 기존 배열 길이의 0.5배만큼 추가로 할당한다는 의미입니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/dy_ar7.png)
newLength 메서드 안으로 들어가 봅시다. prefGrowth와 minGrowth의 최댓값만큼 기존 Length에서 증가시킴을 알 수 있습니다. 1.5 배율에 가깝게 확장하는 것입니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/dy_ar8.png)
soft_max_array_length는 21억이 넘는 꽤나 큰 수입니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/07/dy_ar9.png)
나머지 부분을 봅시다. 현실적으로, prefLength가 21억이 넘어갈 일은 거의 없기 때문에, 보통 else절이 아닌 if절을 타게 됩니다. 그렇기 때문에 grow가 될 때, 최소 1.5 배율만큼 뻥튀기가 될 수 있습니다.