[기술 면접] 2. Dynamic Array는 어떤 자료구조인가요?

Dynamic Array는 Run time 도중에 크기를 조절하여 데이터 구조의 유연성과 필요에 따른 메모리 관리를 가능하게 합니다. 데이터의 추가, 삭제, 재배치를 효율적으로 수행할 수 있어, 다양한 상황에서 사용됩니다. 이번 포스팅은 동적 배열에 대해 알아봅니다.

Q : Dynamic Array는 어떤 자료구조인가요?

Array의 경우 size가 고정되었기 때문에 선언 시에 설정한 size보다 많은 갯수의 data를 저장할 수 없습니다. 하지만, Dynamic Array는 저장 공간이 가득 차면, resize를 통해 유동적으로 size를 조절하여 데이터를 저장하는 자료구조입니다.

Q : Dynamic Array의 resize를 설명해 보세요.

resizing을 하는 방법은 여러 가지가 있는데, 대표적으로 기존 Array size의 2배 를 할당하는 doubling이 있습니다. 데이터 append 시 O(1)의 시간복잡도를 가지다가, doubling이 발생하면, 데이터를 일일이 옮겨야 하므로 O(n)의 시간복잡도를 가집니다.

• 분할상환 시간복잡도 Amortized time complexity : append 시 O(1)로 진행 되다가 doubling이 발생할 때만 O(n)이 됩니다. 이러한 경우 시간 복잡도를 O(1)로 규정하며, 더욱 정확히 표현하면 amortized O(1)이라고 칭합니다.

Q : Dynamic Array를 Linked List와 비교하여 장단점을 설명해 주세요

Linked List와 비교했을 때, Dynamic Array의 장점은

• 데이터 접근과 할당이 O(1)로 굉장히 빠른 속도를 자랑합니다. Random access의 index 접근 방법이 배열 첫 data의 주소값에 offset을 더하는 산술 연산으로 이루어져 있기 때문입니다.
• Dynamic Array의 맨 뒤에 데이터를 추가하거나 삭제하는 것이 O(1)의 시간 복잡도이며 상대적으로 빠릅니다.

Linked List와 비교했을 때, Dynamic Array의 단점은

• Dynamic Array의 맨 끝이 아닌 곳에 data를 insert하거나 remove할 때, O(n)의 시간복잡도로 느린 편입니다. 메모리상에서 data들이 연속적으로 저장되어 있으므로, 이후의 data들을 모두 한 칸씩 shift 해야하기 때문입니다.
• resize를 해야할 때, 현저히 낮은 performance가 발생합니다.
• resize 시 필요 이상의 메모리 공간을 할당받기 때문에, 낭비되는 메모리 공간이 발생합니다.

마치며

Dynamic Array 자료구조에 대해 알아보았습니다. 동적 배열이 무엇인지 보다는, 어떻게 동작하며 어떤 특징이 있는 지에 대해 질문이 많이 들어오는 것 같습니다. 다른 자료구조와 비교해서 대답할 수 있도록 특징에 따르는 장, 단점도 준비하시길 바랍니다.

다음 시간엔 Linked List에 대해 알아보겠습니다.