📌 배열이란?
메모리상의 연속된 공간에 같은 타입의 데이터를 저장하는 자료구조
크기는 고정되어있고, 데이터는 일렬로 배치되어있다.
📌 배열의 작동방식
메모리 할당
배열을 선언하면 메모리에 연속된 공간이 할당된다. 각 요소는 동일한 크기의 메모리를 차지하므로, 특정 인덱스의 메모리 주소를 쉽게 계산할 수 있다.
주소 계산 공식:
`요소의 주소 = 시작 주소 + (인덱스 × 요소 크기)`
int자료형이라고 생각하고
시작주소 1004번
인덱스 10
요소의 주소 = 1004 + 4 \* 10 = 1044
접근 방식
이 공식 덕분에 배열은 인덱스만 알면 O(1) 시간에 어떤 요소든 바로 접근할 수 있다. 이를 랜덤 액세스(Random Access)라고 한다.
📌 배열의 특징
장점
- 인덱스를 통한 빠른 접근 (O(1))
- 메모리 효율성 (연속된 공간 사용)
- 캐시 친화적 (지역성 원리)
단점
- 크기가 고정적 (선언 시 크기 결정)
- 삽입/삭제 시 다른 요소들을 이동해야 함 (O(n))
- 메모리 낭비 가능성 (미사용 공간)
📌 여러가지 배열
동적배열
js나 python 같은 경우 위 배열과는 차이가 존재한다.
- 삽입, 삭제 가능
- 다양한 데이터타입 할당가능 등
HOW ?
{
elements: [메모리 포인터들],
length: 현재 길이,
capacity: 실제 할당된 용량
}- 배열의 길이
- 동적으로 데이터를 다룰 수 있는 이유는
배열의 크기를 크게 잡고, 그 이상 데이터가 늘어난다면
새로운 배열(더 높은 capacity)을
만들어 복사한다. - 그리고 기존 메모리의 데이터들을 해제한다.
- 다양한 데이터타입
- elements라는 포인터 배열을 생성하고,
그 안에 데이터의 주소를 입력한다. - 따라서 접근이 O(1)인 것은 변하지 않는다.
성능상의 차이점
캐시 효율성
**전통적 배열**: 높음 (데이터가 연속되어 있어 캐시 히트율 높음)
**동적 배열**: 낮음 (실제 데이터가 흩어져 있어 캐시 미스 가능성 높음)
메모리 사용량
**전통적 배열**: 효율적 (실제 데이터만 저장)
**동적 배열**: 오버헤드 (포인터 + 실제 데이터 + 메타데이터)
더보기
하지만 동적배열이라도 같은 타입의 데이터만 다룰 시
내부적으로 최적화를 하기도 한다.
📌 효율적으로 사용하려면?
1. 재할당 최소화
# 할당
# 나쁜 예: 반복적인 재할당
arr = []
for i in range(10000):
arr.append(i) # 여러 번 재할당 발생
# 좋은 예: 예상 크기 미리 설정
arr = [None] * 10000 # 또는 [0] * 10000
for i in range(10000):
arr[i] = i
# 더 좋은 예: 리스트 컴프리헨션
arr = [i for i in range(10000)]## 삽입
# 나쁜 예: 개별 삽입
new\_items = \[1, 2, 3, 4, 5\]
for item in new\_items:
arr.append(item)
# 좋은 예: 배치 삽입
arr.extend(new\_items) # 또는 arr += new\_items 2. 타입 일관성 유지
3. 순차 접근 활용
순차접근활용
# 좋은 예: 순차적 접근 (캐시 효율성 높음)
for i in range(len(arr)):
process(arr\[i\])
# 더 좋은 예: 직접 순회
for item in arr:
process(item)
# 인덱스와 값이 모두 필요한 경우
for i, item in enumerate(arr):
process(i, item) 랜덤접근 최소화
import random
# 나쁜 예: 무작위 접근
for \_ in range(1000):
random\_index = random.randint(0, len(arr) - 1)
process(arr\[random\_index\])
# 좋은 예: 필요한 경우만 랜덤 접근
random.shuffle(arr) # 한 번에 섞기
for item in arr:
process(item)