[핵심 답변]
Array의 경우 size가 고정되었기 때문에 선언시에 설정한 size보다 많은 갯수의 data가 추가되면 저장할 수 없습니다. 이에 반해 Dynamic Array는 저장공간이 가득 차게 되면 resize를 하여 유동적으로 size를 조절하여 데이터를 저장하는 자료구조 입니다.
[면접 
TIP]
TIP]Array의 특징중에 fixed-size의 한계점을 보완하고자 고안된 자료구조인 Dynamic Array에 대해서 면접을 위해 깊게 공부하실 내용은 크게 두 가지 입니다.
1. resize를 하는 방식
2. 데이터 추가(append)할 때의 시간복잡도
Dynamic Array
Dynamic Array는 size를 자동적으로 resizing을 하는 Array입니다. 기존에 고정된 size를 가진 Static Array의 한계점을 보안하고자 고안되었습니다. Dynamic Array는 data를 계속 추가하다가 기존에 할당된 memory를 초과하게 되면, size를 늘린 배열을 선언하고 그곳으로 모든 데이터를 옮김으로써 늘어난 크기의 size를 가진 배열이 됩니다. 이를 resize라고 합니다. 이로써 새로운 data를 저장할 수 있게 됩니다. 따라서 Dynamic Array는 size를 미리 고민할 필요없다는 장점이 있습니다.
resizing 을 하는 방법은 여러 가지가 있는데, 대표적으로 기존 Array size의 2배 size를 할당하는 doubling이 있습니다.
Doubling
resize의 대표적인 방법으로는 Doubling이 있습니다. 데이터를 추가(append ) 하다가 메모리를 초과하게 되면 기존 배열의size보다 두배 큰 배열을 선언하고 데이터를 일일이 옮기는(n개의 데이터를 일일이 옮겨야 하므로 ) 방법입니다.
분할상환 시간복잡도 Amortized time complexity
Dynamic array에 데이터를 추가할 때마다 의 시간이 걸리게 됩니다. → 추가를 하다가 미리 선언된 size를 넘어서는 순간에 resize를 하게 됩니다. → 이 때는 일일이 데이터를 모두 옮겨야 되기 때문에 이 때만큼은의 시간이 걸리게 됩니다.
그렇다면 결과적으로 append의 시간복잡도는 일까요 아니면 일까요?
append의 총 과정을 살펴보면 데이터를 마지막 인덱스에 추가하는()작업이 대다수이고, size를 넘어설 때는 size를 두 배 늘리고 데이터를 일일이 옮기는 과정 (resize )이 아주 가끔 발생합니다. 결론부터 말하자면 append의 전체적인 시간복잡도는 입니다. 좀 더 정확히 말하면 amortized 이라고 부릅니다.
쉽게 설명하자면 가끔 발생하는 O(n)의 resize하는 시간을, 자주 발생하는 O(1)의 작업들이 분담해서 나눠 가짐으로써 전체적으로 O(1)의 시간이 걸린다고 생각하시면 됩니다.
[꼬꼬무 문답]
Q) Dynamic Array를 Linked list와 비교하여 장단점을 설명해 주세요.