Array와의 차이점
Array와 Dynamic Array의 차이점은 기존에 할당한 크기 이상의 데이터를 보관하기 위한 'Resize 작업에 대한 수행 여부'입니다. Dynamic Array의 경우 한계를 넘어서는 데이터 추가가 이루어질 경우 Resize 작업을 수행하여 이를 보관합니다.
장단점
장점은 '조회'와 '마지막 인덱스 추가, 삭제'의 시간 복잡도가 O(1)으로 성능이 우수합니다. Dynamic Array이 또한 Array와 동일한 방식으로 데이터를 보관하기 때문에 동일한 장점을 가지고 있습니다.
하지만, Resize 작업 수행이라는 차이로 인해 '더욱 큰 메모리를 낭비'와 '예상치 못한 낮은 성능 저하'가 발생할 수 있다는 단점을 가지고 있습니다.
왜, 그럴까?
Array 자료구조와의 차이인 'Resize 작업'을 바탕으로 단점을 생각해 보도록 하겠습니다.
장점
Array와 동일하게 데이터 관리에 대하여 '연속성'을 가지고 있기에, 인덱스를 산술적인 연산으로 구할 수 있습니다. 이로 인해, '조회'와 '마지막 인덱스에 대한 추가 및 삭제' 작업을 수행함에 있어 O(1)의 시간 복잡도 가지는 우수한 성능을 보여줍니다.
단점
Dynamic Array는 '가변성'이라는 특징을 가지고 있습니다. 이를 위해 Resize 기능을 수행합니다. 이로 인해, 예상치 못한 성능 저하와 더 큰 메모리 낭비를 초래할 수 있다는 단점이 있습니다.
이제, 그림을 통해 자세히 살펴보도록 하겠습니다.
기존 Array의 경우 위 그림과 같이 이미 할당한 크기를 넘어서는 데이터를 보관할 수 없습니다.
하지만, Dynamic Array의 경우 '불변성'의 한계를 보완하기 위해 Doubling(Resize)를 수행합니다. 이를 통해, 기존보다 2배 증가한 메모리 공간을 사용하여 기존의 데이터를 복사한 후 데이터를 추가하는 과정을 수행합니다.이로 인해, 기존 추가 작업에선 O(1)의 시간 복잡도를 가지고 있지만 Doubling이 필요한 추가의 경우 O(n)의 시간 복잡도를 가지고 있습니다. 즉, 예상치 못한 성능 저하가 발생할 수 있습니다.
또한, 다음 그림처럼 데이터 보관을 위해 Doubling을 수행한다고 가정해보겠습니다.
만약, N이 10,000,000 또는 100,000,000와 같이 무수히 큰 수라면 어떨까요? 겨우 1개의 데이터를 더 저장하기 위해 무수히 큰 크기의 메모리 공간을 추가로 사용해야 합니다. 즉, 엄청난 메모리 공간을 낭비할 수 있다는 가능성을 가지고 있습니다.
정리
위 내용을 정리하자면, Dynamic Array는 크기가 가변적인 Array라고 할 수 있을 것 같습니다. 이를 위해 Resize(Doubling) 작업이 수행되는 것을 알 수 있습니다.
예상 질문
Dynamic Array는 어떤 자료구조인가요?
Array와 동일한 방식으로 데이터를 보관합니다. 하지만, Dynamic Array의 경우 크기가 가변적 입니다.
Dynamic Array의 장단점은?
장점은 빠른 조회, 마지막 인덱스에 대한 빠른 추가와 삭제가 가능합니다. 단점은 resize 수행으로 인해 예상치 못한 성능 저하와 메모리 공간 낭비를 초래할 수 있습니다.
Resize는 어떻게 수행되나요?
우선, 2배 크기를 가지는 Array를 생성한 후 기존 데이터를 모두 복사합니다. 이후 추가된 데이터를 저장하고, 기존 Array는 메모리에서 삭제합니다.
Data 추가시 시간 복잡도
전체적으로 O(1)이라는 시간 복잡도를 가지고 있습니다. 물론, 크기 이상의 데이터를 추가할 때 resize 작업으로 인해 O(n)의 시간 복잡도를 가지는 경우도 있습니다. 하지만, 이는 굉장히 드물게 수행되는 작업이므로 분할 상환 시간 복잡도는 O(1)입니다.
