<aside> ❓ 배열

</aside>

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

배열의 성질)

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

Cache hit rate(캐시 메모리 적중률) : “적중률 = 적중 횟수 / 총 접근 횟수”로 캐시 기억장치가 있는 컴퓨터의 성능을 나타내는 척도 적중률이 0.95~0.99일 때 우수한다고 함

배열에서 제공된 연산

• 임의의 위치에 있는 원소를 확인/변경
  • 시간 복잡도 : O(1)
• 윈소 추가 연산
  • 끝자리에 원소 증가시키고 넣음
  • 시간 복잡도 : O(1)
• 마지막 원소 제거
  • 길이를 1줄임 (시간복잡도) : O(1)
• 임의의 위치에 있는 원소 제거
  • 시간복잡도 : O(N)
  • 임의의 원소를 제거하면 그 뒤에 있는 원소들을 한 칸 씩 당겨와야 메모리 상에서 연속되게 배치 할 수 있기 때문이다.

<aside> ❓ 배열의 구현

</aside>

/* insert 구현 */
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++;
}
/* erase 구현 */
void erase(int idx, int arr[], int& len){
	len--;
	for(int i = idx; i < len; i++)
		arr[i] = arr[i+1]
}

/* 배열 초기화 */
int a[21];
int b[21][21];
/* fill 함수 사용 */
fill(a, a+21, 0);
for(int i = 0; i <21; i++)
	fill(b[i], b[i] + 21, 0); 

/* 반복문 사용 */
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;

/* STL vector 활용 */
#include <bits/stdc++.h>

using namespace std;

int main(void){
	vector<int> v1(3, 5); // {5, 5, 5}
	cout << v1.size() << '\\n'; 
	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'; // {124}
	v4.pop_back(); // {1, 2}
	v4.clear(); // {}
}

• push_back, pop_back : 시간 복잡도 O(1)
• push_front, pop_front : 시간 복잡도 O(N)
• int& v : 원본 v의 값 불러옴, int v : 복사된 v의 값 불러옴

범위 기반 for 문

• 시작과 끝점을 알려주지 않아도 알아서 처음부터 끝까지 순회를 해주는 반복문