1. Dynamic Array의 정의
- 개념: 고정된 크기(Fixed-size)를 가진 Static Array의 한계를 보완하기 위해, 저장 공간이 가득 차면 유동적으로 크기를 조절(Resize)하는 자료구조.
- 주요 특징: 데이터 추가 시 기존 배열의 크기를 초과하면 더 큰 배열을 새로 선언하고 데이터를 복사하여 저장 공간을 확보.
2. 리사이징(Resizing)과 Doubling
배열의 크기를 동적으로 확장하는 핵심 메커니즘.
- 동작 원리: 기존 메모리 한계를 초과할 경우, 새로운 대규모 배열을 선언하고 모든 데이터를 일일이 이동시키는 과정 수행.
- Doubling: 리사이징의 대표적인 방법으로, 기존 배열 크기의 2배에 해당하는 새로운 메모리 공간을 할당하는 방식.
- 비용 발생: 데이터 복사 과정에서 n개의 데이터를 옮겨야 하므로 일시적으로 O(n)의 시간 복잡도 발생.
3. 분할상환 시간복잡도 (Amortized Time Complexity)
가끔 발생하는 비싼 연산 비용을 빈번한 저렴한 연산들이 나누어 가짐으로써 평균 비용을 산출하는 개념.
- Append 연산의 특징:
- 대부분의 데이터 추가 작업은 마지막 인덱스에 저장되는 O(1) 연산.
- 아주 가끔 저장 공간이 가득 찼을 때만 리사이징을 위한 O(n) 연산이 발생.
- 최종 복잡도: 가끔 발생하는 O(n)의 비용을 다수의 O(1) 작업이 분담하여 전체적인 평균은 Amortized O(1)로 유지.
4. Dynamic Array vs Linked List 비교
| 구분 | Dynamic Array | Linked List |
|---|---|---|
| 데이터 접근 | 인덱스를 통한 Random Access (O(1)) | 처음부터 순차적으로 탐색 (O(n)) |
| 끝부분 추가/삭제 | 매우 빠름 (O(1)) | 포인터 변경만으로 가능 (O(1)) |
| 중간 삽입/삭제 | 데이터 시프트(Shift) 발생으로 느림 (O(n)) | 노드 연결 변경으로 상대적 빠름 (O(1)) |
| 메모리 효율 | 연속된 공간 사용 및 리사이징 시 낭비 발생 가능 | 필요할 때마다 할당하나 포인터 저장 공간 추가 필요 |
추가 정리
Q. Dynamic Array의 결정적인 단점은?
- 중간 삽입/삭제 성능 저하: 메모리상에 연속적으로 데이터가 저장되어 있어, 중간 작업 시 뒤의 데이터를 모두 한 칸씩 옮겨야 하는 O(n)의 비용 발생.
- 예측 불가능한 지연: 리사이징이 발생하는 시점에 현저히 낮은 퍼포먼스가 발생하여 실시간성이 중요한 작업에서 리스크로 작용 가능.
- 메모리 공간 낭비: 리사이징 시 향후 추가될 데이터를 고려해 실제 필요한 것보다 더 많은 공간을 할당받으므로 미사용 메모리 발생.
핵심 정리
- Dynamic Array: 크기 고민 없이 데이터를 추가할 수 있도록 자동 리사이징 기능을 제공하는 배열 구조.
- Amortized O(1): 리사이징 비용(O(n))이 가끔 발생하지만, 전체적인 추가(Append) 연산의 평균 효율은 상수로 유지.
- 용도: 데이터의 개수가 유동적이고 빈번한 인덱스 접근이 필요한 경우 최적의 선택지.