[바킹독]3. 배열

https://youtu.be/mBeyFsHqzHg?si=lx-RwTJVo-O_sroz

https://blog.encrypted.gg/927

[실전 알고리즘] 0x03강 - 배열

 

1. 정의와 성질
2. 기능과 구현
3. STL vector
4. 연습 문제 

 

1. 정의 

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

2. 성질

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

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

3) Cache hit rate가 높음

* Cache hit rate (캐시 적중률)

https://80000coding.oopy.io/e0a65449-6ef1-44cc-932b-7b7bff393948

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

 

3. 기능 

1) 임의의 위치에 있는 원소를 확인/변경 : O(1)

2) 원소를 끝에 추가 : O(1)

3) 마지막 원소를 제거 : O(1)

4) 임의의 위치에 원소를 추가 / 임의 위치의 원소 제거 : O(N)

 

4. 구현

1) 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++;
}

2) erase 

왼쪽부터 처리를 하면 추가적인 메모리를 쓰지 않고 구현가능

void erase(int idx, int arr[], int& len){
  len--;
  for(int i = idx; i < len; i++)
    arr[i] = arr[i+1];
}

 

5. 사용 팁 - 전체를 특정 값으로 초기화 

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

1) cstring 헤더 - 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) algorithm 헤더 - fill 함수 

-> 실수할 여지 x, 짧으니 제일 추천 

fill (a, a+21, 0);
for (int i = 0; i < 21; i++)
	fill(b[i], b[i]+21, 0);

 

 

6. STL vector

https://cplusplus.com/reference/vector/vector/

https://cplusplus.com/reference/vector/vector/

 

1) 메소드

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

- v.begin() + x

* iterator 

 

- 시간 복잡도 O(N) : insert(), erase()

- O(1) : push_back, pop_back (제일 끝에 원소를 추가/빼는 것이라) 

 

2) 모든 원소 순회

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

방법 1. range-based for loop : int e : vs ( = for문)

-> e에 v1 원소들이 하나씩 들어가는 for문 (C+11 이상) 

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

 

방법 2. 인덱스 하나씩 돌기 (기존 for문) 

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] << ' ';

size 메소드 반환값이 unsigned -> 3번처럼 구현하면 큰일남 

* unsigned int overflow 

 

7. 연습문제

1) BOJ 10808 알파벳 개수 

2) 강의 연습문제