유용한 C++ 라이브러리

C++을 쓰는 이유에서 언급했다시피 C++에는 유용한 라이브러리/함수가 많습니다.

대회 중 인터넷 검색도 허용되는 만큼 많은 도움이 되었으면 좋겠습니다.

 

팁: #include "bits/stdc++.h" 로 알고리즘 문제풀이에 쓰는 모든 헤더파일을 불러올 수 있습니다

Visual Studio에서 기본 제공되지는 않는데 대회 당일에 시간이 남으면 세팅해둘게요

 

목차

• 배열/벡터 정렬(sort)
• 작은 거, 큰 거(min, max)
• 배열/벡터에서 가장 작은 거, 가장 큰 거(min_element, max_element)
• 벡터에서 중복 원소 제거
• 원하는 원소를 빠르게 넣고 빼고 싶을 때(set)
• 일대일 대응시키고 싶을 때(map)

 

배열/벡터 정렬(sort)

헤더파일: <algorithm>

#include <algorithm>
#include <vector>
using namespace std;
 
bool cmp(int, int);
 
int arr[100005];
vector<long long> v;
int main() {
 
    // 필수 ---------------------------------------------------
 
    sort(arr, arr + 1000); // arr[0] ~ arr[999] 오름차순 정렬
    sort(v.begin(), v.end()); // v의 모든 원소 오름차순 정렬
 
    // --------------------------------------------------------
    // 알면 좋음 -----------------------------------------------
 
    sort(arr, arr + 1000, greater<int>()); // arr[0] ~ arr[999] 내림차순 정렬
    sort(arr + 10, arr + 10001); // arr[10] ~ arr[10000] 오름차순 정렬
    sort(v.begin(), v.end(), greater<long long>()); // v의 모든 원소 내림차순 정렬
 
    // --------------------------------------------------------
    // 알면 언젠가 씀 ------------------------------------------
 
    sort(arr, arr + 1000, cmp); // arr[0] ~ arr[999] 10으로 나눈 나머지가 작은 순서대로 정렬(비교 함수 직접 정의)
    sort(arr, arr + 1000, [](int a, int b) {
        return a % 10 > b % 10;
    }); // arr[0] ~ arr[999] 10으로 나눈 나머지가 큰 순서대로 정렬(비교 함수로 익명 함수 넣음)
}
 
bool cmp(int a, int b) {
    return a % 10 < b % 10;
}

 

작은 거, 큰 거(min, max)

헤더파일: <algorithm>

min(a, b) - a,b 중 작은 값 반환

max(a, b) - a,b 중 큰 값 반환

min({ a, b, c, d }) - 중괄호 안의 값 중 가장 작은 값 반환(몇 개든 쓸 수 있음)

max({ a, b, c, d }) - 중괄호 안의 값 중 가장 큰 값 반환(몇 개든 쓸 수 있음)

 

if문 쓰면 되지/삼항연산자 쓰면 되지라고 생각할 수도 있지만 익숙해지면 직관적이고 좋습니다

 

배열/벡터에서 가장 작은 거, 가장 큰 거

헤더파일: <algorithm>

min_element(arr, arr + n): 배열 arr[0], arr[1], ... , arr[n - 1] 중 가장 작은 값을 가리키는 포인터 반환

max_element(arr, arr + n): arr[0], arr[1], ... , arr[n - 1] 중 가장 큰 값을 가리키는 포인터 반환

min_element(v.begin(), v.end()): 벡터 v에서 가장 작은 값을 가리키는 포인터 비슷한 이터레이터 반환

max_element(v.begin(), v.end()): 벡터 v에서 가장 큰 값을 가리키는 포인터 비슷한 이터레이터 반환

 

다 앞에 * 붙이면 실제 값을 가져올 수 있습니다.

 

벡터에서 중복 원소 제거

#include <algorithm>
#include <vector>
using namespace std;
 
vector<long long> v;
int main() {
    
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
 
}

이렇게 하면 v에는 같은 데이터가 두 개 이상 들어있지 않으며, 오름차순으로 정렬되어 있게 됩니다.

 

원하는 원소를 빠르게 넣고 빼고 싶을 때(set)

헤더파일: <set>

잘 익혀두면 정말 많이 쓰입니다.

#include <set>
using namespace std;
 
set<int> st;
int main() {
 
    st.insert(1); // st에 1 삽입
    st.insert(2); // st에 2 삽입
    st.insert(3); // st에 3 삽입
    st.insert(4); // st에 4 삽입
 
    printf("%d\n", *st.begin()); // 최솟값 출력 - 출력값: 1
    printf("%d\n", *st.rbegin()); // 최댓값 출력 - 출력값: 4
    printf("%d\n", *++st.begin()); // 두 번째로 작은 출력 - 출력값: 2
    printf("%d\n", *++st.rbegin()); // 두 번째로 큰 출력 - 출력값: 3
 
    printf("%d\n", st.find(3) != st.end()); // 3이 st에 있으면 1, 없으면 0 출력 - 출력값: 1
    printf("%d\n", st.find(5) != st.end()); // 5가 st에 있으면 1, 없으면 0 출력 - 출력값: 0
 
    st.erase(3); // st에서 3 삭제
 
    for (int i : st)
        printf("%d ", i); // st의 원소 오름차순으로 하나씩 출력 - 출력값: 1 2 3
    return 0;
}

그냥 배열/벡터 쓰면 된다고 생각할 수 있지만

찾기/삭제 연산이 $O(\log N)$으로 훨씬 빠릅니다. (N은 들어있는 원소 수)

set에는 같은 값이 여러 개 들어갈 수 없습니다. 이미 들어있는 값을 또 넣으려고 하면 그냥 무시합니다.

같은 걸 여러 개 넣고 싶으면 <set>의 multiset을 쓰면 됩니다.

다 똑같은데 삭제 부분만 조금 다릅니다. 여기 참고

 

일대일 대응시키고 싶을 때(map)

헤더파일: <map>

set에서 값 그 자체가 아니라 값에 대응되는 무언가를 정할 수 있습니다.

어떤 값에 접근하면 그 값에 대응되는 값을 얻을 수 있습니다.

접근할 때 쓰는 값을 키(key)라고 부릅니다.

파이썬의 딕셔너리와 비슷한 역할입니다.

쓰는 법은 배열이랑 비슷한데, [] 안에 string, pair 등 아무거나 들어갈 수 있습니다.

보통 다양한 값에 숫자를 하나씩 매기거나 같은 게 몇 개 있는지 카운트하는 용도로 씁니다.

잘 익혀두면 set보다 더 많이 씁니다.

#include <map>
using namespace std;
 
map<char, int> mp;
int main() {
 
    mp['1'] = 1; 
    mp['~'] = 102; 
    mp['^'] = 3121; 
    mp['.']++; // 삽입하지 않은 키에 접근하면 0으로 초기화됨 -> ++했으니 1 증가함
 
    printf("%d\n", mp['~']); // 102 출력
 
    char str[] = "akksssassmb";
    for (int i = 0; str[i] != '\0'; i++)
        mp[str[i]]++; // 각 알파벳이 몇 개씩 나왔는지 카운트
 
    for (char i = 'a'; i <= 'z'; i++)
        printf("%c: %d\n", i, mp[i]); 
    /* 출력값
    a: 2
    b: 1
    c: 0
    d: 0
    ...
    k: 2
    l: 0
    m: 1
    ...
    s: 5
    ...
    y: 0
    z: 0
    */
    return 0;
}