[C++/코테] 배열과 Vector

배열은 데이터를 자주 바꾸지 않고 그냥 쌓아두고 싶을 때 활용할 수 있다.

입력을 담아두기 위해 많이 사용.

배열의 성질

• $O(1)$에서 k번째 원소를 확인/변경 가능하다.
• 추가적으로 소모되는 메모리의 양(overhead)가 거의 없다.
• Cache hir rate가 높다.
• 메모리 상에서 연속한 구간을 잡아야 해서 할당에 제약이 걸린다.

배열의 연산

$O(1)$

• 임의의 위치에 있는 원소를 확인/변경
• 원소를 끝에 추가
• 마지막 원소를 제거

$O(N)$

• 임의의 위치에 원소를 추가 - 평균적으로 N/2개의 원소가 밀리기 때문
• 임의의 취이에 있는 원소를 제거

배열 사용팁

배열 전체를 특정 값으로 초기화하기

1. cstring 헤더에 있는 memset 함수를 활용하는 방식 (비추)
2. for문을 사용해서 하나하나 바꿔주는 것
3. algorithm 헤더의 fill 함수 사용

---

벡터

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

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

int main(void)
{
    vector<int> v1(3, 5);
    cout << v1.size() << '\n';
    v1.push_back(7);

    vector<int> v2(2);
    v2.insert(v2.begin() + 1, 3);

    vector<int> v3 = {1, 2, 3, 4};
    v3.erase(v3.begin() + 2); // {1, 2, 4}

    vector<int> v4;
    v4 = v3; // {1, 2, 4}. = 을 사용하면 deep copy가 발생
    cout << v4[0] << v4[1] << v4[2] << '\n';
    v4.pop_back(); // {1, 2}
    v4.clear();
}

$O(1)$

• push_back
• pop_back

$O(N)$

• insert
• erase
• push_front
• pop_front

 

vector에 있는 모든 원소를 순회하려고 할 때, range-based for loop를 이용할 수 있다.

vector<int> V1 = {1, 2, 3, 4, 5, 6};
// range-based for loop (since C++ 11)
for (int e : V1)	// V1의 복사본이 들어가서, 원본에는 영향 X
    cout << e << ' ';

기초적인 for문을 사용할 수도 있다.

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

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

* vector는 size를 unsigned int 형으로 반환한다.

 

연습문제

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

func2({1, 52, 48}, 3) = 1
func2({50, 42}, 2) = 0
func2({4, 14, 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) // if (occur[100 - arr[i]]) 로만 적어도 됨
            return 1;
        occur[arr[i]] = 1;
    }
    return 0;
}

 

나다어

• 값 자체를 찾아보려면 $O(N)$의 복잡도를 피할 수 없지만, 값을 배열의 인덱스로 사용하면 인덱스 검색에 $O(1)$의 복잡도로 문제를 해결할 수 있다.