동적 배열 (Dynamic Array)

동적 배열 (Dynamic Array)

크기가 고정되지 않고 요소 추가 시 자동으로 확장되는 배열 기반 자료구조로, 용량 초과 시 더 큰 배열을 할당하고 기존 데이터를 복사하여 가변 크기를 지원

목적: 가변 크기, 자동 확장, 배열의 빠른 접근 유지

특징: 용량(capacity) vs 크기(size), 동적 확장, 재할당, 분할상환 분석

구성요소: 내부 배열, 크기(size), 용량(capacity), 증가 인자(growth factor)

동작 원리: ① 요소 추가 → ② size == capacity 시 → ③ 2배(또는 1.5배) 용량 배열 할당 → ④ 기존 데이터 복사 → ⑤ 새 요소 추가

증가 전략: 2배 증가(Java ArrayList), 1.5배 증가(C++ vector), 메모리-속도 트레이드오프

시간 복잡도

• •접근: O(1)
• •추가(끝): O(1) - 분할상환
• •추가(중간): O(n)
• •삭제(끝): O(1)
• •삭제(중간): O(n)

분할상환(Amortized): n번 추가 시 총 복사 = 1+2+4+...+n < 2n → O(1) per operation

장점: 가변 크기, 빠른 접근(O(1)), 끝 추가·삭제 효율적

단점: 재할당 오버헤드, 메모리 낭비(여유 공간), 중간 삽입·삭제 비효율

적용사례: Java ArrayList, C++ vector, Python list, C# List

비교: 동적 배열(연속/빠른접근) vs 연결 리스트(분산/빠른삽입)

연관: 배열, 분할상환 분석, ArrayList, Vector