[바킹독의 실전 알고리즘] 0x03강 - 배열

배열

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

성질

1. O(1)에 k번째 원소를 확인 / 변경 가능
   • 임의의 위치에 원소 추가 / 제거 O(N)
     • 추가하는 위치가 끝에 가까울수록 시간 ↓ => 평균적으로 N/2개 밀어야 함
2. 추가적으로 소모되는 메모리의 양(= overhead)가 거의 X
3. Cache hit rate ↑
   캐시 적중률(Cache hit rate) = 적중횟수/ 총 접근횟수, 컴퓨터의 성능 나타내는 척도
4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림

시간복잡도

• O(1)
  • 임의의 위치에 있는 원소 확인/ 변경
  • 원소 끝에 추가
  • 마지막 원소 제거
• O(N)
  • 임의의 위치에 원소 추가 / 임의의 위치의 원소 제거

void insert(int idx, int num, int arr[], int& len);

void erase(int idx, int arr[], int& len);

int main(void) {
	int arr[10] = {10, 50, 40, 30, 70, 20};
    	int len = 6;
    	insert(3, 60, arr, len); // 10 50 40 60 30 70 20
    	erase(4, arr, len) // 10 50 40 60 70 20
}

구현

#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];
}

void printArr(int arr[], int& len) {
	for(int i = 0; i < len; i++) cout << arr[i] << ' ';
    cout << "\n\n";
}

void insert_test() {

}

void erase_test() {

}

int main(void) {
	insert_test();
    erase_test();
}

사용팁

1. memset (비추천)
cstring 헤더에 있는 memset 함수
(+) 코드 길이 ↓
(-) 0이나 -1이 아닌 다른 값 -> 오동작
(-) 2차원 이상의 배열을 함수 인자로 넘겨 memset -> 잘못 들어감

2. for
코드 투박 But, 실수할 여지 X

3. fill (추천)
algorithm 헤더의 fill 함수
실수할 여지 X, 코드 길이 ↓

int a[21];
int b[21][21];

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

// 2. for
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;
        
// 3. fill
fill(a, a+21, 0);
for(int i = 0; i < 21; i++)
	fill(b[i], b[i]+21, 0);

---

STL vector

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

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

(1)
int e : v1 -> 복사된 값이 e에 들어감
=> for 문 내에서 e를 바꿔도 v1에는 영향 X
int& e : v1 -> 원본이 e에 들어감
=> for 문 내에서 e를 바꿔도 v1에는 영향 O (해당 원소 값 변경)

(3) 
vector의 size 메소드 -> unsigned int 반환
=> v1이 빈 vector일 때 v1.size() - 1 == unsigned int 0 - int 1
, unsigned int와 int 연산 -> unsigned int로 자동 형변환

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

// 1. range-based for loop (since C++11)
for(int e : v1)
	cout << e << ' ';

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

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

---

연습문제

주어진 길이 N의 int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을,
존재하지 않으면 0을 반환하는 함수 func2(int arr[], int N)을 작성

func2({1, 52, 48}, 3) = 1,
func2({50, 42}, 2) = 0,
func2({4, 13, 63, 87}, 4) = 1

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

나와 합이 100이 되는 원소를 매 순간마다 O(1)에 찾고 이 행위 N번 반복
=> 총 시간복잡도 O(N)

---