배열(Array)

(static) Array

아래의 배열의 특성 두 가지만 이해하면 배열에 대해 다 이해한 것.

 

# 배열의 특성

1. 고정된 저장 공간(fixed-size)

2. 순차적인 데이터 저장(order)

 

 

배열은 선언 시에 size를 정하여, 해당 size만큼의 연속된 메모리를 할당받아 data를 연속적/순차적으로 저장하는 자료구조.

- 배열은 선언시부터 size가 정해져있고, 그 size만큼 연속된 메모리를 할당받아놓은 상태.

- 그리고 연속된 메모리에 data를 연속적/순차적으로 저장하는 자료구조.

 

 

실제 C언어에서 Array를 어떻게 선언하는지 보자.

int arr[5] = {3, 7, 4, 2, 6}

int형 데이터를 5개까지 저장하는 배열을 선언했다. → int arr[5]

선언과 동시에 초기화도 해줬다. → = {3, 7, 4, 2, 6}

int형 데이터 5개를 저장할 수 있는 공간에 5개의 int형 데이터를 집어넣었다.

이렇게 위의 예시에서는 배열의 size를 5개로 정했기 때문에, int형 데이터(4byte) 5개를 저장할 메모리 공간인 20byte를 미리 할당받는다.

- 지금 우리 컴퓨터 환경에서는 int형 데이터가 4byte이지만, 운영체제나 컴파일러에 따라서 어떤 경우에는 8byte가 될 수도 있다. 우리는 int형 데이터가 4byte라고 가정해보자.

- 이 경우, arr이라는 배열이 갖게될 메모리 공간은 20byte이다. 왜냐하면 4byte 5개를 저장할 메모리공간을 미리 할당받기 때문에.

이처럼 고정된 size를 갖게되기 때문에 static array라고 부르기도 한다.

보통 array라고 말하지만, Dynamic array와 비교하기 위해 static array라고 부르자.

4byte(int형 데이터) * 5(size) = 20byte가 미리 할당된다.

또한 배열의 데이터를 '연속적'이고 '순차적'으로 메모리에 저장한다.

 

int형 데이터 5개를 저장할 수 있는 배열인 arr을 선언하고, 선언과 동시에 초기화를 해줬다.

아직 할당이 되지 않은 메모리가 있다. 비어있기 때문에 어떤 데이터든 집어넣을 수 있다.

 

int형 데이터가 각각 4byte이다.

메모리 구조에서 하나하나 bit로 저장하고, bit가 8개 모이면 byte이고, byte마다 주소가 주어진다.

int형 데이터는 4byte이므로, 4개의 byte를 할당받는다.

 

 

 

3을 저장하고싶다면, 3에 해당되는 2진법 숫자가 저장이 된다.

배열이 어떻게 저장이 되는지, 어떻게 할당되는지 그림으로 보자.

 

4byte씩 5개가 있다. 이렇게 총 20byte가 할당이 되었다. arr이라는 배열이 할당받은 메모리 공간이다. 이 공간에다가 3, 7, 4, 2, 6 순서로 저장을 할거다.

이렇게 3, 7, 4, 2, 6을 저장을 한다. 2진법으로 보면 밑에서부터 '00000000..11' 이게 3.

이런식으로 숫자를 저장할 수 있다. int형 데이터를 저장했다.

 

## 데이터들의 주소값

여기서 알고가야할 것이 있다. 각 숫자가 저장된 공간이 4칸씩이다. 3이 저장된 곳으로 가고싶다. 그러면 3이 저장된 첫번째 주소로 찾아가면 된다.

7을 찾아가고싶으면, 7의 주소중 가장 앞에 있는 주소를 찾아가면 7을 찾을 수 있다. (여기서는 0x4AF5B)

가장 앞에 있는 주소값이 데이터들의 주소값이다.

 

 

## 배열의 주소

또 하나 알아야할 것이 있다.

arr이라는 이름 자체도, arr라는 array가 차지하고 있는 공간이 20byte로 크다. arr이라는 배열이 저장되어있는 메모리가 어딘지 찾아가려면 주소를 알아야한다. arr에도 주소가 저장되어있다.

배열이 할당받은 메모리 중에서, 맨 첫번째 주소(0x4AF57), 이 주소가 arr이 가리키고 있는 주소값이다.

그래서 우리가 선언을 하고 초기화를 한 다음에 arr[0] (arr의 첫번째 데이터)를 찾아가고싶다라고 하면, arr에 이미 0x4AF57이라는 주소가 저장되어있다. 그래서 '아, 0x4AF57로 가면 되겠구나, 거기서 첫번째 값인 3을 꺼내오자'

 

## 배열의 주소를 이용한 데이터 찾는 방법

그럼, arr[1] (arr의 1번 index)에는 어떤 데이터가 저장되어있는지 알고싶다면, 그곳 메모리로 찾아가야하는데 어떻게 갈까?

→ arr은 첫번째 주소값을 가지고 있다. arr덕분에 0x4AF57로 갈 수 있다. 1번째 인덱스는 4byte만큼 띄어진 곳에 저장이 되어있다. 왜냐하면 순차적/연속적으로 저장이 되어있으므로. 거기다가 4byte씩 띄어져있는 int형이므로 0x4AF57에서 4를 더하면 0x4AF5B의 주소값이 된다. 따라서 거기에 있는 '7'이라는 값을 가져올 수 있다.

이런식으로 arr[0] (arr의 0번째 인덱스)든, 1번째 인덱스든, 2번째 인덱스든 바로 접근이 가능하다.

 

ex: arr[3]에 접근하고 싶다면, arr이 가리키고 있는 0x4AF57에서 4byte만큼 세번 떨어져있는 곳인 0x4AF63으로 바로가면 된다.

이러한 배열의 특성 때문에 배열의 몇번째 인덱스라도 즉시 접근이 가능하다.

 

 

이걸 바로 random access, 또는 direct access라고 한다.

 

# Random access

• 메모리에 저장된 데이터에 접근하려면 주소값을 알아야한다.
  • 주소값을 알아야 메모리에 찾아가서 거기에 저장되어있는 데이터에 접근할 수 있다.
• 배열변수는 자신이 할당받은 메모리의 첫 번째 주소값을 가리킨다.
  • int arr[5] = { } 여기서 arr이라는 배열변수는 자신이 할당받은 메모리의 첫번째 주소를 가리키고있다.
• 배열은 순차적/연속적으로 저장되어있기 때문에, 첫 주소값만 알고 있다면 어떤 index에도 즉시 접근이 가능하다. 이를 direct access 또는 random access라고 부른다.
  • 첫번째 데이터가 저장된 주소값이 0x4AF55라면, 두번째 데이터가 저장된 주소값은 0x4AF55 + 4*1에 저장되어있다.
  • 3번째 데이터는 0x4AF55 + 4*2에 저장되어있을 것이고, n번째 데이터는 0x4AF55 + 4*(n-1)에 저장되어있다.
• 아무리 긴 배열이라도 한번의 연산으로 원하는 데이터에 바로 접근할 수 있다.
  • 즉, O(1)의 시간복잡도를 갖는다. → 덧셈 한번 만으로도 주소값을 알 수 있다.

 

 

다음에 배울 linked list는 메모리상에서 연속적/순차적으로 저장되어있지 않기때문에 random access는 불가능하다.

n번째 데이터에 접근하기 위해서 Array는 1번의 연산만 해도 되지만(O(1)), Linked list는 n번의 연산을 해야하기때문에 시간복잡도는 O(n)이 된다.

 

→ 이 차이가 굉장히 크다. 그래서 random access는 array의 굉장히 중요한 특징이고, random access가 가능한 이유는 연속적/순차적으로 저장되어있기 때문이다.

이렇게 몇번째 index에 접근을 하든, 계산을 한번만 해도 되기 때문에 O(1)으로 바로 접근을 할 수 있다. 

 

다시 array의 특징을 이야기해보면,

1. 고정된 저장공간 → 이 특징 때문에 static array의 한계가 생긴다.

2. 연속/순차적 저장 → 이 특징 때문에 random access가 가능.

 

# static array 한계

데이터의 개수가 정해져있는 경우에는 static array를 사용하는것이 매우 효율적이다.

하지만 선언시에 정한 size보다 더 많은 데이터를 저장해야하는 경우, 공간이 남아있지 않아 문제가 발생할 수 있다.

그렇다고 매번 크기가 엄청 큰 배열을 선언한다면 그만큼 메모리 비효율이 발생하게 된다.

이러한 문제점을 해결할 수 있는것이 바로 dynamic array.

 

만약, 프로그램이 시작하고 끝날때까지 데이터룰 5개만 저장하면 된다고 하면, 이렇게 정해져있는 경우에는 static array를 사용하는게 매우 효율적이다. 자투리 공간도 필요없고, 딱 필요한 만큼만 선언해서 사용하면 되므로.

 

5개만 필요할 것 같아서 사이즈가 5개인 array를 선언했는데, 프로그램이 실행되고보니 7개가 배열에 저장되어야한다. 하지만 메모리할당을 5개만큼만 이미 받았다. 따라서 2개는 저장을 할 수 없게된다.

 

그러면 처음 선언할 때 넉넉하게 사이즈가 100인 배열을 선언하면 되잖아? → 그만큼 자투리 공간이 많이 남기때문에 메모리 비효율이 발생하게된다.

이러한 문제점을 해결할 수 있는게 바로 dynamic array.

 

 

**출처 : 모든 내용은 인프런의 '코딩테스트 [ALL IN ONE]'강의를 기반으로 작성하였습니다.