[참고자료] 코딩테스트 유용한 함수&자료

[ 헤더 파일 뭉탱이 선언 ]
#include <bits/stdc++.h> : 표준 라이브러리 헤더파일을 한번에 선언하는 것

 

[ 올림, 내림, 반올림 ]
#include <cmath> 추가

- 올림: ceil(double, float, long double N);     -> 4.2 = 5

- 내림: floor(double, float, long double N);   -> 4.2 = 4

 

- 반올림 방법1: round(double, float, long double N); 

- 반올림 방법2: floor(N + 0.5);   -> 4.2 = 4 / 4.6 = 5

- ceil 없이 올림: int num = (A / B) +1;

 

[ 특정 내용으로 배열 채우기 ]

- 헤더파일 #include <cstring> 추가 - (Visual Studio에서는 헤더파일이 없어도 되지만, 백준에서는 안쓰니까 오류났음)

memset(배열, 채울내용, 크기)

ex) bool[10] b;

     memset(b, true, sizeof(b));

 

@ 주의사항: memset은 0또는 -1로만 내용을 채울 수 있다!!! 그 밖의 값으로 배열을 채우려면 fill 함수 사용

 

- 헤더파일 없이 std 함수 : fill

1차원 배열: vector<int> arr;

fill(arr.begin(), arr.end(), 채울내용);

2차원 배열: vector<vector<int>> arr;

fill(arr.begin(), arr.end(),  vector<int>(열 개수, 채울내용))

ex) vector<vector<int>> arr(5, vector<int>(5));

fill(arr.begin(), arr.end(), vector<int>(5, 10));  -> 2차원 배열을 모두 10 으로 채우기

 

[ set<> 자료형 -> vector 중복 없이 카운트하기 ]

- set: 노드 기반 컨테이너이며 균형 이진트리로 구성되었다.

- Key라고 불리는 원소들의 집합으로 이루어진 컨테이너

- 이때 Key값은 중복되지 않는다.

- insert 멤버로 삽입하면 자동 정렬(default 오름차순)된다.

#include <set> 필요

map이랑 비슷한데 value값은 없이 키값만 필요할 때 쓰면 좋을거같음 + vector를 중복 없애고싶을때 사용하기 매우 좋음

unordered 있는것도 다 똑같도 count 함수도 동일

* 벡터 변환 초기화 방법: set<int> nums(vector.begin(), vector.end());

 

[ Heap, 우선순위 큐 (Priority Queue) ]

#include <queue> 추가

- 최대힙(내림차순) : priority_queue<int> pq;   →  Default 가 내림차순 (3,2,1)

- 최소힙(오름차순) : priority_queue<int, vector<int>, greater<int>> pq;  → (1,2,3)

- 문자열 내림차순 정렬 : priority_queue<string, vector<string>> pq; → (C, B, A)

 

[ 순열 구하기 ]

#include <algorithm> 추가

- 함수 사용 전 next는 오름차순으로, prev는 내림차순으로 꼭 정렬하기!!

- next_permutation(begin(), end())

- prev_permutation(begin(), end())

결과: 123 next로 돌리기 -> 123,132,213,231,312,321

         321 prev로 돌리기 -> 321,312,231,213,132,123

 

[ 2진수 변환 bitset ]

#include <bitset> 추가

- 특정 숫자 2진수로 변환 : bitset<자릿수>(2진수로 바꿀숫자)

- 단순 선언: bitset<자릿수> 변수명;

- 예시: int num = bitset<20>(15).count();    // 1의 개수 count

- 예시: cout << bitset<20>(15).to_string();  // 2진수 string으로 출력

그밖에 함수들

bit.set() : 전체 비트를 1로 셋팅

bit.reset() : 전체 비트를 0으로 셋팅

bit.any() : 하나라도 1이면 1을 반환, 모두 0일때만 0 반환

bit.none() : 모두 0 이어야 1을 반환

bit.flip() : 전체 비트를 반전

 

[ 두 원소 중 하나의 원소로만 배열 정렬하기 ]

vector<pair<int, string>> v;

- stable_sort(v.begin(), v.end(), Comp);

 

bool Comp(pair<int, string> a, pair<int, string> b)

{

    return a.first > b.first;

}

이렇게 정렬을 수행하면 int 원소로만 정렬을 수행하고, int 원소가 같은 경우 입력 순서대로 출력됨

 

[ map 자료형 정렬하기 ]

map<string, int> m : 오름차순 정렬

map<string, int, greater<>> m : 내림차순 정렬

 

[ map 자료형 역순 출력 (iterator 활용) ]

map<string, int> m;

for(auto iter = m.rbegin(); iter != m.rend(); iter++)

    cout << iter->first << '\n';

 

[ 합집합, 교집합, 차집합 ]

set_union : 합집합

set_intersection : 교집합

set_difference : 차집합

- 해당 함수들을 사용하기 위해선 벡터의 공간을 미리 확보해야 한다.

- 반환값은 삽입이 끝난 후의 끝 지점 iterator.

 

vector<int> A(벡터크기);

vector<int> B(벡터크기);

vector<int> Result;

auto iter = set_difference(A.begin(), A.end(), B.begin(), B.end(), Result.begin());

Result.erase(iter, Result.end());