soowanlog
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
'자료구조' 카테고리의 다른 글
Linked List (0) | 2024.03.26 |
---|---|
B-tree (0) | 2024.03.19 |