[ 알고리즘 ] 배열 , STL vector

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

 

특징

- k 번째 원소를 확인, 변경가능

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

-Cache hit rate가 높음

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

 

기능

- 배열 추가, 삭제, ghkrdls O(1)

- 임의의 위치에 원소 추가, 삭제 O(N)

 

// 배열 임의의 위치에 추가, 삭제하는 코드

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

void insert(int idx, int num, int arr[], int& len) {
	if (len != idx) {
		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-1; 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();
}

 

전체를 특정값으로 초기화 시키는 방법

1) cstring 헤더 memset

실수여지 큼

2) for문으로 하나하나 바꾸기

조잡하지만 실수여지 없음

3) algorithm헤더 fill 함수

강추

 

 

SLT vector

//STL 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}; 뒤에 넣기 O(N)

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

 

/*
문제2
주어진 길이 N의 int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을, 존재하지 않으면 0을 반환하는 함수 func2(int arr[],intN)을 작성하라.
arr의 각 수는 0이상 100이하이고 N은 1000이하이다.
*/

// 시간복잡도 O(N) 으로 짜는 방법

void func2(int arr[], int N) {

	int occur[101] = {};
	for (int i = 0; i < N; i++) {
		if (occur[100 - arr[i]] ) {
			cout << 1;
			return;
		}
		occur[arr[i]] = 1;

	}

}

 

 

이전에는 이중 for문을 이용했기에 시간복잡도가 O(N^2)이 되었다.

 

하지만 배열을 이용하면 O(N)으로 코드를 짤 수 있었다.

0부터 100까지를 담당하는 101칸 짜리 int 배열을 만들고

입력된 배열을 하나 씩 읽으며 더해서 100이 되는 수가

배열 안에 있었다는 확인하는 알고리즘이다.

 

더 효율적으로 짤 수 있다고 했을 때, 너무 생각이 안나서 강의를 봤는데,

 앞으로는 조금더 고민 해봐야 겠다.