Array

Array

배열(Array)는 메모리 상에서 데이터가 연속적으로 연결되어있는 선형 자료구조입니다.

• 배열의 크기는 한번 초기화하면 고정되며, 변경할 수 없습니다. 즉, 데이터의 삽입 & 삭제는 불가능합니다.
• 배열의 i 번째 데이터에 접근 & 변경에 O(1)의 시간복잡도를 갖습니다. (Random Access)
• 배열에 X 라는 데이터가 있는지 확인하는데 O(N)의 시간복잡도를 갖습니다. (Sequential Access)

Dynamic Array

동적 배열(Dynamic Array)은 일반 배열과 마찬가지로, 메모리 상에서 데이터가 연속적으로 저장되는 선형 자료구조입니다. 근본적으로는 고정 크기 배열을 기반으로 구현 되며 Python의 List, C++의 Vector, Java의 ArrayList가 있습니다.

동적 배열은 일반 배열과 달리 크기를 동적으로 조절할 수 있다는 특징이 있습니다. 동적 배열에 원소를 Insert 시 더 이상 데이터를 저장할 공간이 없을 경우 일정 크기만큼 배열을 확장하는 Resizing 과정을 통해 용량을 늘립니다. 확장하는 크기는 언어나 구현에 따라 다르지만, 일반적으로는 기존 크기의 2배 혹은 1.5배 정도입니다. 하지만 늘린 사이즈만큼 저장공간을 모두 사용하지 않을 수 있기 때문에 어느정도 메모리 낭비가 있을 수 있습니다.

• 동적 배열의 i 번째 데이터에 접근 & 변경에 O(1)의 시간복잡도를 갖습니다. (Random Access)
• 동적 배열에 X 라는 데이터가 있는지 확인하는데 O(N)의 시간복잡도를 갖습니다. (Sequential Access)
• 동적 배열에 끝에 데이터의 삽입 & 삭제에는 Amortized O(1)의 시간복잡도를 갖습니다.
• 동적 배열의 끝을 제외한 데이터의 삽입 & 삭제에는 O(N)의 시간복잡도를 갖습니다.

Resizing 과정

Resizing 과정은 새로운 메모리를 할당하고, 기존 데이터를 복사한 뒤 이어서 저장하는 과정으로 수행됩니다. 이러한 구조 덕분에 평균적으로 O(1) 라는 빠른 삽입 성능을 유지할 수 있습니다.

Resizing

1. 동적 배열의 초기 크기는 4 로 지정합니다. (Java 기준 동적 배열(ArrayList) 초기 크기는 10 입니다.)
2. 동적 배열의 초기 크기가 모두 차도록 원소를 add 합니다.
3. add(6) 을 하게 되면 동적 배열의 초기 사이즈가 넘게 됩니다. 따라서 배열을 확장하는 Resizing 과정이 수행됩니다. 기존동적 배열의 크기를 N 이라고 가정한다면
   1. N + (N / 2) 크기만큼 새로운 메모리를 할당하고(Java 기준 Resize 크기는 1.5 배입니다) 기존 데이터를 복사 및 저장합니다.
   2. Resizing 자주 발생하지 않으므로 평균적으로는 O(1) 의 빠른 삽입 성능을 유지할 수 있습니다. 하지만 Resizing 이 발생한다면 O(N) 만큼의 시간복잡도가 소요됩니다.

Insertion

Insert First or Middle

동적 배열에서 끝을 제외한 위치에 데이터를 삽입하는 경우, Resizing 여부와 관계없이 O(N)의 시간복잡도를 가집니다. 예를 들어, Index 1에 10이라는 원소를 삽입하고자 할 때 다음과 같은 절차로 동작합니다

1. 삽입 위치(Index 1)부터 끝까지의 모든 요소를 오른쪽으로 한 칸씩 이동시킵니다.
2. 삽입 위치(Index 1)에 10을 저장합니다.

이 과정에서 요소들을 이동시키는 비용 때문에 O(N)의 시간복잡도가 발생합니다.

이제 위 상태에서 동일하게 Index 1에 11이라는 원소를 삽입하면, 배열의 크기가 가득 차 있기 때문에 Resizing이 발생합니다.

1. 7 + (7 / 2) = 10 크기만큼 새로운 메모리를 할당하고, 기존 데이터를 복사 및 저장합니다.
2. 삽입 위치(Index 1)부터 끝까지의 모든 요소를 오른쪽으로 한 칸씩 이동시킵니다.
3. 삽입 위치(Index 1)에 11을 저장합니다.

이 과정에서는 배열을 확장하면서 새로운 배열을 생성하고 데이터를 복사하는 데 N, 그리고 요소들을 이동시키는 데도 N 의 비용이 발생합니다. 즉, 총 2N 만큼의 연산이 필요하지만, 시간복잡도 표기법에서는 결국 O(N)으로 표현됩니다.

Insert Last

동적 배열의 끝에 데이터의 삽입 하는 경우, 평균적으로 O(1)의 시간복잡도를 가집니다. 구체적으로 Resizing 이 발생하지 않으면 O(1), Resizing 이 발생하면 O(N)의 시간복잡도를 갖습니다.

예를 들어, Resizing 이 일어나지 않는다는 것을 가정하고 동적 배열의 끝에 10이라는 원소를 삽입하고자 할 때 다음과 같은 절차로 동작합니다.

1. 동적 배열의 맨 마지막에 10을 저장합니다.

이제 배열이 가득 찬 상태에서 끝에 11이라는 원소를 삽입하고자 한다면, 배열의 크기가 다 차 Resizing 이 발생하게 됩니다.

1. 7 + (7 / 2) = 10 크기만큼 새로운 메모리를 할당하고, 기존 데이터를 복사 및 저장합니다.
2. 새로운 배열의 끝에 11을 저장합니다.

Removal

Remove First or Middle

동적 배열에서 끝을 제외한 위치에 데이터를 삭제하는 경우, O(N)의 시간복잡도를 가집니다. 예를 들어, Index 1에 해당하는 원소를 지우고할 때 다음과 같은 절차로 동작합니다.

1. Index 1 에 위치한 원소를 제거합니다.
2. Index 2 부터 끝까지의 요소를 한 칸씩 왼쪽으로 이동시킵니다.
3. 배열의 마지막 요소는 중복되므로 제거합니다.

이 과정에서 요소들을 이동시키는 비용 때문에 O(N)의 시간복잡도가 발생합니다.

Remove Last

동적 배열의 끝의 원소를 삭제 하는 경우, O(1)의 시간복잡도를 가집니다. 이는 다음과 같은 절차로 동작합니다.

1. 배열의 끝 원소를 제거합니다.

삭제한 뒤에도 다른 요소를 이동시킬 필요가 없습니다.

Reference

김희성님 유튜브