[Algorithm] 배열

참고자료
바킹독의 실전 알고리즘 https://blog.encrypted.gg/category/%EA%B0%95%EC%A2%8C/%EC%8B%A4%EC%A0%84%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98?page=1

배열

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

배열의 성질

1. O(1) 에 k번째 원소를 확인/변경 가능

2. 추가적으로 소모되는 메모리의 양이 거의 없음

3. Cache hit rate 가 높음 (메모리 상에 데이터들이 붙어있기 때문에!)

   📍 Cache란?
   대부분 프로그램은 한번 사용한 데이터를 다시 사용할 가능성이 높고, 그 주변의 데이터도 곧 사용할 가능성이 높은 데이터 지역성을 가지고 있다. 데이터 지역성을 활용하여 메인 메오리에 있는 데이터를 캐시 메모리에 불러와 두고, CPU가 필요한 데이터를 캐시에서 먼저 찾도록 하면 시스템 성능을 향상시킬 수 있다.
   📍 Cache hit ratio
   cache hit ratio : 적중률 = (캐시히트횟수)/(전체 참조횟수)
   cache hit : 참조하려는 데이터가 캐시에 존재할때 캐시 히트
   cache miss : 참조하려는 데이터가 캐시에 존재하지 않을때 캐시 미스

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

배열의 연산

1. 임의의 위치에 있는 원소 확인하고 변경 = O(1)
2. 임의의 원소를 끝에 추가 = O(1)
3. 마지막 원소를 제거 = O(1)

---

4. 임의의 위치에 원소 추가 = O(N)
   중간에 원소를 추가한다면 그 뒤의 원소들을 모두 한 칸씩 밀어야한다. 추가하는 위치가 끝에 가까울 수록 시간은 줄어들고, 반대는 늘어날 테지만 평균적으로는 N/2개이므로, O(N)
5. 임의의 위치에 있는 원소 제거 = O(N)
   중간에 원소를 제거한다면, 그 뒤의 모든 원소를 한 칸씩 앞으로 땡겨와야한다.

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