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

 

이 게시글은 바킹독님의 강의를 공부하고 개인적으로 정리한 글입니다.

blog.encrypted.gg/927?category=773649

[실전 알고리즘] 0x03강 - 배열

 

0x03강 - 배열

 

1. 정의와 성질

배열이란 메모리 상에 원소를 연속하게 배치한 자료구조입니다.

• O(1)에 k번째 원소를 확인/변경 가능합니다. => 시작 주소에서 k칸만큼 오른쪽 가면 되기 때문입니다.
• 추가적으로 소모되는 메모리의 양(overhead)이 거의 없습니다.
• 메모리 상에 데이터들이 연속하게 저장되어 있기 때문에 Cache hit rate가 높습니다.
• 데이터 저장을 위해 메모리 상에 연속한 구간을 잡아야 하기 때문에 할당에 제약이 있습니다.

 

2. 기능과 구현

• 임의의 위치에 있는 원소를 확인/변경 => O(1)
• 원소를 끝에 추가 => O(1)
• 마지막 원소를 제거 => O(1)
• 임의의 위치에 원소를 추가/제거 => O(N) (뒤의 원소들을 전부 한 칸씩 뒤로 밀거나 앞으로 당겨야 합니다.)

임의의 위치에 원소를 추가/제거하는 함수 insert와 erase를 구현합니다.

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 += 1;
}

• 원하는 인덱스에(임의의 위치에) 원소 num을 추가하는 insert()입니다.
• 임의의 위치에 있는 원소부터 배열의 끝에 있는 원소를 끝에서부터 뒤로 한 칸씩 밀고 원하는 위치에 원소를 추가한 후, 배열의 길이를 1 증가시킵니다. (배열의 길이인 len은 참조자로 변수 값 자체를 받아 값을 변경시킵니다.)

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

• 원하는 인덱스에(임의의 위치에) 저장된 원소를 제거하는 erase()입니다.
• 임의의 위치에 뒤에 있는 원소부터 배열의 끝에 있는 원소를 앞에서부터 앞으로 한 칸씩 당기고, 배열의 길이를 1 감소시킵니다.

C++에서의 배열 전체를 특정값으로 초기화하는 방법들을 살펴봅니다.

int a[21];
int b[21][21];

// 1. memset
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);

// 2. 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;
        
// 3. fill
fill(a, a + 21, 0);
for(int i = 0 ; i < 21 ; i++)
	fill(b[i], b[i] + 21, 0);

• memset()은 #include<cstring>로 사용합니다. 하지만 0 또는 -1 이외의 값을 넣거나 1, 2차원 이상의 배열을 함수의 인자로 넘기는 경우 오작동할 가능성이 있으니 웬만하면 사용하지 않습니다.
• fill()은 #include<algorithm>로 사용합니다. 쉽고 실수할 여지없이 사용하기 좋습니다.

 

3. STL vector

vector는 배열과 거의 동일한 기능을 수행하는 자료구조로, 배열과 마찬가지로 원소가 메모리에 연속하게 저장되어있어 O(1)에 인덱스로 각 원소에 접근할 수 있습니다. 단 배열과 다르게 크기를 자유자재로 늘이거나 줄이는 것이 가능합니다.

• C++ vector 레퍼런스 사이트를 통해 vector의 함수와 사용법을 확인할 수 있습니다.

vector<int> v1(3, 5);	//{5,5,5}
cout << v1.size() << "\n";	//3
v1.push_back(7);		//{5,5,5,7}

vector<int> v2(2);		//{0, 0}
v2.insert(v2.begin()+1, 3);	//{0,3,0}

vector<int> v3 = { 1,2,3,4 };	//{1,2,3,4}
v3.erase(v3.begin() + 2);	//{1,2,4}

vector<int> v4;			//{}
v4 = v3;				//{1,2,4}
cout << v4[0] << v4[1] << v4[2] << "\n";
v4.pop_back();			//{1,2}
v4.clear();

• 이전 강의에서 작성했듯이, #include<vector>를 통해 사용할 수 있습니다.
• vector<type> vector_name;으로 비어있는 vector를 선언할 수 있고 위 예와 같은 방법으로 크기가 정해져 있거나 원소들이 초기화된 vector를 선언할 수 있습니다.
• 배열에서 구현했던 insert()와 erase()가 이미 구현되어 있습니다. 인자로 v.begin()+x와 같이 C++ iterator를 사용합니다. insert()와 erase()는 배열에서 구현한 것과 비슷하게 시간복잡도가 O(N)입니다.
• push_back()과 pop_back()은 제일 끝에 원소를 추가/삭제하는 함수로 시간복잡도가 O(1)입니다.
• v4 = v3;와 같이 =를 사용하면 deep copy가 발생합니다. 복사된 v4의 원소 값을 변경하더라도 기존 객체(v3)에는 영향을 주지 않습니다.

vector의 모든 원소를 순회하는 방법들을 살펴봅니다.

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

//1. range-based for loop (since C++11)
for (int e : v5)
	cout << e << ' ';

//2. not bad
for (int i = 0; i < v5.size() ; i++)
	cout << v5[i] << " ";

//3. don't do it
for (int i = 0; i <= v5.size()-1; i++)
	cout << v5[i] << ' ';

 

• range-based for loop를 이용하면 위와 같이 int e : v5 라고 했을 때 e에 v5의 원소들이 하나씩 들어가는 for문이 됩니다. int& e : v5를 사용하면 v5의 원소 원본이 e에 들어가 for문 내에서 e를 변경시키면 v5의 원본 원소 값이 변경됩니다. 이 기능은 vector뿐 아니라 list, map, set 등에서도 사용 가능하지만 C++11 이후부터 사용할 수 있습니다.
• vector의 size() 함수를 사용하여 for문으로 인덱스를 돌아 순회할 수 있습니다. 단 size()는 unsigned int를 반환하므로, vector가 비어있을 때 size() - 1는 unsigned int overflow를 일으킬 수 있습니다. 

배열은 데이터를 자주 바꾸지 않고 단순히 쌓아만 두고 싶을 때 효율적으로 활용할 수 있습니다. 대부분의 알고리즘 문제에서 입력값을 일단 저장해 놓고 시작하므로 배열을 많이 사용합니다.

이 외에도 인덱스에 해당하는 원소를 빠르게 접근하는 목적으로 배열을 사용할 때 효율적입니다. 

 

아래는 배열 알고리즘 문제를 풀이한 링크입니다.

- boj 방 번호

eunsolsblog.tistory.com/entry/C-%EB%B0%B1%EC%A4%80-1475%EB%B2%88-%EB%B0%A9-%EB%B2%88%ED%98%B8?category=972492

- boj 두 수의 합

eunsolsblog.tistory.com/entry/C-%EB%B0%B1%EC%A4%80-3273%EB%B2%88-%EB%91%90-%EC%88%98%EC%9D%98-%ED%95%A9