정적 배열과 동적 배열의 차이는 “크기를 누가 관리하느냐”에 있다. 정적 배열은 생성할 때 크기가 정해지고, 그 크기를 직접 바꿀 수 없다. 반면 동적 배열은 겉으로는 계속 add할 수 있는 리스트처럼 보이지만, 내부적으로는 더 큰 배열을 새로 만들고 기존 데이터를 복사하면서 크기를 늘린다.
Java의 ArrayList, C++의 vector가 대표적인 동적 배열이다. 이름은 리스트나 벡터지만, 핵심은 결국 배열이다. 그래서 인덱스 접근은 O(1)이고, 데이터가 연속 메모리에 놓이기 때문에 순차 순회도 빠르다.
동적 배열은 어떻게 커질까
동적 배열은 내부에 size와 capacity를 따로 가진다. size는 실제로 들어 있는 원소 수이고, capacity는 현재 내부 배열이 담을 수 있는 최대 개수다. 원소를 추가했는데 아직 여유 공간이 있으면 O(1)에 끝난다. 하지만 size가 capacity에 도달하면 더 큰 배열을 만들고 기존 원소를 모두 복사해야 한다.
capacity = 4, size = 4
[A][B][C][D]
E를 추가하려면 capacity를 늘린 새 배열을 만든다.
[A][B][C][D][E][ ][ ][ ]이 순간의 추가는 O(n)이다. 그런데 매번 이런 일이 생기는 것은 아니다. 보통 용량을 1.5배나 2배 정도로 늘리기 때문에, 많은 add 연산을 길게 보면 평균 비용은 O(1)에 가깝다. 이를 분할 상환(amortized) O(1)이라고 부른다.
정적 배열이 맞는 경우
정적 배열은 크기가 명확할 때 단순하고 빠르다. 월별 데이터처럼 정확히 12개만 필요하거나, 고정 크기 버퍼처럼 크기를 미리 알고 있는 경우에는 굳이 동적 배열이 필요 없다. 크기가 정해져 있으면 추가적인 확장 정책이나 여유 공간에 대해 생각할 필요도 줄어든다.
다만 크기를 잘못 잡으면 문제가 생긴다. 너무 작게 잡으면 더 담을 수 없고, 너무 크게 잡으면 메모리가 낭비된다. 크기가 입력이나 사용자 행동에 따라 계속 달라지는 상황에서는 동적 배열이 더 다루기 쉽다.
동적 배열이 맞는 경우
대부분의 애플리케이션 코드에서는 동적 배열을 더 자주 쓴다. 데이터가 얼마나 들어올지 정확히 모르지만, 인덱스 접근이나 순차 처리가 필요할 때 잘 맞는다. 끝에 추가하는 작업이 많고, 중간 삽입/삭제가 핵심이 아니라면 ArrayList 같은 구조가 안정적인 기본 선택이다.
성능이 중요한 경우에는 예상 크기를 알고 있을 때 초기 용량을 지정하는 것도 좋다. Java에서는 new ArrayList<>(10000), C++에서는 reserve(10000)처럼 미리 공간을 잡아두면 중간중간 재할당과 복사를 줄일 수 있다.
면접에서 말할 포인트
정적 배열은 크기가 고정되어 단순하지만 확장이 어렵다. 동적 배열은 내부적으로 더 큰 배열을 재할당하고 복사하면서 확장한다. 개별 확장 시점에는 O(n)이 들 수 있지만, 여러 번의 추가를 평균 내면 amortized O(1)이다. 그래서 랜덤 접근과 끝쪽 추가가 많은 상황에서는 동적 배열이 좋은 기본 선택이 된다.