[실전 알고리즘] 0x03강

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

2022. 1. 21. 16:55ㆍAlgorithm/1강

1. 정의와 성질

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

배열의 성질

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

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

3. Cache hit rate가 높음

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

2. 기능과 구현

기능

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

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

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

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

구현 - insert, erase 함수

수정 전 코드

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

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

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

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

수정 후 코드

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

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

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

전체를 특정 값으로 초기화시키는 3가지 방법

1. cstring 헤더에 있는 memset 함수 활용

0이나 -1이 아닌 다른 값을 넣으면 오동작하고 2차원 이상의 배열을 함수의 인자로 넘겨 memset을 하면 잘못 들어갈 때가 있다.

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

memset(a, 0, sizeof a);
memset(b, 0, sizeof b);

2. for문을 돌면서 값을 일일이 다 바꾸는 방식

코드가 투박해도 실수할 여지가 없다.

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

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. alorithm 헤더의 fill 함수 이용

실수할 여지도 없고 코드도 짧다.

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

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

3. STL vector

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

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

insert, erase - O(N)

push_back, pop_back - O(1)

vector에서 =를 사용하면 deep copy가 발생한다. deep copy는 그 내용을 가진 객체를 따로 또 만들어 서로 영향을 주지 않는 copy이고 shallow copy는 같은 객체를 참조하기 때문에 값을 바꾸면 서로 영향을 준다.

vector에 있는 원소 순회 방법

1. range-based for loop

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

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

위의 코드처럼 range-based for loop를 돌리면 복사된 값이 e에 들어가고 아래 코드처럼 참조자를 붙여 돌리면 원본이 e에 들어가게 된다.

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

for(int& e : v1){
  cout << e << ' ';
}

이 기능은 vector 뿐 아니라 list, map, set 등에서도 모두 사용할 수 있어 유용하지만 C++11부터 추가된 기능이기 때문에 코딩테스트가 C++11을 지원하지 않으면 사용할 수 없다.

2. for문

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

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

위의 코드처럼 무난하게 for문으로 인덱스를 하나씩 다 돌아도 된다. 하지만 아래 코드처럼 쓰면 잘못될 수 있다. 기본적으로 vector의 size 메소드는 시스템에 따라 unsigned int 혹은 unsigned long long을 반환한다. 그렇기 때문에 32비트 컴퓨터 기준 아래의 코드 같이 쓰면 v1이 빈 vector일 때 v1.size() - 1이 unsigned int 0에서 int 1을 빼는 식이 되고, unsigned int와 int를 연산하면 unsigned int로 자동 형변환이 발생하기 때문에 (unsigned int)0 - (int)1은 -1이 아니라 4294967295이 되어버리는 불상사가 발생한다. 4294967295이라는 이상한 값은 unsigned int overflow로 인해 생기게 된 값이다. 결국 런타임 에러를 마주하게 되니까 주의해서 사용해야 한다.

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

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

아래는 vector에 대한 레퍼런스 사이트.

http://www.cplusplus.com/reference/vector/vector/

vector - C++ Reference

difference_typea signed integral type, identical to: iterator_traits ::difference_type usually the same as ptrdiff_t

www.cplusplus.com

4. 연습 문제

BOJ 10808번 : 알파벳 개수

10808번: 알파벳 개수

단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다.

www.acmicpc.net

아래 코드는 투박하고 단순한 코드지만 통과한 코드이다.

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int alpha[26] = {
        0,
    };
    string s;
    cin >> s;
    for (char c : s)
    {
        switch (c)
        {
        case 'a':
            alpha[0]++;
            break;
        case 'b':
            alpha[1]++;
            break;
        case 'c':
            alpha[2]++;
            break;
        case 'd':
            alpha[3]++;
            break;
        case 'e':
            alpha[4]++;
            break;
        case 'f':
            alpha[5]++;
            break;
        case 'g':
            alpha[6]++;
            break;
        case 'h':
            alpha[7]++;
            break;
        case 'i':
            alpha[8]++;
            break;
        case 'j':
            alpha[9]++;
            break;
        case 'k':
            alpha[10]++;
            break;
        case 'l':
            alpha[11]++;
            break;
        case 'm':
            alpha[12]++;
            break;
        case 'n':
            alpha[13]++;
            break;
        case 'o':
            alpha[14]++;
            break;
        case 'p':
            alpha[15]++;
            break;
        case 'q':
            alpha[16]++;
            break;
        case 'r':
            alpha[17]++;
            break;
        case 's':
            alpha[18]++;
            break;
        case 't':
            alpha[19]++;
            break;
        case 'u':
            alpha[20]++;
            break;
        case 'v':
            alpha[21]++;
            break;
        case 'w':
            alpha[22]++;
            break;
        case 'x':
            alpha[23]++;
            break;
        case 'y':
            alpha[24]++;
            break;
        case 'z':
            alpha[25]++;
            break;
        default:
            break;
        }
    }

    for (int i = 0; i < 26; i++)
    {
        cout << alpha[i] << " ";
    }
    return 0;
}

위의 코드를 더 정리하면 아래 코드와 같다. 아스키코드를 이용해서 switch 문의 긴 코드를 freq[c-'a']++; 한 줄로 바꿀 수 있다.

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


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int freq[26] = {0,};
    string s;
    cin >> s;
    for (auto c:s){
        freq[c-'a']++;
    }
    for (int i = 0; i < 26; i++){
        cout << freq[i] << " ";
    }

    return 0;
}

0X01강의 연습문제 문제 2

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

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

이전의 0X01강에서는 O(N^2)의 코드를 짰었지만 이번에는 O(N)의 시간복잡도를 갖는 코드를 짜봤다.

참고자료