코딩 테스트 전 Cheating Sheet in C++

본 문서는 코딩 테스트에서 유용하게 사용될 수 있는 STL 등을 잠시 흘겨볼 수 있도록 작성된 문서입니다.
자세한 이론은 링크를 달아두었으니 참고하면 됩니다.

목차

  1. 입출력 속도 향상
  2. 모든 라이브러리를 대체하는 라이브러리
  3. string과 char * , int 의 변환
  4. C++ STL Algorithm의 sort 함수
  5. DFS와 BFS의 포인트
  6. union find algorithm
  7. C++ STL string
  8. C++ STL 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
  15. 입력 끝 판단하기

입출력 속도 향상

  • 링크

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

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

  • 링크

    #include <bits/stdc++.h>

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

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를, 비어있지 않다면 false
  • s.size(); : s의 크기를 반환

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(); : 큐의 원소 갯수 반환

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;

+ Recent posts