[부트캠프] 알고리즘 - 동적 배열(Dynamic Array)

Claire·2024년 9월 4일

배열 요소의 삽입/삭제

배열이란

번호(인덱스)와 인덱스에 대응하는 데이터 값들로 이루어진 자료 구조

예를 들어

int num[] = {3, 4, 67, 245, 765};

num[0] = 3;

과 같이 num이라는 배열이 있을 때, 첫번째 자리인 0번 인덱스에 해당하는 데이터값은 '3'이다.
이처럼, 인덱스 번호와 각 인덱스 번호에 해당하는 데이터 값으로 이루어진 데이터의 집합체가 "배열(Array)"이다.

⁕⁕ 프로그래밍 언어에서 배열은 1번이 아닌 0번부터 시작한다. 따라서, 마지막 배열의 인덱스는 전체 길이 -1과 같다.
예를 들어 위 num이라는 배열의 길이는 총 5개로 '5'이지만 인덱스는 0번부터 시작하기 때문에 결국 마지막 인덱스는 "4"이다.

배열의 장/단점

배열의 장점
1. 구조가 단순하여 정보 자체를 기억하는 메모리 외에 추가 소모 메모리가 없다.
2. 배열의 크기가 커지더라도 검색 속도가 일정하다

배열의 단점
1. 연속된 메모리 공간에 배치되어 있어야 하므로 중간의 요소를 삭제하거나 새로운 요소를 삽입할 수 없다.

배열 요소의 삽입/삭제

: 배열은 일반적으로 삽입/삭제가 안되는 것으로 알려져 있는데 일종의 고정 관념이다. 즉, 요소의 삽입/삭제가 가능하다

char arr[16] = "abcdef";

void main() {
	printf("최초: %s\n", arr);

	// 추가
	// memmove("복사될 대상", "복사할 소스", "복사할 크기")
	memmove(arr + 3 + 1, arr + 3, strlen(arr) - 3 + 1);
	arr[3] = 't';
	printf("삽입 후: %s\n", arr);

	// 삭제
	memmove(arr + 1, arr + 2, strlen(arr) - 1);
	printf("삭제 후: %s\n", arr);
}

삽입 전

a	b	c	d	e	f

삽입 후

a	b	c	t	d	e	f

위 코드에서 추가 및 삭제를 함수로 빼서 만들어보면 아래 코드와 같다.

char arr[16] = "abcdef";

void Insert(int idx, char ch) {
	memmove(arr + idx + 1, arr + idx, strlen(arr) - idx + 1);
	arr[idx] = ch;
}

void Delete(int idx) {
	memmove(arr + idx, arr + idx + 1, strlen(arr) - idx);
}

void main() {
	// 추가
	Insert(3, 't');

	// 삭제
	Delete(3);
}

동적 배열

heap을 이용하여 배열의 크기를 컴파일 단계가 아닌 실행 시간(=run time)에 가변적으로 변경할 수 있는 배열

기존의 (정적)배열의 중간에 새로운요소가 삽입되더라도 배열의 크기가 자동으로 늘어나지 않는다.
예를 들어 위 코드에서 arr[16]은 메모리가 16개인 배열이기에 들어갈 수 있는 최대 문자의 수는 "15개"이다. 이렇듯 메모리의 크기가 늘어나지 않는 배열의 한계를 극복하기 위해 생겨난 것이 "동적 배열"이다. 즉, 실행 중에 필요한만큼 늘었다 줄였다하며 신축성이 있는 배열이 필요해서 생성된 것이 "동적 배열"
기존 할당된 메모리를 재할당하는 realloc 함수를 사용하면 가능
C++ 라이브러리인 MFC, STL 등 동적 배열 클래스 내부의 원리는 거의 동일하다

데이터 추가/삭제 시 동적 배열의 처리 순서

최초의 초기 메모리 할당 및 추가할 메모리 사이즈 설정
데이터 추가
메모리 할당 이상의 데이터를 추가했을 때 처리 (추가할 메모리만큼 사이즈를 늘려준 뒤 데이터 할당)
데이터 삭제
삭제된 데이터의 크기만큼 메모리 사이즈 줄이기

int* arr;
unsigned size = 0;
unsigned growby = 5; // unsinged: 정수 중에서 음수를 무시하고 양수값만 받아서 사용하겠다는 의미 (=음수값은 허용하지 않겠다는 의미이기에 음수값이 들어오면 오류 발생)
// 예를 들어 char형은 1바이트로 표현 가능 범위가 -128에서 +127까지 가능한데 앞에 unsigned를 붙이게 되면 표현 범위가 0에서 255 사이의 값으로 표현이 가능하게 된다.
unsigned num = 0;

void InitArray(unsigned nSize, unsigned nGrowby) {
	// 초기값 복사
	size = nSize;
	// 추가할 메모리 사이즈 초기값 복사
	growby = nGrowby;
	//1. 최초의 초기 메모리 할당
	arr = (int*)malloc(size * sizeof(int)); // 초기 메모리 할당
}

void Insert(int idx, int value) {
	
	// 기존의 데이터 사이즈와 필요한 데이터의 사이즈 체크
	int need = num + 1; // 추가로 들어갈 데이터의 메모리 개수

	if (need > size) { // 필요한 데이터 공간이 부족할 때 
		// 재할당(추가할 메모리 사이즈 재할당)
		size = need + growby;
		arr = (int*)realloc(arr, size * sizeof(int));
	}
	
	// 2. 데이터 추가
	// memmove(대상, 소스, 사이즈)
	memmove(arr + idx + 1, arr + idx, (num - idx) * sizeof(int));
	arr[idx] = value;
	num++; // 현재 메모리 상에 들어가 있는 데이터의 개수
}

void UnInitArray() {
	free(arr);
}

void PrintArray() {
	for (int i = 0; i < num; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void main() {
	//1. 최초의 초기 메모리 할당 및 추가할 메모리 사이즈 설정
	InitArray(10, 5);

	//2. 데이터 추가, 메모리 할당 이상의 데이터를 추가했을 때 처리
	for (int i = 0; i <= 8; i++) {
		Insert(num, i);
	}

	PrintArray();
	Insert(3, 10);
	PrintArray();
	Insert(3, 11);
	PrintArray();
	Insert(3, 12);
	PrintArray();

	//3. 데이터를 삭제
	UnInitArray();
}