한양과기고 에듀테크 수업도구 대시보드

인덱스 하나로 원소 하나에 바로 닿는, 가장 단순하고 가장 빠른 자료구조

배열(Array)은 같은 크기의 원소들을 메모리에 빈틈없이 연속으로 늘어놓은 자료구조다. 원소가 어디에 있는지 하나하나 찾아갈 필요 없이, 주소 계산 한 번이면 몇 번째 원소든 바로 꺼낼 수 있다. 이 페이지는 자료구조 커리큘럼의 첫 걸음이다 — 여기서 나오는 "연속 메모리", "capacity vs length", "상환 분석" 개념은 뒤에 나올 연결 리스트·스택·큐·해시테이블을 이해하는 기초가 된다.

1 왜 인덱스 접근은 O(1)인가

배열의 각 원소는 크기가 똑같고 메모리 위에 순서대로 나란히 놓인다. 그래서 i번째 원소의 주소는 "몇 번째인지 세어보지 않고" 곱셈 한 번으로 바로 계산된다:

주소(i) = base 주소 + i × 원소 크기

base = 1000, 원소 크기 = 4바이트 (int 배열)

인덱스

인덱스를 입력하고 계산해 보자. 배열 접근에는 "찾는" 과정이 없다 — 바로 계산만 있을 뿐이다.

2 정적 배열 vs 동적 배열

정적 배열 (Static Array)

크기가 선언 시점에 고정된다. C의 int arr[5]처럼 한 번 잡은 메모리 블록의 크기를 나중에 늘릴 수 없다. 꽉 차면 더 못 넣고, 자리가 남으면 낭비된다. 대신 오버헤드가 전혀 없어서 가장 빠르고 예측 가능하다.

동적 배열 (Dynamic Array)

Python list, JS Array, C++ vector가 이 방식이다. 내부적으로는 여전히 "고정 크기 블록"이지만, 꽉 차면 더 큰 블록을 새로 잡고 통째로 옮기는 일을 자동으로 해줘서 마치 무한히 늘어나는 것처럼 보인다.

동적 배열은 항상 두 숫자를 따로 관리한다: length(실제 들어있는 원소 수, 흔히 len())와 capacity(재할당 없이 더 넣을 수 있는 최대 자리 수, 실제로 확보된 메모리 크기). 아래 시뮬레이터에서 length가 capacity를 넘는 순간 무슨 일이 벌어지는지 직접 눌러 보자.

3 재할당(Reallocation) 시뮬레이터

capacity 1로 시작. "끝에 추가"를 눌러가며 재할당이 언제 일어나는지 관찰해 보자.

length

capacity

재할당 횟수

총 push 횟수

4 상환 분석 (Amortized Analysis) — 왜 평균 O(1)인가

재할당이 일어나는 순간엔 기존 원소를 전부 복사해야 하니 그 한 번은 O(n)이다. 그런데 capacity를 2배씩 키우면 재할당은 갈수록 점점 드물게 일어난다. capacity가 1→2→4→8→16…으로 자라는 걸 보자:

n번 push 하는 동안 재할당에서 발생하는 복사 총량은 대략 1 + 2 + 4 + … + n ≈ 2n 번에 불과하다. 결국 push n번의 총 비용이 O(n)이라서, 한 번당 평균(=상환) 비용은 O(1)이 된다. 이게 "가끔 비싼 연산이 있어도 여러 번에 걸쳐 나누면 평균은 싸다"는 상환 분석의 핵심 아이디어다. 만약 capacity를 매번 +1씩만 늘렸다면 재할당이 n번 모두 일어나 총 비용이 O(n²)이 되어버린다 — 그래서 실무 구현은 전부 배수 성장을 쓴다. 더 엄밀한 증명(회계 방법·잠재함수 방법)은 상환 분석 페이지에서 이어서 보자.

5 삽입·삭제는 "어디서" 하느냐에 따라 다르다

연산	시간복잡도	이유
끝에 추가 / 삭제	O(1) (상환)	뒤에 자리가 있으면 그냥 채우면 끝. 가끔만 재할당.
맨 앞에 삽입 / 삭제	O(n)	기존 원소를 전부 한 칸씩 밀어야(shift) 자리가 생긴다.
중간 i번째에 삽입 / 삭제	O(n)	i번 뒤의 원소 전부를 밀어야 한다 (최악 O(n), 평균 O(n)).
인덱스로 읽기 / 쓰기	O(1)	주소 계산 한 번, 이동 없음.

위 3번 시뮬레이터에서 "맨 앞에 삽입"과 "맨 앞에서 삭제"를 눌러보면, 원소들이 한 칸씩 순서대로 밀리는 애니메이션이 보인다 — 원소가 n개면 최대 n번 밀어야 하므로 O(n)이다. 반면 끝에서의 추가/삭제는 밀 원소가 없어서 즉시 끝난다.

6 그럼 중간 삽입이 느린 건 어떻게 해결할까?

배열은 "연속 메모리"라서 인덱스 접근이 빠른 대신, 중간에 뭔가 끼워 넣으려면 뒤 원소들을 전부 밀어야 한다. 만약 원소들을 메모리에 연속으로 두지 않고, 대신 각 원소가 "다음 원소의 위치"를 화살표(포인터)로 기억하게 만들면 어떨까? 그러면 중간에 원소 하나를 끼워 넣을 때 화살표 몇 개만 바꿔주면 되고, 뒤 원소들을 옮길 필요가 없어진다 — 대신 이번엔 "몇 번째 원소가 어디 있는지" 한 번에 계산할 수 없어서 인덱스 접근이 O(n)으로 느려진다. 이 트레이드오프를 확인하러 연결 리스트(Linked List)로 가보자.

7 언어별로 보기

Python — append(끝, 빠름) vs insert(0, x)(앞, 느림)

# append: 끝에 추가 — 상환 O(1)
arr = [1, 2, 3]
arr.append(4)          # [1, 2, 3, 4] — capacity 여유 있으면 즉시 끝

# insert(0, x): 맨 앞에 삽입 — O(n)
arr.insert(0, 0)       # [0, 1, 2, 3, 4] — 기존 원소를 전부 한 칸씩 뒤로 밀어야 함

C — 정적 배열은 크기가 컴파일 타임/선언 시점에 고정

// 크기 5로 고정 — 나중에 6번째 원소를 못 넣는다
int arr[5] = {10, 20, 30, 40, 50};

// i번째 주소 계산 (컴파일러가 내부적으로 하는 일)
// &arr[i] == (char*)arr + i * sizeof(int)
int third = arr[2];   // O(1): base + 2*4 만큼 떨어진 곳을 바로 읽음

한 줄 정리 — 배열이 빠른 이유는 "연속된 메모리 + 곱셈 한 번"으로 인덱스 접근을 O(1)에 끝내기 때문이고, 동적 배열은 capacity를 2배씩 키우는 재할당으로 그 편리함을 유지하면서 상환 O(1) 추가까지 얻어낸다 — 단, 끝이 아닌 위치의 삽입·삭제는 여전히 원소를 밀어야 하는 O(n)이라는 대가가 남는다.