자료구조 배열 기본

Arrays

따로 증빙자료를 찾지 않고 생각의 흐름대로 작성한 것이라 사실과 다를 수 있음.
수정할 부분 혹은 추가할만한 내용이 있다면 댓글로 남겨주세요.

— 0

 

배열은 물론 데이터를 표현하는 기타 자료구조들이 없다고 가정하자. 서로 연관된 데이터라 해도 이를 프로그램상에 표현하기 위해 취할 방법은 변수를 여러개 만드는 것이다. 오늘의 기온 데이터를 적당히 샘플링해서 시간 순서에 따라 676개로 나눈걸 표현해보자.

int a = 10;
int b = 13;
int c = 11;
...
int zz = 21;

676개의 데이터를 표현하긴 했지만, 이해하기 힘든 코드가 될 것이고 쓸데없이 코드길이도 길어질것이고, 변수명 창작의 고통(어제날짜 기온도 표현하려면?)도 따른다.

 

 

— 1

 

  그럼 생각을 좀 바꿔서 어차피 서로 연관된 데이터니까 메모리상에 연속된 구간에다가 '차례대로' 넣고, 그냥 해당 연속 구간의 시작점과 그 끝이 어딘지만(총 몇개인지) 알면 되지 않을까?

 

(메모리 어딘가에 있는 3000번지부터 연속해서 데이터를 넣음.)

 

주의 : 실제론 배열로 만든 자료형(int, double 등)에 따라 표현하기 위한 메모리 크기가 달라지며, 이는 운영체제, CPU 등 다양한 변수로 인해 달라진다. 예를들어 boolean은 실제론 1bit만 필요하지만 실제론 1 byte 혹은 int형과 동일한 크기를 차지하기도 한다. c언어 처럼 sizeof 함수를 통해 현재 프로그램에서 판단하는 크기를 얻는 경우도 있고, 자바처럼 그냥 신경 안써도 되는 경우도 있다. 아무튼 이 글은 배열의 개념에 대해 작성한 것이니 그냥 3000→3001처럼 주소의 차이가 1인 것으로 가정함.

 

이제 arr이라는 변수에 3000이라는 주소값만 저장해보자. 그럼 기존에는 a,b,c,d,...,zz 까지 676개의 변수로 각각 표현해야 했던 데이터를 arr에 담겨진 3000 이라는 주소값과, 총 676개라는 정보만 있으면 표현할 수 있다.

 

1. 첫번째 데이터인 a에 접근하려면 3000 번지를 읽으면 된다.

2. 두번째 데이터인 b에 접근하려면 3000+1 번지를 읽으면 된다.

3. 마지막 데이터인 zz에 접근하려면 3000+675 번지를 읽으면 된다.

 

 

자바에서는 아래와 같이 표현된다. { } 또는 new int[676] 처럼 배열이 생성되면 메모리상 어딘가 연속된 공간에 위 그림과 같은 배열이 생성되며, arr에는 해당 주소가 리턴되서 들어간다. 그 이후로는 arr[n] 과 같이 n+1번째 데이터에 접근할 수 있다(배열 인덱스의 시작은 0이므로). 그럼 자바 시스템은 arr[n] 을 호출할 때 마다 곱셈연산을 통해 메모리에 int형 사이즈의 n배를 곱한 주소의 데이터를 가져오게 된다.

int[] arr = {10, 13, 11, ..., 21};
arr[0]; // 변수 a 였던것
arr[1]; // 변수 b 였던것
arr[675]; // 변수 zz 였던것

 

좀 더 상세히 보기 위해 더 raw한 언어인 c언어를 보자. int형 사이즈는 위에도 썼듯이 시스템마다 다를 수 있으므로 sizeof 함수를 통해 가져와서 메모리에 원하는 사이즈의 연속공간을 가져오는 malloc 함수로 공간을 가져온다. 이후 자바에서 배열 사용하는 것 처럼 arr[n] 으로도 사용 가능하지만, *arr, *arr+1 처럼 '+n' 을 통해서도 데이터를 가져올 수 있다.

int* arr = malloc(sizeof(int) * 676);
arr[0] = 10;
arr[1] = 13;
...
arr[675] = 21;

*arr; // 변수 a 였던것
*arr+1; // 변수 b 였던것
*arr+675; // 변수 zz 였던것

 

 

— 2

 

  그런데 뭔가 이상한 점이 있을꺼임. 자바에서 String을 생각해보자. 분명히 String[] str = new String[5]; 이런식으로 String도 배열을 만들 수 있다. 연속된 공간을 할당받아서 접근한다고 했는데 String은 마음대로 늘려서 작성할 수 있다. 그럼 얼마나 큰 크기의 String을 쓸지 어떻게 알고 미리 만들어둠?

 

  자바 혹은 대부분의 언어들은 자료형을 primitive type(원시형)과 reference type(참조형)으로 나눈다. 일반적으로 알고있는 소문자로 시작하는 녀석들 (int, boolean, byte, long, double, char 등)이 원시형이다. 얘네들은 메모리상에 실제값 그 자체가 저장된다.
그 이외 모든 타입은 참조형으로 (int[] 도 참조형임) 이 타입은 주소값을 저장한다. 위 예시에서도 보다시피 int[] arr에서 arr은 주소값인 3000을 가지고 있었다.

 

  참조형 타입에 대한 다음과 같은 배열을 보면 이해가 갈 것임. 즉 실제 데이터는 연속적이지 않지만, 실제 데이터가 있는 주소값을 저장하는 부분이 연속적임 (실제론 뭐 스택영역, 힙영역 등의 메모리 설명도 살짝 알면 좋지만 역시 배열 개념에 대한 내용이므로 넘어감)

String[] str = {"ABCD", "DDDDDDDD", "배열이다", "NN"};

 

 

— 3

 

  배열에 대한 기본 개념은 이정도면 될 것 같다. 그럼 개발자에게 이런 개념이 왜 필요하냐 하면, 언제 배열을 쓰고 언제 리스트를 쓰고 언제 map을 쓰고 언제 set을 쓰고... 를 알려면 기본 동작 원리와 개념을 이해하고 있어야 하기 때문이다. 외워서 하는건 한계가 있다. 원리를 알면 더 편하게 응용까지하며 사용할 수 있다. 그럼 위 내용들로 유추될 수 있는 배열의 특징을 생각해보자.

 

1. 순서가 있다. (메모리 순서대로)

2. 연속된 공간을 '미리' 정해서 사용해야 한다. (확정된 메모리 공간을 할당받아 써야 하므로)

3. N번째 데이터에 접근하기 위해 복잡한 과정 필요없이 그냥 덧셈과 곱셈 한번이면 가능하다. (n번째 데이터 접근 : 시작 주소 + (n-1) * 해당 자료형 크기)

 

위 특징들만 봐도, 갯수가 확정된 경우에 배열이 쓰일 수 있다는 점을 알 수 있다(이후 리스트 설명에서 확정되지 않은 경우 배열의 사용법도 다룬다.). 그럼 좀 더 들어가서 CRUD에 대해 배열이 어떻게 동작할 지 생각해보자.

 

- Create : 이미 new int[5];로 만들어져있는 데이터인데 새로운 6번째 데이터를 새로 배열에 넣으려고 한다. 어찌보면 어차피 메모리에 연속된 공간을 사용중이었으니까 메모리에 연속된 공간으로 하나 더 늘리면 되지 않나? 싶을 수 있으나, 이미 해당 공간이 사용중인지 아닌지 알 수 없으므로 그렇게 사용하면 안되기도 하고, 자바에서는 그렇게 할 수도 없다. (C는 raw해서 그렇게 할 수 있다. 물론 몇만번 그렇게 돌리다보면 메모리 충돌나서 뻗는다.)
유일한 방법은 새로운 연속된 공간을 다시 할당받고 기존에 있던 데이터를 모두 새로운 곳으로 옮기는 것이다. 코드로 나타내면 아래와 같다. (예외로 미리 더 큰 크기의 배열을 선언했고, 빈 공간에 넣을 경우엔 당연히 한 번에 넣을 수 있다.)

int[] arr = new int[5];
arr[0] = 1;
... // 무언가 넣음

int[] tmp = new int[6];
for (int i = 0; i < arr.length; i++) {
    tmp[i] = arr[i];
}
arr = tmp;

 

- Read : 몇번째 데이터라도 덧셈과 곱셈 한번씩이면 접근할 수 있으므로 매우 빠르게 접근할 수 있다.

 

- Update : Read와 마찬가지로 매우 쉽게 접근해서 수정 가능하다.

 

- Delete : Create처럼 어렵다. int[] arr = new int[5];에서 arr[3]을 제거하려고 한다. 그럼 Create의 예시처럼 new int[4]; 를 만든 후 복사해 넣어야 한다. 혹은 공간 자체는 안줄여도 된다고 해도 arr[3]이후의 모든 값을 한칸씩 앞으로 땡겨줘야한다. (예외로 배열의 크기를 사용하는 데이터의 갯수와 관계없이 유지해도 되고 마지막 데이터를 삭제하는 경우라면 한방에 가능하다.)

 

 

  그럼 이하와 같이 시간복잡도도 계산해볼 수 있다.

- 데이터 읽기, 수정 : O(1)

- 데이터 추가, 삭제 : O(N)

- 예외 : 배열에 빈 공간이 존재하는걸 허용하며 짜는 경우라면 마지막 데이터의 추가, 삭제는 O(1)

 

  최종적으로 데이터 갯수가 확정되어 있고, 데이터 읽기와 수정이 많고 새로운 데이터가 추가되거나 삭제되지 않는 경우 배열을 사용하기 적합하다고 알 수 있다. 이런식으로 원리를 알면 어떨 때 어떤 자료구조를 사용해야 하는가는 따로 외우지 않아도 유추해서 적합한 자료구조를 사용할 수 있다.

 

끝.