정적 배열(Array) vs 동적 배열(Vector)

정적 배열(Array)의 개념과 메모리 구조

정적 배열(static array)은 컴파일 시간 또는 프로그램 시작 시 크기가 고정되고, 메모리 공간이 연속적으로 할당되는 배열 자료구조입니다.

정적 배열의 정의

• 배열은 동일한 자료형의 데이터를 메모리 상에 연속적으로 배치하여 관리하는 자료구조입니다.
• 정적 배열은 선언 시 크기가 고정되며, 실행 중에는 변경할 수 없습니다.

int arr[5]; // 크기가 5로 고정된 정적 배열

정적 배열의 메모리 구조

• 메모리 상에 연속된 공간에 데이터가 저장됩니다.
• 배열의 첫 번째 주소 + 인덱스 × 자료형 크기로 빠르게 접근 가능 (O(1) 시간복잡도)
• 공간은 스택(stack)이나 전역 메모리(static/global segment)에 할당됩니다.

정적 배열의 주요 특징

• 장점:
  • 인덱스를 통한 빠른 접근 가능 (O(1))
  • 메모리 연속성 보장
  • 구현이 단순하고 빠름
• 단점:
  • 크기 변경 불가 (고정)
  • 메모리 낭비 가능성 존재
  • 삽입/삭제 연산 시 비효율적 (O(n))

---

동적 배열(Vector)의 개념과 동작 원리

동적 배열(dynamic array), 대표적으로 C++의 std::vector, Java의 ArrayList 등은 프로그램 실행 중 크기를 동적으로 조절할 수 있는 배열 형태의 자료구조입니다.

동적 배열의 정의

• 동적 배열은 처음에는 일정 크기로 시작하지만, 요소가 추가됨에 따라 자동으로 크기를 증가시키는 자료구조입니다.
• 내부적으로는 정적 배열을 활용하지만, 메모리 재할당(reallocation)을 통해 확장합니다.

std::vector<int> vec;
vec.push_back(10); // 요소 추가

동적 배열의 메모리 구조와 리사이징

• 메모리는 힙(Heap) 영역에 할당됩니다.
• 현재 용량이 부족해지면:
  • 더 큰 메모리 블록을 새로 할당
  • 기존 데이터를 새로운 배열로 복사
  • 기존 배열은 해제
• 일반적으로 2배씩 크기를 늘려 성능 저하를 최소화

동적 배열의 주요 특징

• 장점:
  • 크기 자동 조절
  • 배열처럼 인덱스 접근 가능 (O(1))
  • 라이브러리 제공 메서드로 편리한 사용
• 단점:
  • 크기 변경 시 복사 연산 발생 → 비싼 리사이징 비용 (O(n))
  • 메모리 공간이 분산될 수 있어 캐시 효율성 저하 가능

---

정적 배열과 동적 배열의 차이점 정리

항목	정적 배열 (Array)	동적 배열 (Vector)
메모리 할당 위치	스택 / 정적 메모리	힙 메모리
크기 변경	불가능	가능 (자동 증가)
초기 할당	고정 크기 지정 필요	유동적, 자동 확장
삽입/삭제	O(n) (전체 이동 필요)	O(n), 끝에 삽입은 amortized O(1)
접근 속도	O(1)	O(1)
구현 복잡도	단순	복잡 (내부 복사 및 재할당)
사용 예	C 배열, 임베디드 환경	C++ vector, Java ArrayList 등

 

---

동적 배열에서 '암시적 복사 비용'과 '성능 분석'의 중요성

동적 배열에서는 특히 다음 개념이 면접에서 자주 질문됩니다.

1. 암시적 복사 비용 (Implicit Copy Cost)

• 동적 배열이 용량을 초과하면, 새 배열을 할당하고 기존 데이터를 복사해야 합니다.
• 이 복사 비용은 amortized(평균)로는 O(1)이지만, 특정 시점에는 O(n)의 비용이 발생합니다.
• 이 점은 대량 데이터 처리 시 성능 병목으로 작용할 수 있습니다.

2. 시간복잡도 분석

• push_back()은 보통 O(1)이지만, 리사이징이 일어나면 O(n)
• insert(), erase()는 위치에 따라 O(n)
• 연속된 메모리 공간 사용으로 cache locality가 좋지만, 리사이징 시 복사 비용 존재

---

면접 대비를 위한 핵심 질문 및 설명 포인트

자주 나오는 면접 질문

• 정적 배열과 동적 배열의 차이를 설명해주세요.
• 동적 배열은 왜 메모리 재할당이 필요한가요?
• 벡터의 크기 증가 방식은 어떻게 결정되나요?
• 정적 배열과 벡터 중 어떤 상황에서 무엇을 선택할 건가요?
• 벡터의 삽입/삭제 시간복잡도는 어떻게 되나요?

답변 포인트 요약

• 정적 배열은 크기 고정, 메모리 연속, 빠른 접근
• 동적 배열은 자동 크기 조절, 복사 비용 수반, 유연성
• 내부적으로 리사이징이 어떻게 작동하는지, 성능 영향은 무엇인지 설명할 수 있어야 함
• 상황에 따라 어떤 배열이 적절한지 기준을 제시할 수 있어야 함

---

요약

• 정적 배열은 고정된 크기와 빠른 인덱스 접근이 특징이며, 구조가 단순하고 연속된 메모리 공간을 사용합니다.
• 동적 배열은 크기를 동적으로 조절할 수 있어 유연성이 높지만, 내부적으로 복사 및 재할당 비용이 발생합니다.
• 벡터는 정적 배열의 단점을 보완한 구조로, 리사이징 전략, 성능 분석, 메모리 사용 방식을 이해하는 것이 중요합니다.
• 면접에서는 단순한 구조 정의를 넘어서, 성능 분석, 내부 동작, 선택 기준, 시간복잡도 및 메모리 효율성까지 종합적으로 설명할 수 있어야 좋은 평가를 받을 수 있습니다.