동적 배열(Dynamic Array)은 내부적으로 어떻게 크기를 늘리며, 이 과정에서 발생하는 비용을 어떻게 평가하나요?

동적 배열은 내부적으로 미리 정해진 용량(capacity)을 가지고 있습니다. 이 용량이 꽉 차서 새로운 요소를 추가해야 할 때, 동적 배열은 더 큰 새로운 배열을 생성하고 기존 배열의 모든 요소를 새 배열로 복사합니다. 이 과정을 '재할당'이라고 합니다.

재할당 과정은 기존 배열의 모든 요소를 복사해야 하므로 O(n)의 시간 복잡도를 가집니다. 하지만 동적 배열은 보통 용량을 기하급수적으로 늘립니다 (예: 현재 용량의 두 배). 이렇게 하면 재할당이 자주 발생하지 않게 됩니다.

이러한 재할당 비용은 '분할 상환 분석(Amortized Analysis)'을 통해 평균적으로 상수 시간 O(1)으로 평가됩니다. 즉, 개별 연산은 비쌀 수 있지만, 많은 연산을 수행했을 때 평균적으로 드는 비용은 매우 낮다는 의미입니다.