동적 배열(Dynamic Array)

동적 배열(Dynamic Array)이란?

동적 배열은 배열과 유사하지만, 크기를 미리 지정하지 않고 필요에 따라 크기가 동적으로 변경되는 자료구조입니다. 이러한 동적 배열은 컴퓨터 과학에서 매우 중요한 자료구조 중 하나이며, 많은 프로그래밍 언어에서 기본적으로 제공됩니다.

 

동적 배열은 메모리 상에서 연속된 공간에 요소들을 저장하는 배열과 달리, 요소들이 반드시 연속된 공간에 저장되지 않습니다. 대신, 배열의 크기가 변경될 때마다 새로운 메모리 공간을 할당하고, 기존의 데이터를 새로운 공간으로 복사하는 방식을 사용합니다.

 

이러한 방식으로 동적 배열은 필요한 만큼의 메모리를 동적으로 할당하여, 크기를 미리 지정하지 않아도 되므로 매우 유연한 사용이 가능합니다. 동적 배열은 일반적으로 배열과 같은 인덱스 방식으로 요소에 접근할 수 있으며, 배열의 크기를 변경하는 기능도 제공됩니다.

 

요소를 추가하려면 일단 배열에 추가할 요소를 할당하고, 이전 요소들을 모두 복사하여 새로운 배열에 저장해야 합니다. 이때, 크기가 큰 배열을 복사하는 경우에도 시간과 메모리의 소비가 커지므로, 동적 배열은 대개 배열의 크기를 늘리는데 사용되는 전략적인 알고리즘을 사용합니다.

 

동적 배열은 일반적으로 O(1)의 시간 복잡도를 가집니다. 하지만 요소를 추가하거나 삭제하는 경우에는, 새로운 공간을 할당하고 이전 요소들을 복사해야 하므로 최악의 경우 O(n)의 시간 복잡도를 가지게 됩니다.

 

동적 배열은 다음과 같은 상황에서 유용하게 사용될 수 있습니다:

• 배열의 크기를 미리 알 수 없는 경우
• 배열의 크기가 계속해서 변경되는 경우
• 메모리 공간이 제한적인 경우

대표적인 동적 배열 구현체로는 C++ std::vector, 파이썬의 list, 자바의 ArrayList 등이 있습니다. 이들은 각각의 언어에서 제공하는 라이러리를 통해 사용할 수 있으며, 동적 배열의 특성을 충분히 활용할 수 있습니다.