Array

• Array(배열)란?
• Array(배열)의 장점
  - 빠른 접근
  - 메모리 공간의 효율성
  - 낮은 캐시 미스 확률
  - 다차원 배열
• Array(배열)의 단점
  - 크기 제한
  - 삽입과 삭제의 어려움

• Array(배열)란?

배열은 동일한 데이터 타입의 요소들을 연속된 메모리 공간에 저장하는 자료구조입니다.

 

배열을 구성하는 각각의 값을 element(요소)라고 하며, 배열에서의 위치를 가리키는 숫자를 index(인덱스)라고 합니다.

• Array(배열)의 장점

- 빠른 접근 :

배열은 데이터를 연속된 메모리 공간에 저장하기 때문에 데이터의 크기와 index를 알고 있다면 원하는 위치의 element에 O(1)에 접근할 수 있습니다.

예를 들어 Java에서 short 타입의 배열이 크기가 3으로 선언 되었고 다음과 같이 메모리에 저장되었다면 1번 index를 찾기 위해 배열의 시작부터 2byte를 더한 위치에 있는 데이터를 읽으면 원하는 element에 접근할 수 있습니다.

 

즉, '배열의 시작 위치 + index * 데이터 크기 = 원하는 element의 위치' 가 성립합니다.

 

- 메모리 공간의 효율성 :

배열은 연속된 메모리 공간에 요소를 저장하기 때문에 부가정보 없이 데이터만 저장할 수 있어 메모리 공간의 효율성이 좋습니다.

 

- 낮은 캐시 미스 확률 :

캐시 메모리는 참조 지역성(Locality of Reference)의 원리를 활용하여 작동합니다.

이는 한 번 참조된 데이터에 인접한 메모리에 있는 데이터도 참조될 가능성이 높다는 원리입니다.

배열은 연속된 메모리 공간을 사용하기 때문에 한 번 참조한 데이터의 주변 데이터 또한 캐시에 미리 로드될 가능성이 높기 때문에 캐시 미스의 확률이 낮다고 말할 수 있습니다.

 

이를 오해하여 배열은 캐시 미스가 일어나지 않는다고 생각하면 안됩니다.

배열의 크기가 매우 크거나 순차적인 데이터의 접근이 아닌 임의의 데이터에 대한 접근을 한다면 캐시 미스가 발생할 수 있습니다.

 

- 다차원 배열 :

배열은 다차원으로 선언하여 행렬과 같은 다차원 데이터를 표현할 수 있습니다.

예를 들어 위 그림과 같은 5x5의 판에 임의의 위치에 3개의 돌을 놓아 2개의 돌이 인접하면 승리하는 게임을 만든다면, 이미 돌이 놓인 칸에는 돌을 추가로 놓을 수 없게 해야할 것입니다.

이때 특정 위치에 돌이 있는지를 판단하기 위해 2차원 boolean 배열을 선언하여 판단할 수 있습니다.

모든 칸에 위 그림과 같이 2차원 번호를 부여하고 boolean 배열을 선언하여

boolean[][] check = new boolean[5][5];

0~4의 사이의 정수를 랜덤하게 선택하여 돌을 놓는 3번의 과정 중 돌이 이미 놓여있다면 다시 놓을 위치를 선택하는 코드를 작성할 수 있습니다.

int count = 0;

while (count < 3) {
  int x = (int) (Math.random() * 5);
  int y = (int) (Math.random() * 5);
  
  if (check[x][y]) continue;
  else {
    check[x][y] = true;
    count++;
  }
}

이외에도 완전 탐색 등의 다양한 알고리즘에서 다차원 배열이 활용될 수 있습니다.

• Array(배열)의 단점

- 크기 제한 :

배열은 생성할 때 크기를 미리 정하고 이를 변경할 수 없습니다.

그렇기 때문에 미리 배열의 최대 크기를 예상해야 하고 이로 인해 불필요한 메모리 공간의 낭비가 발생할 수 있습니다.

 

- 삽입과 삭제의 어려움 :

배열은 element를 삽입하거나 삭제할 때 해당 element 위치 이후의 모든 element를 이동해야 하기 때문에 작업 비용이 큽니다.

이러한 과정은 일반적으로 반복문을 사용하여 구현됩니다. 다음과 같은 배열이 있을 때

int[] array = new int[]{4, 1, 6, 10, 2};

n번 index를 삭제하고 싶다면 반복문을 통해 다음과 같이 구현할 수 있습니다.

for (int i = n; i < array.length - 1; i++) {
  array[i] = array[i + 1];
}

array[array.length - 1] = null;

위 코드에서 n번 index의 값을 지우고 모든 element를 이동시켰지만 array의 크기는 여전히 5라는 문제가 발생합니다.

이를 해결하기 위해선 크기가 4인 배열을 선언하고 array를 복사하는 과정이 필요합니다.

for (int i = n; i < array.length - 1; i++) {
  array[i] = array[i + 1];
}

int[] newArray = new int[array.length - 1];

System.arraycopy(array, 0, newArray, 0, array.length - 1);

 

제가 예시로 들은 코드들은 Java기반입니다. 다른 언어에서는 다른 동작을 할 수도 있습니다.

참    고    자    료

- [자료구조] 배열 (Array) | yoongrammer

 

- [자료구조] 배열 (Array) 자료구조 알아보기 & Java 예제 코드(+ ArrayList) | 토발자_Hflug