[바킹독 실전 알고리즘 0x03] 배열

배열

정의: 메모리 상에 원소를 연속하게 배치한 자료구조. 

성질: 

• 1. O(1)의 시간복잡도만을 사용해 k번째 원소를 확인/변경이 가능하다. 메모리 상에 연속하게 배치되어있기 때문에 가능하다.
• 2. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없다.
• 3. cache hit rate가 높다.
• 4. 메모리 상에 연속한 구간을 잡아야해서 할당에 제약이 걸린다.

배열의 임의의 위치에 원소를 추가하는 데 걸리는 시간복잡도는 O(N)이다. 하나의 원소를 추가하기 위해 뒤에 남은 원소들을 모두 한 칸씩 밀어야하기 때문이다. 마찬가지로 임의의 원소를 제거하는 연산도 O(N)의 시간복잡도를 요구한다.

배열에 원소를 추가하거나 삭제하는 것은 다음과 같이 구현할 수 있다:

//idx번째 위치에 num을 넣는 함수. 원래 idx의 위치에 있던 원소와 그 뒤의 원소들은 자연스럽게 한 칸씩 뒤로 밀린다.
void insert(int idx, int num, int arr[], int& len);  //len은 참조자로 전달했으므로 insert함수에서 변경된 len값이 원본에도 적용된다.

void erase(int idx, int arr[], int& len);

int main(void) {
    int arr[10] = {10, 50, 40, 30, 70, 20};
    int len = 6;
    insert(3, 60, arr, len); //10 50 40 60 30 70 20
    erase(4, arr, len); //10 50 40 60 70 20
}

 

배열의 특정 자리에 새로운 원소를 추가하는 insert함수와 배열의 특정 원소를 삭제하는 erase함수를 구현하면 다음과 같다:

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

void insert(int idx, int num, int arr[], int& len) {
	for (int i = len+1;i >= idx;i--) {
		arr[i+1] = arr[i];
	}
	arr[idx] = num;
	len++; //원소를 추가한 후 len값을 하나 늘려준다.
}

void erase(int idx, int arr[], int& len) {
	for (int i = idx;i < len;i++) {
		arr[i] = arr[i + 1];
	}
	len--; //원소를 지운 후 len값을 하나 줄인다.
}

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();
}

C++에서 배열 전체를 특정 값으로 초기화하는 방법

• 1. for문을 돌면서 값을 하나씩 입력한다.
• 2. fill함수를 사용한다.

//1.for문
for(int i=0;i<21;i++)
	a[i]=0;
for(int i=0;i<21;i++)
	for(int j=0;j<21;j++)
    	b[i][j]=0;
        
//2.fill
fill(a,a+21,0);
for(int i=0; i<21;i++)
	fill(b[i], b[i]+21,0);

 

STL vector

vector는 배열과 거의 동일한 기능을 수행하는 자료구조로, 배열과 마찬가지로 O(1)의 시간복잡도를 가지고 원소에 접근하거나 원소를 변경할 수 있다. 하지만 vector는 배열과 달리 크기를 자유롭게 늘이거나 줄일 수 있다는 장점을 가진다. 

vector 설명 문서: https://cplusplus.com/reference/vector/vector/

https://cplusplus.com/reference/vector/vector/

 

vector에 =을 사용하면 deep copy가 발생한다. 다음과 같은 코드를 실행했다고 가정하자:

v3 = {1,2,4};
v4 = v3;

이후 v4의 값을 변경해도 v3에는 영향을 주지 않는다.

 

vector의 모든 원소를 순회하는 두 가지 방법

• 1. range-based for loop(since C++11)
• 2. for문

vector<int> v1 = {1,2,3,4,5,6};

//1.range-based for loop
for(int e: v1)  //e에 v1원소들이 하나씩 들어가는 for문. int& e: v1으로 작성하면 for문 내에서 e를 바꾸면 원본인 v1의 값도 이에 따라 변경된다.
	cout << e << ' ';
    
//2.for문
for(int i=0; i<v1.size(); i++)
	cout << v1[i] << ' ';
    
//절대 이렇게 하면 안됨!!!
for(int i=0; i <= v1.size()-1;i++)  //기본적으로 벡터의 size메소드는 unsigned int를 반환하므로 이렇게 쓰면 빈 벡터일 때 unsigned int overflow가 발생한다.
	cout << v1[i] << ' ';