배열 (Array)

정적 배열과 동적 배열

선언 시점에 크기가 고정되는 정적 배열(static array)은 크기를 바꿀 수 없다. 이 한계를 보완한 것이 동적 배열(dynamic array)로, 자바(Java)의 ArrayList, 파이썬(Python)의 list, C++의 vector가 대표적이다.

동적 배열은 내부적으로 실제 크기보다 넉넉한 용량(capacity)을 미리 확보해 두고, 요소가 가득 차면 보통 기존 용량의 1.5배에서 2배 크기의 새 배열을 할당한 뒤 기존 요소를 전부 복사한다. 복사가 일어나는 순간에는 O(n)이 들지만, 확장 빈도가 기하급수적으로 줄어들기 때문에 삽입 한 번당 평균 비용은 O(1)로 수렴한다. 이를 분할 상환 분석(amortized analysis)이라고 한다. 확장 시점을 예측하기 어렵다면 예상 크기를 미리 지정해 재할당 자체를 피하는 것이 실무에서 흔한 최적화다.

코드 예시

다음은 자바에서 배열의 접근, 순회, 중간 삽입을 보여주는 예시다. 중간 삽입에서 뒤쪽 요소를 밀어내는 반복문이 O(n) 비용의 정체다.

int[] arr = new int[5];
arr[0] = 10;
arr[1] = 20;
arr[2] = 40;

// 인덱스 접근: O(1)
int x = arr[2]; // 40

// 인덱스 2 자리에 30을 삽입: 뒤 요소를 한 칸씩 민다. O(n)
for (int i = 3; i > 2; i--) {
    arr[i] = arr[i - 1];
}
arr[2] = 30; // 결과: 10, 20, 30, 40, ...

장단점과 활용

배열은 구조가 단순해 오버헤드가 거의 없고, 인덱스 접근이 O(1)이며, 메모리 연속성 덕분에 순회 성능이 뛰어나다. 반면 크기 변경이 어렵고, 중간 삽입과 삭제가 느리며, 큰 배열은 그만큼 큰 연속 공간을 요구한다는 단점이 있다.

따라서 배열은 데이터 개수가 대체로 고정되어 있고 조회가 압도적으로 많은 경우에 적합하다. 조회보다 중간 수정이 잦다면 연결 리스트나 트리 계열 자료구조를 검토하는 것이 낫다. 또한 배열은 그 자체로 쓰이는 것 못지않게 스택(Stack), 큐(Queue), 해시 테이블(hash table), 힙(Heap)의 기반 저장소로 쓰인다는 점에서 모든 자료구조 학습의 출발점이 된다.

면접에서 이렇게 물어본다

• 배열의 인덱스 접근이 O(1)인 이유를 메모리 주소 계산 관점에서 설명해 보라.
• 배열과 연결 리스트의 순회 성능이 같은 O(n)인데도 실제 속도 차이가 나는 이유는 무엇인가.
• 동적 배열이 확장될 때 내부에서 어떤 일이 일어나며, 삽입의 분할 상환 시간 복잡도가 O(1)인 이유는 무엇인가.
• 배열의 중간에 요소를 삽입하면 어떤 비용이 발생하는지 설명하고, 이 비용을 피할 수 있는 자료구조를 제시해 보라.
• 정렬된 배열에서 특정 값을 찾는 가장 효율적인 방법과 그 시간 복잡도를 설명해 보라.