[알고리즘 정리] 03 배열

배열의 성질

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

책장을 생각하자.
임의의 위치에 있는 원소를 확인, 변경, 원소를 끝에 추가, 마지막 원소 제거는 O(1)의 시간이 걸린다.

하지만 임의의 위치에 원소를 추가, 제거하는 것은 O(N)이다. 책을 다 밀어야 대기 때문.

구현 - 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[20];
int b[20][20];

//1. memset
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);

//2. fill

fill(a, a+20, 0);
fill(&b[0][0], &b[0][0] + 20 * 20, 10);

fill이 실수할 일도 없고 편하다. fill은 algorithm 헤더에 있다.

vector 원소 순회

vector에서 모든 원소를 순회할 때, range-based for loop을 사용하는 것이 편하다.

vector<int> v1 = {1, 2, 3, 4, 5, 6};

for(int e : v1) cout << e << ' ';

여기서 size()를 써서 한다면,

//2.
for(int i = 0 ; i < v1.size(); i++) cout << v1[i] << ' ';

//3.
for(int i = 0 ; i < v1.size()-1;i++) cout << v1[i] << ' ';

2번같이 쓰는 경우 올바르게 실행이 되지만, 3번같이 쓰면 안 된다.
vector의 size()는 시스템에 따라 unsigned int 혹은 unsigned long long을 반환하므로, 이상하게 될 수 있다.