코딩 테스트 전 Cheating Sheet in C++
본 문서는 코딩 테스트에서 유용하게 사용될 수 있는 STL 등을 잠시 흘겨볼 수 있도록 작성된 문서입니다.
자세한 이론은 링크를 달아두었으니 참고하면 됩니다.
목차
- 입출력 속도 향상
- 모든 라이브러리를 대체하는 라이브러리
- string과 char * , int 의 변환
- C++ STL Algorithm의 sort 함수
- DFS와 BFS의 포인트
- union find algorithm
- C++ STL string
- C++ STL vector
- C++ STL stack
- C++ STL queue
- C++ STL priority_queue
- C++ STL map
- min_element, max_element
- next_permutation
- 입력 끝 판단하기
입출력 속도 향상
모든 라이브러리를 대체하는 라이브러리
링크
#include <bits/stdc++.h>
string과 char * , int 의 변환
char * -> string
char * cStr = "Cstring";
string appStr = cStr;
string -> char *
string cStr = "Cstring";
const char * cStr2 = cStr.c_str();
// const 타입으로 리턴되는 것을 기억
char * -> int
char * cStr = "20200701"
int num = atoi(cStr);
string -> char * -> int
string s = "2020"
int num = atoi(s.c_str());
C++ STL Algorithm의 sort 함수
배열인 경우
오름차순
int arr[10] = {5, 4, 3, 2, 1, 9, 8, 7, 6, 10};
sort(arr, arr + 10);
내림차순
int arr[10] = {5, 4, 3, 2, 1, 9, 8, 7, 6, 10};
sort(arr, arr + 10, greater<int>());
vector인 경우
오름차순
sort(v.begin(), v.end());
내림차순
sort(v.rbegin(), v.rend());
DFS와 BFS의 포인트
DFS
- DFS 함수의 파라미터로 무엇을 넘기고 넣을 것인가
- DFS의 초깃값을 어떻게 잡을 것인가
- 언제 DFS를 멈추게 할 것인가
- DFS 함수 내에서 새 DFS 함수를 호출할 때 문제의 조건에 맞게 적절히 호출하는가
BFS
- queue의 데이터 타입
- queue의 초깃값
- q.front() 원소가 답이 될 수 있는지, 혹은 정보 update가 가능한지 check 이후 행동
- 읽어온 원소로부터 queue에 push할 수 있는 원소를 push 하기
C++ STL string
.at
.assign
문자열을 할당
( 문자열 ) : 문자열을 할당
( 개수, 문자 ) : 문자를 개수만큼 할당
( 문자열, 시작위치, 개수 ) : 매개변수 문자열의 시작 위치부터 개수만큼을 호출한 문자열에 할당
string s1, s2, s3;
s1.assign("ABCDEFG"); // s1 = "ABCDEFG"
s2.assign(3,'a'); // s2 = "aaa"
s3.assign(s1,2,4); // s3 = "CDEF"
.append
문자열을 끝에 더한다
( 문자열 ) : 문자열을 더한다
( 개수, 문자 ) : 문자를 개수만큼 끝에 더한다
( 문자열, 시작위치, 개수 ) : 매개변수 문자열의 시작 위치부터 개수 만큼을 호출한 문자열에 할당
string s1, s2;
s1.append("ABCDEF"); // s1 = "ABCDEF"
s1.append(3,'x'); // s1 = "ABCDEFxxx"
s2.append(s,2,4); // s2 = "CDEF"
s2 += "X"; // s2 = "CDEFX"
.clear
문자열의 내용을 모두 삭제
s.clear();
.empty
문자열이 비어있는 지 확인
s.empty();
.substr
문자열의 일부분을 문자열로 반환
( 시작위치 ) : 시작위치부터 끝까지의 문자들을 문자열로 반환
( 시작위치, 개수 ) : 시작위치부터 개수만큼의 문자를 문자열로 반환
string s = "ABCDEF";
string s2 = s.substr(4); // s2 = "EF" (index 4부터 끝까지의 문자열을 반환)
string s3 = s.substr(1,3); // s3 = "BCD" (index 1부터 3까지의 문자열을 반환)
.strstr(char * a, char * b)
문자열 a에 문자열 b가 포함되어 있는지, 즉 부분 문자열인지 확인한다.
없다면 NULL을 리턴함
#include <bits/stdc++.h>
using namespace std;
char a[1000001], b[1000001];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> a >> b;
if (strstr(a, b) == NULL) cout << 0;
else cout << 1;
}
C++ STL vector
vector 생성
empty vector 생성
vector<int> a;
size가 정의된 vector 생성
vector<int> a(5);
vector 배열 생성
vector<int> a[3];
c[0].push_back(1);
c[0].push_back(2);
c[1].push_back(2);
c[2].push_back(3);
cout << c[1][0] << endl;
pair와 vector를 혼합
vector< pair<int, int> > graph[3];
graph[1].push_back({3, 5});
graph[2].push_back(make_pair(7, 7));
cout << graph[1][0].first << " " << graph[2][0].second << endl;
struct와 vector를 혼합
struct Data{
int money;
int when;
Data(int a, int b){
money = a;
when = b;
}
bool operator<(const Data &b) const {
return when > b.when;
}
};
int main(){
vector<Data> T;
// ...
T.push_back(Data(a, b));
sort(T.begin(), T.end());
// ...
}
vector 중복값 없애기
sort(v.begin(), v.end());
v.erase(unique(v.begin(),v.end()), v.end());
C++ STL stack
- 링크
stack<int> s;s.push(element); : top에 원소를 추가s.pop(); : top에 있는 원소를 삭제int a = s.top() : top에 있는 원소를 반환s.empty(); : s가 비어있다면 true를, 비어있지 않다면 falses.size(); : s의 크기를 반환
C++ STL queue
- 링크
queue<int> q;q.push(element); : 큐에 원소 pushq.pop(); : 큐의 원소 popint a = q.front(); : 큐 제일 앞에 있는 원소 반환int b = q.back(); : 큐 제일 뒤에 있는 원소 반환q.empty(); : 큐가 비어있으면 true, 비어있지 않다면 falseq.size(); : 큐의 원소 갯수 반환
C++ STL priority_queue
최대 힙 (MAX HEAP)
최소 힙 (MIN HEAP)
우선순위 큐에 사용자 정의 함수 적용하기
struct State{
int x, y, dis;
State(int a, int b, int c){
x = a; y = b; dis = c;
}
bool operator < (const State & b) const {
if(dis == b.dis){
// prior 3
if(x = b.x) return y > b.y;
// prior 2
else return x > b.x;
}
// prior 1
else return dis > b.dis;
}
};
priority\_queue Q;
C++ STL map
map 선언
map<char, int> m;
map의 key로 접근하여 value 바꾸기 / 추가하기
m['c']++;
m['d'] = 7;
map의 모든 원소 출력
// with iterator
map<char, int>::iterator itr;
for(itr = m.begin(); itr != m.end(); itr++){
cout << itr->first << " " << itr->second << endl;
}
// with auto
for(auto &k : m){
cout << k.first << " " << k.second << endl;
}
map의 단일 원소 출력
min_element, max_element
배열에서
int *arr = new int[size];
for(int i = 0; i < size; i++){
cin >> arr[i];
}
cout << "max : " << *max_element(arr, arr + size) << endl;
cout << "min : " << *min_element(arr, arr + size) << endl;
vector에서
vector<int> v;
for(int i = 0; i < size; i++){
cin >> val;
v.push_back(val);
}
cout << "max : " << *max_element(v.begin(), v.end()) << endl;
cout << "min : " << *min_element(v.begin(), v.end()) << endl;
- 만약
max_element(v.begin() + 2, v.begin() + 5) 라고 사용했다면 v[2]부터 v[4]까지 중 최대값을 찾아준다.
next_permutation
순열 (permutation)
오름차순에서 내림차순으로
sort(v.begin(), v.end());
do{
// do something
} while(next_permutation(v.begin(), v.end());
내림차순에서 오름차순으로
sort(v.rbegin(), v.rend());
do{
// do something
} while(next_permutation(v.rbegin(), v.rend());
조합 (combination)
by DFS
#include <bits/stdc++.h>
using namespace std;
int n, r, ch[20];
void dfs(int s, int L){
if(L == r){
for(int i = 0; i < r; i++)
printf("%d ", ch[i]);
printf("\n");
}
else{
for(int i = s; i < n; i++){
ch[L] = i;
dfs(i + 1, L + 1);
}
}
}
int main(){
cin >> n >> r;
dfs(0, 0);
}
오름차순에서 내림차순으로
#include <bits/stdc++.h>
using namespace std;
int n, r;
int main (){
cin >> n >> r;
vector<int> v, ind;
for(int i = 0; i < n ; i++)
v.push_back(i);
for(int i = 0; i < r; i++)
ind.push_back(0);
for(int i = 0; i < n - r; i++)
ind.push_back(1);
sort(ind.begin(), ind.end());
do{
for(int i = 0; i < n; i++){
if(ind[i] == 0)
printf("%d ", v[i]);
}
printf("\n");
}while(next_permutation(ind.begin(), ind.end()));
}
내림차순에서 오름차순으로
#include <bits/stdc++.h>
using namespace std;
int n, r;
int main (){
cin >> n >> r;
vector<int> v, ind;
for(int i = 0; i < n ; i++)
v.push_back(i);
for(int i = 0; i < r; i++)
ind.push_back(1);
for(int i = 0; i < n - r; i++)
ind.push_back(0);
sort(ind.begin(), ind.end());
do{
for(int i = 0; i < n; i++){
if(ind[i] == 1)
printf("%d ", v[i]);
}
printf("\n");
}while(next_permutation(ind.begin(), ind.end()));
}
입력 끝 판단하기
cin >> n >> m;
if(cin.eof()) return;
