바킹독님의 실전알고리즘배우기 3강듣고 요약

배열의 성질

배열의 공간 지역성 때문에 cache hit rate가 높다.

insert와 erase 함수의 구현 &

#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(){
  cout << "***** insert_test *****\n";
  int arr[10] = {10, 20, 30};
  int len = 3;
  insert(3, 40, arr, len); // 10 20 30 40
  printArr(arr, len);
  insert(1, 50, arr, len); // 10 50 20 30 40
  printArr(arr, len);
  insert(0, 15, arr, len); // 15 10 50 20 30 40
  printArr(arr, len);
}

void erase_test(){
  cout << "***** erase_test *****\n";
  int arr[10] = {10, 50, 40, 30, 70, 20};
  int len = 6;
  erase(4, arr, len); // 10 50 40 30 20
  printArr(arr, len);
  erase(1, arr, len); // 10 40 30 20
  printArr(arr, len);
  erase(3, arr, len); // 10 40 30
  printArr(arr, len);
}

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

배열의 멤버를 모두 특정 값으로 초기화시키기

2번 for문을 직접 돌리거나,
3번 fill 함수를 이용하면 좋다.
(1번은 실수할 여지가 있다.)

vector 사용하기

vector에서는 iterator(v.begin())를 이용하고,
v.push_back(), v.pop_back() -> O(1)
v.insert(), v.erase() -> O(N) 등 함수롤 이용하여 데이터를 수정한다.

range-based for loop(C++11 이상) 사용하면 편하다.

3번처럼 vector를 쓰면 무한루프에 빠지게 된다.
-> vector는 unsigned int를 반환하기 때문에 0보다 작은 값이 없다.
따라서 0 - 1 = 4294967295(2^32-1)가 된다.
range-based for loop를 쓰면 for문을 돌기 편리하다.

연습문제 1

BOJ 10808번

연습문제 2

내 풀이

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

이렇게 하면 arr[i]가 0일 때 freq[-1]에 접근하기 때문에 runtime error가 발생할 수 있다고 바킹독님께서 지적해주셨다 (오류를 지적해주셔서 감사합니당ㅎㅎ 앞으로도 누구든지 블로그 글에 대한 오류가 있으면 지적해주시면 감사하겠습니다!)
그래서 실제로 돌려봤는데 띠용하는 일이 벌어져서 그것에 대한 자세한 사항은 이 글에 적어두었다.
또한 말씀해주신 대로 고친 풀이는 아래와 같다.

고친 풀이

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

baaaaaaaarkingDog님의 풀이

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

array,vector,range-based for loop

J-Shine