[2기 대구 이현복] Data Structure - Array

안녕하세요

대구 멤버십 21기 이현복 입니다.

Data Structure 중 첫번째 주제인 Array에 대한 이야기 입니다.

자료구조를 공부하게 되면 가장 먼저 보게 되는 것이 Array 즉 배열인데요

흔히 배열을 '일련의 연속적인 메모리 위치'로 인식하고 있습니다.

물론 일련의 연속적인 메모리 위치로 구현되는 것이 보통이지만

좀더 배열이란 구조를 효율적으로 사용하자면

'인덱스와 값의 쌍으로 구성된 집합'이라는 것을 생각해 보아야 합니다.

즉 정의된 인덱스는 그와 관련된 값을 가지고 있기 때문에 인덱스에 의미를 부여할 수가 있습니다.

수학 용어로는 대응(Correspondence) 또는 사상(Mapping)이라고도 합니다.

배열에 기본적인 연산은 create, retrieve, store 가 필요합니다.

create : 새로운 배열을 생성하는 함수

retrieve : 인덱스에 해당하는 값을 반환하는 함수

store : 인덱스에 해당하는 값을 저장하는 함수

즉 인덱스에 의한 직접적인 참조, Direct Access가 가능합니다.

그러면 이러한 특성을 가지는 배열을 직접 만든다고 생각해 봅시다.

어떤 방법이 가장 좋을까요?

인덱스 위치에 값이 있어야 하므로 인덱스는 값이 있는 위치의 주소가 될 것이고

각 인덱스를 따로 관리한다는 것은 어렵기 때문에 특정 위치부터 연속된 인덱스를 부여하게 될 것입니다.

위 그림과 같이 배열의 이름은 배열의 첫 원소인 array[0]의 주소를 기본 주소(base address)로 가지게 됩니다.

인덱스에 해당하는 주소는 arr[i] = a + i * sizeof(int) 가 되는데 여기서 a는 기본 주소 입니다.

물론 C언어에서는 배열의 특정 원소에 접근하기 위해 그 타입의 크기와 인덱스를 곱하지는 않습니다.

그러므로 (arr + i) 와 &arr[i]는 항상 같으며, *(arr + i)와 arr[i]도 같은 값이 됩니다.

즉 배열은 정수를 가리키는 포인터(여기서의 arr의 경우) 입니다.

일반 포인터를 선언하는 것과 차이라면 배열의 경우 정수를 위한 메모리 위치가 예약되어 진다는 것입니다.

배열을 만들때 크기를 지정해 주어야 하지만 필요한 정확한 크기를 모를 경우가 있습니다.

또는 만들고 싶은 크기를 입력받아서 만들고 싶을 수가 있습니다.

이러한 경우 동적 할당을 통하여 생성 할 수 있습니다.

메모리를 할당하는 함수로 malloc, calloc, realloc를 들 수 있습니다.

malloc : 요구한 메모리 사이즈만큼 메모리를 할당하고 그 주소를 반환 합니다.

calloc : 요구한 메모리 사이즈로 요구한 수만큼 메모리를 할당하고 0으로 초기화 하여 주소를 반환합니다.

realloc : 할당 받은 메모리의 크기를 변경하기 위해 재 할당하는 함수 입니다.

즉 int arr[5] 를 동적으로 할당 받는 다면

int *arr = ( int * ) malloc ( sizeof ( int ) * 5 );

int *arr = ( int * ) calloc ( 5, sizeof ( int ) );

로 할당 받을 수 있습니다.

다차원의 배열을 할당한다면 다음과 같이 쓸수 있습니다.

int arr [ row ] [ col ];

int **arr;

arr = ( int ** ) malloc ( sizeof ( int ) * row );

for ( i = 0; i < row; i ++ ) arr [ i ] = malloc ( sizeof ( int ) * col );

다음과 같이 2차원 3차원 등의 다차원 배열을 선언하는 경우

정적 배열과 동적 배열은 다른 모양으로 선언되게 됩니다.

정적 배열로 선언한 경우 동적 배열로 선언한 경우

정적 배열로 선언한 경우 2차원 이상의 배열도 일련의 연속된 메모리로 선언되기 때문에

적절한 계산을 통하여 임의 접근을 할 수가 있습니다.

동적 배열로 선언한 경우 특정 포인터 배열에서 각각의 배열을 가리키는 형식으로 선언되기 때문에

각각의 부분으로 나누어 계산을 해 주어야 합니다.

물론 C언어에서 배열의 크기에 상관없이 할당하기 때문에 시도 할 수는 있으나 추천하는 방법은 아닙니다.

배열은 같은 타입의 데이터 모임이므로 다른 타입의 데이터를 넣고 싶을 때는 구조체(struct) 를 사용합니다.

구조체는 데이터 항목의 집단으로서 각 항목은 타입과 이름으로 식별 됩니다.

구조체를 만들 때 고려해야 하는 것은 순서에 따라 크기가 다르다는 것입니다.

위 그림에서 보다싶이 들어가는 순서에 따라 크기가 달라지게 됩니다.

각 타입별 사이즈만 보자면

name : 10

age : 4

grade : 8

이렇게 22바이트가 필요하지만

각 데이터 타입의 배수의 공간에만 들어가도록 되어 있기 때문에

중간중간에 빈 공간을 남겨두고 메모리를 할당 받게 됩니다.

이렇게 구조체 사이에 생기는 공간을 보고 '패딩(Padding)' 이라고 합니다.

메모리를 연속해서 할당할 경우 추가적인 연산이 많이 생기기 때문에

최대 할당되는 메모리 타입을 기준으로 할당 하는 것이 성능상에서 좋습니다.

그렇기 때문에 구조체를 설계할 때는 패딩을 잘 고려하여 최소한이 되도록 배치하는 것이 중요합니다.

기본 구조체 사이즈를 임의로 조정하고 싶다면

#pragma pack을 이용하거나

#pragma pack(puch, 2)   // 기본 구조체 사이즈를 2바이트형으로 변경.

#pragma pack(pop)        // 기본 구조체 사이즈를 기본 바이트로 변경.

Visual Studio에서는 속성 페이지에서 할당을 설정 할 수 있습니다.

자료구조 중 첫번째인 배열은 가장 기초적이고 쉬우면서도 가장 중요한 자료구조입니다.

물론 대부분 쉽게 사용하시기 때문에 머 굳이 알아야 하느냐? 라고 묻긴 하지만

중요한 만큼 한번더 집고 넘어 갈 수 있다면 좋겠습니다.