[C언어] 동적 배열

🤔 동적 배열?

프로그램을 작성하다 보면 배열의 길이를 미리 정할 수 없는 경우가 있다. 이런 경우 C에서 해결 방법은 두 가지가 있다.

방법 1. 매우 큰 크기의 배열 사용
방법 2. 동적 배열 사용

방법 1은 불필요하게 많은 메모리가 사용될 수 있다. 그 해결책으로 제시된 것이 방법 2, 동적 배열이다. 동적 배열은 프로그램이 실행되는 동안 그 크기가 변할 수 있는 배열을 뜻한다. C++, C#, java 등에서는 동적 배열 라이브러리를 제공하지만 C언어에서는 동적 할당을 이용해 직접 구현해야 한다. 이 글에서는 그 방법에 대해 설명해보고자 한다.

---

🔨 구현 방법

1. 배열(${A}$)을 동적 할당한다.
2. 동적 배열의 크기를 나타내는 변수(${S}$), 마지막 요소의 인덱스를 저장하는 변수(${L}$)를 선언한다.
3. 배열에 요소를 추가할 경우 다음의 절차를 따른다.
   • ${L < S - 1}$ 인 경우
     a) ${L}$을 1 증가시키고 ${A[L]}$에 새로운 요소를 저장한다.
   • 그렇지 않은 경우
     a) ${2×S}$ 크기의 배열(${B}$)을 새롭게 동적 할당한다.
     b) ${B}$에 ${A}$의 요소들과 추가할 요소를 복사한다.
     c) ${A}$를 메모리에서 해제한다.
     d) ${A}$를 가리키던 포인터의 값을 ${B}$의 주소로 변경한다.

---

⏱ 시간복잡도

접근

접근할 때의 시간복잡도는 ${O(1)}$임을 쉽게 알 수 있다.

추가(Append)

한 요소를 추가하는 작업의 시간복잡도는 ${O(1)}$이다. 그 이유는 예를 들어 설명하겠다.

초기 크기가 0인 동적 배열이 있다고 하자.
1개의 요소를 추가하기 위해 필요한 복사 횟수는 0번이다.
2개의 요소를 추가하기 위해 필요한 복사 횟수는 1번이다.
4개의 요소를 추가하기 위해 필요한 복사 횟수는 3번이다.
8개의 요소를 추가하기 위해 필요한 복사 횟수는 7번이다.
16개의 요소를 추가하기 위해 필요한 복사 횟수는 15번이다.

요소 ${N}$개를 추가할 때 시간복잡도는 ${O(N)}$이므로 요소 1개를 추가할 때의 시간복잡도는 ${O(1)}$임을 알 수 있다. 이렇게 되는 이유는 확장된 배열의 크기가 마지막 확장 때 복사된 요소(${K}$)의 개수의 2배이기 때문이다. ${K+K/2+K/4+...+4+2+1 < 2K}$ 가 항상 성립하기 때문에 최악의 상황(${N=2^t-1}$, ${t>1}$)에서도 상수시간이 걸린다. 따라서 ${O(1)}$의 시간복잡도를 보장한다.