정의
같은 타입의 데이터를 연속된 메모리에 저장하고, 인덱스로 즉시 접근할 수 있는 자료구조입니다.
배열은 자료구조 중에서도 가장 기본이면서, 성능 특성이 매우 명확합니다. i번째 원소 접근이 빠른 대신, 중간 삽입/삭제가 잦으면 비용이 커질 수 있습니다.
“연속된 메모리”라는 특성 때문에 CPU 캐시 친화적이라 반복문/순회가 빠른 편이고, 많은 알고리즘(정렬, DP, 투 포인터 등)의 기본 기반이 됩니다.
핵심 메시지
“배열은 빠른 접근을 얻는 대신,
삽입/삭제의 비용을 치르는 자료구조다.”
핵심 특징
배열의 본질은 인덱스 → 주소 계산이 가능하다는 점입니다.
배열은 i번째 원소를 찾을 때 “앞에서부터 i번 이동”하지 않습니다. 대신 시작 주소 + (i × 원소 크기)로 메모리 주소를 바로 계산해 접근합니다. 그래서 랜덤 접근(Random Access)이 O(1)입니다.
💡 TIP / 참고사항
“배열은 빠르다”는 말은 보통 연속 메모리 + 캐시 친화적이라는 뜻입니다.
같은 양의 데이터를 순회할 때, 연결 리스트보다 배열이 유리한 이유가 여기에 있습니다.
연산별 비용
접근/수정은 빠르고, 중간 삽입/삭제는 비쌉니다.
GOOD vs BAD
쓰임새가 명확합니다.
👍 GOOD
- 인덱스로 빠르게 접근해야 하는 경우 (DP, 정렬, 투포인터)
- 데이터가 연속적으로 저장되어 순회 성능이 중요한 경우
- 크기가 어느 정도 예측 가능하거나, 재할당 비용이 감당되는 경우
👎 BAD
- 중간 삽입/삭제가 매우 잦은 경우 (매번 shift 발생)
- 데이터 크기가 극단적으로 크고, 리사이즈 비용이 치명적인 경우
- 빈번한 삭제로 “구멍”이 생기는데 압축(compaction)이 어려운 경우
실무/코테에서 자주 쓰는 패턴
패턴과 함께 쓰면 “도구”가 됩니다.
1
Prefix Sum (누적합) 구간 합을 O(1)로 만들기 위해 dp처럼 누적값을 저장합니다.
2
Two Pointers (투 포인터) 정렬된 배열에서 양 끝/구간을 좁혀가며 조건을 만족하는 답을 찾습니다.
3
Sliding Window (슬라이딩 윈도우) 연속 부분 구간을 이동시키며 최적값(최대/최소)을 찾습니다.
💡 TIP / 참고사항
코테에서 “배열”은 단독 주제라기보다, 투포인터/누적합/슬라이딩 윈도우/DP 같은 기법의 무대가 됩니다.
즉, 배열 자체보다 “배열을 어떻게 쓰는지”가 더 중요합니다.
✅ 핵심 요약
- ✔️ 배열은 연속된 메모리에 저장되어 인덱스 접근 O(1)이 가능하다.
- ✔️ 중간 삽입/삭제는 shift 비용 때문에 O(n)으로 비싸다.
- ✔️ 누적합/투포인터/슬라이딩 윈도우/DP 등 알고리즘 패턴의 기반으로 가장 자주 쓰인다.
728x90