[C++] 코딩 테스트 Cheating Sheet

1. 입출력 속도 향상

ios_base::sync_with_stdio(false);
cin.tie(NULL);	cout.tie(NULL);

2. 모든 라이브러리를 대체하는 라이브러리

#include <bits/stdc++.h>

3. string과 char *, int의 변환

(1) char * → string

char * cStr = "Cstring";
string appStr = cStr;

(2) string → char *

string cStr = "Cstring";
const char * cStr2 = cStr.c_str(); // const 타입으로 리턴

(3) char * → int

char * csTr = "20200701";
int num = atoi(cStr);

(4) string → char * → int

string s = "2020";
int num = atoi(s.c_str());

4. C++ STL Algorithm의 sort 함수

(1) array의 경우

// 오름차순
int arr1[10] = {5, 4, 3, 2, 1, 9, 8, 7, 6, 10};
sort(arr1, arr1 + 10);

// 내림차순
int arr2[10] = {5, 4, 3, 2, 1, 9, 8, 7, 6, 10};
sort(arr2, arr2 + 10, greater<int>());

(2) vector의 경우

// 오름차순
sort(v.begin(), v.end());

// 내림차순
sort(v.rbegin(), v.rend());

5. DFS와 BFS의 포인트

(1) DFS

DFS 함수의 파라미터로 무엇을 넘기고 넣을 것인가
DFS의 초깃값을 어떻게 잡을 것인가
언제 DFS를 멈추게 할 것인가
DFS 함수 내에서 새 DFS 함수를 호출할 때 문제의 조건에 맞게 적절히 호출하는가

(2) BFS

queue의 데이터 타입
queue의 초기값
q.front() 원소가 답이 될 수 있는지, 혹은 정보 update가 가능한 지 check 이후 행동
읽어온 원소로부터 queue에 push할 수 있는 원소를 push 하기

6. union find algorithm

#include <bits/stdc++.h>
using namespace std;

int n, m, a, b, temp;
vector<int> arr(1001);

int find(int index){
	if(arr[index] == index) return index;
	else return arr[index] = find(arr[index]);
}

void union(int a, int b){
	a = find(a);
	b = find(b);
	if(a != b) arr[a] = b;
}

int main(){
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n ; i++)
		arr[i] = i;
	for(int i = 1; i <= m; i++){
		scanf("%d %d", &a, &b);
		union(a, b);
	}

	scanf("%d %d", a, b);
	if(find(a) == find(b)) printf("YES");
	else printf("NO");
}

7. C++ STL string

(1) .at

해당 위치에 해당하는 문자를 반환

String str = "myName";
char c = str.at(0) // c = 'm'

(2) .assign

문자열을 할당
(문자열) : 문자열을 할당
(개수, 문자) : 문자를 개수만큼 할당
(문자열, 시작위치, 개수) : 문자열의 시작 위치부터 개수만큼을 할당

string s1, s2, s3;

s1.assign("ABCDEFG"); // s1 = "ABCDEFG"
s2.assign(3, 'a'); // s2 = "aaa"
s3.assign(s1, 2, 4); // s3 = "CDEF"

(3) .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"

(4) .clear

문자열의 내용을 모두 삭제

(5) .empty

문자열이 비어있는 지 확인

(6) .substr

문자열의 일부분을 문자열로 반환
(시작위치) : 시작위치부터 끝까지의 문자들을 문자열로 반환
(시작위치, 개수) : 시작위치부터 개수만큼의 문자를 문자열로 반환

string s = "ABCDEF";
string s2 = s.substr(4); // s2 = "EF" (index 4부터 끝까지의 문자열을 반환)
string s3 = s.substr(1,3); // s3 = "BCD" (index 1부터 3까지의 문자열을 반환)

(7) .strstr(char * a, char * b)

문자열의 일부분을 잘라서 반환
(시작위치) : 시작위치부터 끝까지의 문자들을 반환
(시작위치, 개수) : 시작위치부터 개수만큼의 문자를 반환

#include <bits/stdc++.h>
using namespace std;

char a[1000001], b[1000001];

// 문자열 a 안에 b와 같은 문자열이 있는지 확인할 수 있다.
int main(){
	cin >> a >> b;
	if (strstr(a, b) == NULL) cout << 0;
	else cout << 1;
}

8. C++ STL vector

(1) 다양한 vector 선언

// empty vector
vector<int> a;

// size가 정의된 vector
vector<int> b(5);

// vector 배열
vector<int> c[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[1].push_back(make_pair(3, 5));
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());
	// ...
}

(2) vector 중복값 제거

sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

9. C++ STL stack

stack<int> s;
s.push(element) : top에 원소를 추가
s.pop() : top에 있는 원소를 삭제
s.top() : top에 있는 원소를 반환
s.empty() : s가 비어있다면 true를, 비어있지 않다면 false를 반환
s.size() : s의 크기를 반환

10. C++ STL queue

queue<int> q;
q.push(element) : 큐에 원소 push
q.pop() : 큐의 원소 pop
int a = q.front() : 큐 제일 앞에 있는 원소 반환
int b = q.back() : 큐 제일 뒤에 있는 원소 반환
q.empty() : 큐가 비어있으면 true, 비어있지 않다면 false
q.size() : 큐의 원소 갯수 반환

11. C++ STL priority_queue

// 최대 힙 - 부모 노드가 최댓값
priority_queue<int, vector<int>, less<int>> max_heap;

// 최소 힙 - 부모 노드가 최솟값
priority_queue<int, vector<int>, greater<int>> 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) {
            if (x = b.x) {
                return y > b.y;
            } else {
                return x > b.x;
            }
        } else {
            return dis > b.dis;
        }
    }
}

priorty_queue<State> q;

12. C++ STL map

// map 선언
map<char, int> m;

// map의 key로 접근하여 value 조회/변경/추가
cout << m['c'] << endl;
m['c']++;
m['d'] = 4;

개발자가 추가하지 않은 value를 출력하려고 하면, 오류가 아닌 0을 출력해준다.
map의 모든 원소 출력

// 1. iterator
map<char, int>::iterator itr;

for(itr = m.begin(); itr != m.end(); itr++) {
    cout << itr->first << " " << itr->second << endl;
}

// 2. auto
for (auto & k : m) {
    cout << k.first << " " << k.second << endl;
}

13. min_element, max_element

// array

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;
cout << *max_element(v.begin() + 2, v.begin() + 5) << endl; // v[2] ~ v[4] 중 max 값

14. next_permutation

(1) 순열 : permutation

앞에서부터

sort(v.begin(), v.end());
do {
    // logic
} while (next_permutation(v.begin(), v.end());

뒤에서부터

sort(v.rbegin(), v.rend());
do {
    // logic
} while (next_permutation(v.begin(), v.end());

(2) 조합 : combination

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()));
}

15. 입력 끝 판단하기

cin >> n >> m;
if(cin.eof()) return;

'Coding Test' 카테고리의 다른 글

[Python] 코딩 테스트 Cheating Sheet (1)	2022.09.23

1. 입출력 속도 향상

2. 모든 라이브러리를 대체하는 라이브러리

3. string과 char *, int의 변환

(1) char * → string

(2) string → char *

(3) char * → int

(4) string → char * → int

4. C++ STL Algorithm의 sort 함수

(1) array의 경우

(2) vector의 경우

5. DFS와 BFS의 포인트

(1) DFS

(2) BFS

6. union find algorithm

7. C++ STL string

(1) .at

(2) .assign

(3) .append

(4) .clear

(5) .empty

(6) .substr

(7) .strstr(char * a, char * b)

8. C++ STL vector

(1) 다양한 vector 선언

(2) vector 중복값 제거

9. C++ STL stack

10. C++ STL queue

11. C++ STL priority_queue

12. C++ STL map

13. min_element, max_element

14. next_permutation

(1) 순열 : permutation

(2) 조합 : combination

15. 입력 끝 판단하기

'Coding Test' 카테고리의 다른 글

티스토리툴바