[DS] 1. 배열

배열(Array)?

int arr[5] = {0, 1, 2, 3, 4};

순서대로 번호가 붙은 원소들이, 연속적인 형태로 저장된 자료구조.

---

추상 자료형

데이터 : <인덱스, 요소> 쌍의 집합

연산 :

함수	설명
create(n)	n개 요소의 배열 생성
retrieve(i)1	배열의 i번째 요소 반환
store(i, item)	배열의 i번째 위치에 item을 저장

---

사용법

int arr[3] = {}; // 생성 (모든 원소를 0으로 초기화)
arr[0] = 10; // 0번째 index에 10 저장
std::cout << arr[0] << std::endl; // 10

// 1차원 배열
int arr1[5] = {0, 1, 2, 3, 4};

for (int i = 0; i < 5; ++i)
  std::cout << arr1[i]; // 01234
std::cout << std::endl;

// 2차원 배열 ([행][열])
int arr2[2][5] = {{0, 1, 2, 3, 4},
                  {5, 6, 7, 8, 9}};

for (int i = 0; i < 2; i++)
  for (int j = 0; j < 5; j++)
    std::cout << arr2[i][j]; // 0123456789
std::cout << std::endl;

---

특징

C++ 11부터 생긴 std::array가 존재한다.

부하는 동일하며, 사용법도 유사하다. 다만 이쪽이 좀 더 기능이 많고(.size(), at(), front() 등) 안정적이다.

장단점

• 장점
  • 임의 접근 시의 시간복잡도가 $O(1)$로 빠르다.
  • 캐시 효율성이 높다는 장점이 있다.

    두 장점 다, 같은 자료형이 연속적으로 저장된 형태인 점으로 인한 것이다. 배열의 주소값에, 자료형의 크기와 원하는 값의 인덱스 곱을 더하면 바로 위치가 계산되며, 자료를 캐시에서 처리할 때 인접 정보들을 한번에 가져와 쓸 수 있기 때문. 이는 다른 연속적 형태의 자료구조 특징이기도 하다.

    예시로, 블럭 크기가 다 똑같은 동네가 있는데, 영희네 집은 철수네 집보다 4블럭 옆에 있어요. 라고 하면 굳이 뒤져보지 않아도 정확한 좌표를 찍을 수 있을 것이며(임의 접근이 빠름), 실물 지도에서 위치를 확인할 때는 두 집이 가까우므로 지도를 번갈아 확인하지 않아도 될 것이다(캐시 효율성).

• 단점
  • 데이터 연속성을 유지하면서 중간 요소의 삽입/삭제를 원할 시, 시프트 비용으로 인해 느리다.
  • 선언 시 크기가 고정되기에, 동적으로 원소 갯수를 바꿀 수 없다.
  • 함수로 배열을 넘기게 된다면 배열의 크기 정보를 잃어버린다.

    배열 자체를 인자로 넘기면, 배열의 시작 주소 정보만이 넘어간다. 이를 방지하려면 크기를 같이 넘기거나, 레퍼런스(&)로 원본 자체를 보도록 사용해야 한다.

---

1. retrieve : 검색하다 ↩︎