[알고리즘 공부] 실전 알고리즘 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));
}