[알고리즘 공부] 실전 알고리즘 3강-배열

바킹독님이 올려주신 [실전 알고리즘] 영상을 보면서 공부한것을 기록
모든 사진은 바킹독님의 블로그에서 가져왔습니다.
https://blog.encrypted.gg/

---

배열의 성질

1. 배열의 k번째 원소를 O(1)에 확인/변경 가능
2. 추가적으로 소모되는 메모리의 양=(overhead)가 거의 없음
3. cache hit rate가 높음
4. 메모리 상에 연속된 구간을 잡아야 해서 할당에 제약이 걸림

---

기능과 구현

임의의 위치의 원소를 확인하고 변경하는것은 O(1)
끝에 원소를 추가하거나 마지막 원소를 제거하는것은 O(1)

임의의 위치에 원소를 추가하는것은 O(n).. 임의의 위치 뒤에 원소들을 다 한칸식 뒤로 움직여야 하므로 O(n)이다.

임의의 위치에 있는 원소를 제거하는것도 O(n)

임의의 원소를 추가하는 insert함수와 임의의 위치에 있는 원소를 제거하는 erase함수

#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)
{
	for (int i = idx; i < len; ++i)
		arr[i] = arr[i + 1];
	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();
}

매개변수를 참조자로 보내면 원본의 값이 변경됨

배열 전체를 초기화하는 방법은 fill함수를 추천함

---

STL vector

vector는 배열과 동일한 기능을 수행하는 자료구조로 배열과 마찬가지로 원소가 메모리에 연속적으로 저장되어 있어서 O(1)에 각 원소에 접근할 수 있다. vector는 배열과 다르게 크기를 자유롭게 변경할 수 있는 장점이 있다.

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

int main(void) {
  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(); // {}
}

vector의 insert, erase는 O(n), push_back, pop_back은 끝에 원소를 추가하거나 빼는것이므로 O(1)이다.

for( auto e : v) // range-based for loop
	cout << e << ' ';
    
for(auto &e : v) // range-based for loop
	cout << e << ' ';

range-based for loop 방식을 사용할때 참조를 사용하면 원본인 v값이 변경된다.
이는 나중에 vector뿐만 아니라 list, map, set등에서도 사용하게 된다.

---

연습문제

코드

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

int num[101];

int func2(int arr[], int N)
{
	fill(num, num + 101, 0);
	for (int i = 0; i < N; ++i)
		num[arr[i]]++;

	for (int i = 1; i <= 50; ++i)
		if (num[50 - i] == num[50 + i] && num[50 - i] == 1)
			return 1;
	return 0;
    
    // 바킹독님의 코드
    /*for (int i = 0; i < N; ++i)
	{
		if (num[100 - arr[i]] == 1)
			return 1;
		num[arr[i]]++;
	}
	return 0;*/
}

int main(void) {
	int arr1[] = { 1,52,48 };
	int arr2[] = { 50,42 };
	int arr3[] = { 4,13,63,87 };
	printf("%d", func2(arr1, 3));
	printf("\n");
	printf("%d", func2(arr2, 2));
	printf("\n");
	printf("%d", func2(arr3, 4));
}