[C++] 코딩테스트 알고리즘 c++ 문법 정리

#include <bits/stdc++.h>

using namespace std;

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

 

sort 사용자 정의 정렬

// 1차원 벡터
bool cmp(int a, int b) return a < b;

// 2차원 벡터
bool cmp(vector<int> &v1, vector<int> &v2){
  if(v1[1] == v2[1])
    return v1[0]<v2[0];
  else return v1[1]<v2[1];
}

// pair 벡터
bool cmp(pair<int, int> u, pair<int, int> t){
  if(u.first==t.first)
	return u.second < t.second;
  return u.first < t.first;
}

sort(v.begin(), v.end(), cmp);

 

정렬 후, 중복제거

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

 

정렬된 경우 이분탐색 (크거나 같은 값, 더 큰 값)

lower_bound는 정렬된 배열에서 탐색값이 2개 이상 있는 경우 가장 앞에 위치한 탐색값

upper_bound는 가장 뒤에 위치한 탐색값의 다음 위치 

auto lower = lower_bound(v.begin(), v.end(), n);
-> 벡터에서 최초의 n 이상의 값을 iterator 형태로 저장
auto upper = upper_bound(v.begin(), v.end(), n);
-> 벡터에서 최초의 key 초과값을 iterator 형태로 저장

if(lower_bound(v.begin(), v.end(), n) == v.end()) {
    // no such value
}

순차탐색 (같은 값)

find(v.begin(), v.end(), n);

 

문자열

문자열을 찾을 수 없는 경우

if(str.find("asdf") == string::npos) {
    // cant find
}

 

문자열을 여러개의 정수형으로

int A, B, C;
stringstream ss("123 456 789");
ss >> A >> B >> C;

 

if (find(A.begin(), A.end(), s) == A.end())
    return 0;
else return 1;

find(A.begin(), A.end(), s);
// find(찾으려는 범위의 시작 iterator, 끝 iterator, 찾으려는 값);
// A.end()를 반환한다면 해당 범위에서 s를 찾지 못한 것!

 

map / set

vector 내부 map 정렬

map<string, int> m;

vector<pair<string, int>> v(m.begin(), m.end());

sort(v.begin(), v.end(), compare);

 

값 존재 확인, 값 제거

m.count("asdf"); s.count(1234);
m.erase("asdf"); s.erase(1234);

 

queue / priority_queue

우선순위큐 오름차순, 내림차순 (default 내림차순)

priority_queue<int, vector<int>, greater<int>> pq; // 오름차순
priority_queue<int, vector<int>, less<int>> pq; // 내림차순 default

 

우선순위큐 사용자 설정 정렬

struct cmp{
	bool operator()(int a, int b){
    	return a < b;
    }
};
priority_queue<int, vector<int>, cmp> pq;

 

배열 초기화

// 0이나 -1로 초기화
memset(arr, 0, sizeof(arr))

// 다른 값으로 초기화
fill(&arr[0][0], &arr[N][N], INF);

 

문자열을 어떤 문자로 나누기

string str = "hello world";
istringstream  iss(str);

vector <string> words;
string word;

while(iss >> word) {
words.push_back(word);
}