정적 배열 vs 동적 배열

5 min read

정적 배열 vs 동적 배열

고정 크기 배열과 자동 확장되는 배열의 차이

비교 요약

구분정적 배열동적 배열
크기컴파일/생성 시 고정런타임에 자동 확장
메모리스택 또는 힙힙
예시int arr[10], new int[10]ArrayList, Vector
확장불가능가능 (재할당)

정적 배열 (Static Array)

특징

  • 선언 시 크기가 고정됨
  • 크기 변경 불가
  • 빠른 할당/해제 (스택 배열의 경우)

예시

// Java - 크기 고정
int[] arr = new int[10];  // 10개 고정
 
// C
int arr[10];              // 스택에 고정 크기 할당
int* arr = malloc(10 * sizeof(int));  // 힙에 고정 크기 할당

문제점

int[] arr = new int[10];
// 11번째 요소를 추가하려면?
// → 새 배열 생성 후 복사해야 함 (수동)

동적 배열 (Dynamic Array)

특징

  • 필요에 따라 자동으로 크기 확장
  • 내부적으로는 정적 배열 사용
  • 용량 초과 시 더 큰 배열로 재할당

작동 원리

초기 상태 (capacity=4, size=3):
+---+---+---+---+
| A | B | C |   |
+---+---+---+---+

요소 추가 (size=4):
+---+---+---+---+
| A | B | C | D |
+---+---+---+---+

또 추가하면? → 용량 부족!
1. 새 배열 생성 (capacity=8)
2. 기존 데이터 복사
3. 새 요소 추가
4. 기존 배열 해제

+---+---+---+---+---+---+---+---+
| A | B | C | D | E |   |   |   |
+---+---+---+---+---+---+---+---+

확장 전략

// Java ArrayList의 확장
newCapacity = oldCapacity + (oldCapacity >> 1);  // 1.5배
// 예: 10 → 15 → 22 → 33 → ...
 
// C++ vector의 확장 (구현체마다 다름)
newCapacity = oldCapacity * 2;  // 2배
// 예: 10 → 20 → 40 → 80 → ...

시간복잡도 분석

추가 연산 (add/push_back)

일반적인 추가: O(1)
용량 초과 시 추가: O(n) - 전체 복사 필요

하지만 분할 상환 분석(Amortized Analysis):
→ 평균 O(1)

분할 상환 분석

n개 요소 추가 시 복사 횟수:
- 1 → 2로 확장: 1번 복사
- 2 → 4로 확장: 2번 복사
- 4 → 8로 확장: 4번 복사
- ...
- n/2 → n으로 확장: n/2번 복사

총 복사: 1 + 2 + 4 + ... + n/2 = n - 1

n개 추가에 n-1번 복사 → 평균 O(1)

코드 예시

Java ArrayList

ArrayList<Integer> list = new ArrayList<>();  // 초기 용량 10
 
list.add(1);  // O(1)
list.add(2);  // O(1)
// ...
 
list.get(5);     // O(1) - 인덱스 접근
list.remove(0);  // O(n) - 앞쪽 삭제 시 이동 필요
 
// 용량 미리 지정 (성능 최적화)
ArrayList<Integer> list = new ArrayList<>(10000);

C++ vector

vector<int> v;
v.push_back(1);  // O(1) amortized
v.push_back(2);
 
v[0];            // O(1)
v.at(0);         // O(1) + 범위 체크
 
v.reserve(10000);  // 용량 미리 확보
v.shrink_to_fit(); // 여유 공간 해제

메모리 효율성

실제 사용: 6개
내부 용량: 8개
낭비: 25%

→ shrink_to_fit() 또는 trimToSize()로 최적화 가능
→ 하지만 추가 삽입 시 다시 확장 필요

면접 포인트

  1. ArrayList의 add() 시간복잡도는?

    • 일반: O(1), 확장 시: O(n)
    • 분할 상환 O(1) (Amortized O(1))

  2. 왜 2배 또는 1.5배로 확장하는가?

    • 너무 작으면: 잦은 재할당으로 O(n²)에 가까워짐
    • 너무 크면: 메모리 낭비
    • 1.5~2배가 시간/공간 균형점

  3. ArrayList vs LinkedList 언제 사용?

    • 랜덤 접근 많음 → ArrayList
    • 앞쪽 삽입/삭제 많음 → LinkedList

  4. 초기 용량을 지정하는 이유는?

    • 예상 크기만큼 미리 할당하면 재할당 비용 절감

Backlinks