C++ 벡터(vector) 사용법 (BOJ 2822/5635/14769)

vector 컨테이너에 대하여

C++의 표준 라이브러리에 내장된 컨테이너의 일종이다. 들어오는 값의 개수에 따라 유동적으로 메모리를 할당하며, 미리 크기를 정해둘 수도 있다. 그래서 사용하기에 편리하지만, 배열에 비해 처리 속도는 느린 편이라고 한다.

• vector<자료형> v; → 해당 자료형의 값을 담을 수 있는 크기가 유동적인 벡터 v를 선언한다.
• vector<자료형> v[n]; → 해당 자료형의 값을 담을 수 있는 크기가 n인 벡터 v를 선언한다. (n은 정수)

• v.push_back(a) → 요소 a를 벡터 v의 맨 뒤에 삽입한다.

• v.pop_back() → 벡터 v의 맨 뒤에 있는 요소를 제거한다.

• v.begin() → 벡터 v의 맨 앞에 있는 요소

• v.end() → 벡터 v의 맨 뒤에 있는 요소의 바로 뒤

• sort(v.begin(), v.end()); → 벡터 v를 오름차순으로 정렬한다.

알고리즘 문제를 풀다 보면 pair 컨테이너와 함께 쓰이는 경우가 종종 있다.

• vector <pair<자료형1, 자료형2>> v; → 자료형1과 자료형2에 해당하는 값을 담을 수 있는 페어로 구성된 크기가 유동적인 벡터 v를 선언한다.

• v.push_back(pair<자료형1, 자료형2>(a, b)); → 자료형1에 해당하는 값 a와 자료형2에 대항하는 값 b를 담은 페어를 벡터 v의 맨 뒤에 삽입한다.

• v.pop_back(); → 벡터 v의 맨 뒤에 있는 요소(페어)를 제거한다.

• v.clear(); → 벡터 내의 모든 요소들을 제거한다.

• v[i].first → 벡터의 i번째 페어에 들어있는 요소들 중 앞에 있는 요소를 참조한다.

• v[i].second → 벡터의 i번째 페어에 들어있는 요소들 중 뒤에 있는 요소를 참조한다.

• sort(v.begin(), v.end()); → 페어로 구성된 경우, 페어의 앞에 있는 요소를 기준으로 벡터 v를 오름차순으로 정렬한다.

다음은 BOJ의 몇몇 문제들을 벡터와 페어를 이용한 풀이들이다.

boj_2822 (2022. 11. 29. 풀이)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector <pair<int, int>> v;
vector <pair<int, int>> v2;

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

    int n, sum = 0;
    for (int i=0; i<8; i++) {
        cin >> n;
        v.push_back(pair<int, int>(n, i+1));
    }
    sort(v.begin(), v.end(), greater<>());
    for (int i=0; i<5; i++) {
        sum += v[i].first;
        v2.push_back(pair<int, int>(v[i].second, v[i].first));
    }
    cout << sum << "\n";
    sort(v2.begin(), v2.end());
    for (int i=0; i<5; i++) {
        cout << v2[i].first << " ";
    }
}

boj_5635 (2022. 12. 1. 풀이)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector <pair <pair<string, int>, pair<int, int>> > v;
string s;

int cmp(pair <pair<string, int>, pair<int, int>> a, pair <pair<string, int>, pair<int, int>> b) {
    if (a.second.second != b.second.second)
    return a.second.second > b.second.second;
    else {
        if (a.second.first != b.second.first)
        return a.second.first > b.second.first;
        else return a.first.second > b.first.second;
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, d, m, y;
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> s >> d >> m >> y;
        v.push_back(pair <pair<string, int>, pair<int, int>>(pair<string, int>(s, d), pair<int, int>(m, y)));
    }
    sort(v.begin(), v.end(), cmp);
    cout << v[0].first.first << "\n";
    cout << v[n-1].first.first << "\n";
}

boj_14769 (2022. 11. 28. 풀이)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

string a, b;
vector <pair<int, string>> v;

int main(void) {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, k;
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> a >> b;
        if (a[0] >= 48 && a[0] <= 57) {
            k = stoi(a);
            v.push_back(pair<int, string>(k/2,b));
        }
        else {
            k = stoi(b);
            v.push_back(pair<int, string>(k,a));
        }
    }
    sort(v.begin(), v.end());
    for (int i=0; i<n; i++) {
        cout << v[i].second << "\n";
    }

}