[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는 정렬된 배열에서 n 이상, 첫번째 idx

upper_bound는 정렬된 배열에서 n 초과, 첫번째 idx

auto lower = lower_bound(v.begin(), v.end(), n);
-> 벡터에서 최초의 n 이상의 값을 iterator 형태로 저장
// idx를 가지고 오기 위해선 -v.begin()

// 직접 구현
int mylower_bound(int num){
  int left = 0;
  int right = v.size() - 1;
  int ans = v.size(); 

  while(left <= right) { 
    int mid = (left + right) / 2;

    if (v[mid] >= num) {
      right = mid - 1;
      ans = mid;
    }
    else left = mid + 1;
  }

  return ans;
}


auto upper = upper_bound(v.begin(), v.end(), n);
-> 벡터에서 최초의 key 초과값을 iterator 형태로 저장 
// idx를 가지고 오기 위해선 -v.begin()

// 직접 구현
int myupper_bound(int num){
  int left = 0;
  int right = v.size() - 1;
  int ans = v.size(); 

  while(left <= right) {
    int mid = (left + right) / 2;

    if (v[mid] <= num) {
      left = mid + 1;
    }
    else {
      right = mid - 1;
      ans = mid;
    }
  }

  return ans;
}

순차탐색 (같은 값)

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

 

부동 소수점 처리

double price = 0.7;
int cents = (int)(price * 100); // 기대값: 70

그런데 실제로 price * 100은 정확히 70.0이 아닙니다.

👉 0.7 * 100 = 69.99999999999999...

그래서 int로 형 변환하면 69가 됩니다. ❌

(int)(price * 100 + 0.5)

price * 100 = 69.9999999

+ 0.5 = 70.4999999

(int)로 바꾸면 70이 됩니다 ✔