배열(Array) : C++

1. 배열이란?

배열은 메모리 상에 원소(자료)를 연속하게 배치한 자료구조이다. 배열에 들어가 있는 각 변수를 요소(element)라고 하고, 배열의 개별 요소에 접근하기 위해서는 원하는 요소의 순서를 알려주는 인덱스(index)를 사용하면 된다. C++에서 배열의 인덱스는 0부터 시작한다.

일반적으로 C++에서 배열을 선언한 뒤에 배열의 길이를 변경하는 것이 불가능하지만 자료구조에서 일컫는 배열은 길이를 마음대로 줄이거나 늘릴 수 있다고 생각한다.

2. 배열의 성질

• 배열의 접근은 \(O(1\))의 시간 복잡도를 갖는다.

배열의 첫번째 변수에는 시작 주소값이 저장되고, n번째 원소를 찾기 위해서는 시작 주소값에서 n을 더하면 되는 단순한 사칙연산만이 수행되기 때문이다.

• 논리적 저장 순서와 물리적 저장 순서가 일치한다.

메모리 상에 데이터가 순차적으로 저장되기 때문에 주소값을 계산할 때 편하다.

• 캐시 적중률(Cache hit rate)이 높다.

캐시 적중률은 (캐시 적중횟수)/(총 접근 횟수)로 캐시 지역성(Cache Locality)에 의해 높아진다. 캐시 지역성이란 기억장치 내의 정보에 균일하게 접근하는 것이 아니라 어느 한 순간에 특정 부분을 집중적으로 참조하는 특성인데, 데이터 접근이 시간적, 혹은 공간적으로 가깝게 일어난다면 지역성이 높아진다. 배열의 경우 연속된 메모리 공간에 저장되기 때문에 공간 지역성이 증가하여 캐시 적중률이 높다. 캐시 적중률은 캐시를 갖는 컴퓨터의 성능을 나타내는 척도로 이용되며, 적중률이 높을 수록 우수하다는 것을 의미한다.

• 메모리 할당에 제약을 받을 수 있다.

연속된 메모리에 값을 저장해야 하기 때문에 메모리에 배열을 할당할 때 제약이 있을 수 있다.

3. 배열의 연산

• 임의의 위치에 있는 원소 확인/변경 - \(O(1)\)
• 원소를 끝에 추가 - \(O(1)\)
• 마지막 원소를 제거 - \(O(1)\)

  주소값을 이용해 가볍게 할 수 있는 수준의 연산은 \(O(1)\)의 시간 복잡도를 갖는다.

• 임의의 위치에 원소를 추가 / 제거하는 과정 - \(O(N)\)

  원소를 추가 혹은 제거하기 위해 해당 위치 뒤의 원소들을 모두 한 칸씩 밀거나 당겨와야 하기 때문이다. Big-O 표기법에 의해 알고리즘 효율성의 상한선 기준으로 표기하는 것을 생각해보자.