코딩 테스트 전 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
- 입력 끝 판단하기
입출력 속도 향상
-
ios_base::sync_with_stdio(false); cin.tie(NULL);
모든 라이브러리를 대체하는 라이브러리
-
#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
해당 위치에 해당하는 문자를 반환
String str = "MyName"; char c = str.at(0); // c = 'M'
.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)
부모 노드가 최댓값
priority_queue<int, vector<int>, less<int>> pq;
최소 힙 (MIN HEAP)
부모 노드가 최솟값
priority_queue<int, vector<int>, greater<int>> pq;
우선순위 큐에 사용자 정의 함수 적용하기
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의 단일 원소 출력
주의 : 개발자가 추가하지 않는 value를 출력하려고 할 때 오류를 반환하지 않고 0을 출력해준다.
cout << m['c'] << endl;
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;