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

배열(Array)의 성질

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

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

3. Cache hit rate가 높음

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

insert 함수를 구현할때 왼쪽에서 오른쪽으로 값을 옮기는 알고리즘을 구현했다.

1. n-1번째 인덱스 값이 n번째 인덱스로 이동

2. 배열의 길이 1 늘리기

#include <bits/stdc++.h>

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 함수를 구현할때 오른쪽에서 왼쪽으로 값을 옮기는 알고리즘을 구현했다.

1. n+1번째 인덱스 값이 n번째 인덱스로 이동

2. 배열의 길이 1 줄이기

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

출력 부분

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

벡터(Vector)의 성질

1. 배열과 거의 동일한 기능을 수행하는 자료구조

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

3. 배열과 달리 크기를 자유자재로 늘이거나 줄일 수 있다.

연습문제 1번 - 백준 10808번

목표 : 입력받은 단어에 알파벳이 몇 개가 포함되어 있는지 구하는 프로그램

알고리즘

각 알파벳마다 그릇을 만들어서 입력받은 문자열을 훑으면서 등장횟수를 각 알파벳 그릇에 저장하기

#include <bits/stdc++.h>

int freq[26];
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);

  string s;
  cin >> s;

  for(char c:s)
    freq[c-'a']++;
  for(int i=0; i<26; i++)
    cout << freq[i] << ' ';
}

연습문제 2번

목표 : 배열의 원소 중 두 원소의 합이 100인 배열을 판단해라. 100이 있다면 1 없으면 0, 시간복잡도 O(N)

내가 생각했던 알고리즘

각 원소를 훑으면서 100에서 각 원소를 뺀 값이 배열에 있으면 1을 반환하는 알고리즘을 생각했는데 이것도 시간복잡도를 계산해보니 O(N^2)인 것 같다.

시간복잡도 O(N) 알고리즘

1부터 99까지 배열을 만들고 배열을 차례로 훑으면서 각 원소와 더해 100이 되는 수의 인덱스 값이 1이면 1을 반환하고 아니라면 원소의 인덱스 값을 1로 만드는 방법을 계획했다.

아래의 사진처럼 1이 원소이면 99번째 인덱스 값이 0이기 때문에 1번째 인덱스 값을 1로 바꿔줬다.

다음 원소로 23이고 77번째 인덱스 값이 0이기 때문에 23번째 인덱스 값을 1로 바꿔줬다. 이러한 과정을 배열의 끝까지 반복한다.

이와 같은 방법으로 진행하면 시간복잡도를 O(N)만큼만 사용하여 해결할 수 있게 된다.

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

느낀점 : 배열을 잘 활용한다면 시간복잡도를 줄일 수 있다는 것을 깨달았다.