정적 배열과 동적 배열

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

배열의 메모리 구조

단일 메모리 Chunk에 저장된다.
각 원소는 Base Address로부터의 오프셋을 통해 접근한다.

 

배열의 성능

원소 접근은 상수 시간 O(1)에 수행된다.
정적, 동적 배열은 성능 면에서 동일하다.
Cache locality (캐시 지역성)으로 인해 순차 접근에서 좋은 성능을 낸다.

 

Cache locality란?

특정 원소에 접근할 때 주변 원소들을 함께 가져와 접근 속도가 빨라지는 속성

 

배열을 사용해야 할 때

원소의 개수가 변하지 않는 경우(혹은 최대 개수가 정해진 경우)
순차 접근이 많은 경우
원소의 삽입 삭제가 적은 경우

• 주간 청소 당번 목록
• 최대 100명의 회원 목록

 

정적 배열

int arr[10];

• Stack에 할당된다.
• 선언된 블록이 끝나면 Stack에서 해제된다.

 

동적 배열

int *arr = new int[10];

• Heap에 할당된다.
• 개발자가 해제 시점을 정해주어야 한다.