배열

김정민·2020년 12월 12일

배열은 메모리 상에 원소를 연속하게 배치한 자료구조이다. 원래 C++에서 사용하는 배열에서는 배열을 선언한 뒤에는 배열의 길이를 변경하는게 불가능하지만, 자료구조라는 관점에서 배열의 길이를 마음대로 늘리거나 줄일 수 있다고 생각해보자.

1. 배열의 성질

O(1)에 k번째 원소를 확인/변경 가능

배열은 그림과 같이 메모리 상에 원소를 연속하게 배치한 자료구조이기 때문에 k번째 원소의 위치를 바로 계산할 수 있다. 시작 주소에서 k칸 만큼만 오른쪽으로 이동하면 되기 때문이다.

추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음

Cache hit rate가 높음.
캐시 작동 원리 : https://parksb.github.io/article/29.html

메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림

2. 기능

임의의 위치에 있는 원소를 확인/변경 = O(1)

끝 부분에 원소 추가/끝 부분에 원소 제거 = O(1)

임의의 위치에 원소를 추가/제거 = O(N)

임의의 위치에 원소를 추가하거나 제거하는 과정은 O(N)이다. 추가할 때에는, 특정 위치에 원소를 추가하고 그 뒤에 위치한 원소들을 전부 한 칸씩 뒤로 밀어야 한다. 제거 역시 특정 위치에 있는 원소를 제거하고 나서 뒤에 있는 원소들을 전부 한 칸씩 앞으로 당겨와야 하기 때문이다.

그렇기 때문에 추가/제거 하려는 원소의 위치가 배열의 끝 부분에 가까울수록 시간이 줄어들고, 앞에 가까울 수록 시간은 늘어나지만 평균적으로 N/2개의 원소를 움직여야 하니 O(N)이라고 말 할 수 있다.

3. 구현

임의의 위치에 원소를 추가/제거하는 기능 구현

#include <bits/stdc++.h>
using namespace std;

void insert(int idx, int num, int arr[], int& len) {

	for (int i = len; i > idx; i--) {
		arr[i] = arr[i - 1];
	}
	arr[idx] = num;
	len++;
}

void erase(int idx, int arr[], int& len) {
	len--;
	for (int i = idx; i < len; i++) {
		arr[idx] = arr[idx + 1];
	}
}

void printArr(int arr[], int& len) {
	for (int i = 0; i < len; i++) cout << arr[i] << ' ';
	cout << "\n\n";
}

void insert_test() {
	cout << "***** insert_test *****\n";
	int arr[10] = { 10, 20, 30 };
	int len = 3;
	insert(3, 40, arr, len); // 10 20 30 40
	printArr(arr, len);
	insert(1, 50, arr, len); // 10 50 20 30 40
	printArr(arr, len);
	insert(0, 15, arr, len); // 15 10 50 20 30 40
	printArr(arr, len);
}

void erase_test() {
	cout << "***** erase_test *****\n";
	int arr[10] = { 10, 50, 40, 30, 70, 20 };
	int len = 6;
	erase(4, arr, len); // 10 50 40 30 20
	printArr(arr, len);
	erase(1, arr, len); // 10 40 30 20
	printArr(arr, len);
	erase(3, arr, len); // 10 40 30
	printArr(arr, len);
}

int main(void) {
	insert_test();
	erase_test();
}