C++ Summary 2

C++에서 주로 사용되는 문법을 정리한다.

1. 기본 (입출력 최적화)

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

• ios::sync_with_stdio(false) : C / C++ 입출력 동기화 해제
• cin.tie(NULL) : cout flush 방지
• 대량 입출력 문제에서 시간초과 방지

---

2. STL 컨테이너

2.1 vector

vector<int> v;

v.push_back(10);
v.push_back(20);

cout << v[0];

v.pop_back();

sort

정렬

sort(v.begin(), v.end()); // 오름차순
sort(v.begin(), v.end(), greater<int>()); // 내림차순

커스텀 정렬

sort(v.begin(), v.end(), [](int a, int b)
{
    return a > b;
});

---

erase-remove

특정 값 삭제

vector<int> v = {1,3,2,3,4};

v.erase(remove(v.begin(), v.end(), 3), v.end());

>> 결과
1 2 4

---

unique

중복 제거

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

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

---

lower_bound / upper_bound

vector<int> v = {1,2,2,2,3};

int idx = lower_bound(v.begin(), v.end(), 2) - v.begin();

>> 결과
1

• lower_bound : x 이상 첫 위치
• upper_bound : x 초과 첫 위치

---

binary_search

vector<int> v = {1,2,3,4,5};

bool exist = binary_search(v.begin(), v.end(), 3);

---

2.2 string

find

문자열 검색

string s = "hello world";

int pos = s.find("world");

if(pos == string::npos)
{
    cout << "not found";
}

---

substr

문자열 자르기

string s = "abcdef";

cout << s.substr(2,3);

>> 결과
cde

---

replace

문자열 치환

string s = "abcdef";

s.replace(2,3,"ZZ");

>> 결과
abZZf

여러 번 치환

string s = "ayaaya";

int pos;

while((pos = s.find("aya")) != string::npos)
{
    s.replace(pos,3,"!");
}

---

erase

문자 삭제

string s = "abcdef";

s.erase(2,3);

>> 결과
abf

---

getline

공백 포함 입력

string line;

while(getline(cin,line))
{
    cout << line;
}

---

2.3 pair

두 값을 묶어서 저장

pair<int,int> p = {3,5};

cout << p.first;
cout << p.second;

BFS에서 많이 사용

queue<pair<int,int>> q;

---

2.4 map

정렬된 key-value 저장

map<string,int> m;

m["apple"] = 3;

cout << m["apple"];

• 자동 정렬
• 시간복잡도 O(logN)

---

2.5 unordered_map

해시맵

unordered_map<string,int> m;

m["apple"] = 3;

• 평균 O(1)
• 정렬 없음

---

2.6 set

중복 없는 집합

set<int> s;

s.insert(3);
s.insert(3);
s.insert(5);

for(int x : s)
{
    cout << x;
}

출력

3 5

---

2.7 stack

stack<int> s;

s.push(10);
s.push(20);

cout << s.top();

s.pop();

---

2.8 queue

queue<int> q;

q.push(10);
q.push(20);

cout << q.front();

q.pop();

---

2.9 priority_queue (힙)

priority_queue<int> pq;

pq.push(5);
pq.push(10);
pq.push(1);

cout << pq.top();

결과

10

최소 힙

priority_queue<int, vector<int>, greater<int>> pq;

---

3. 그래프 탐색

BFS

queue<int> q;

q.push(1);

while(!q.empty())
{
    int cur = q.front();
    q.pop();

    for(int next : graph[cur])
    {
        if(!visited[next])
        {
            visited[next] = true;
            q.push(next);
        }
    }
}

---

DFS

void dfs(int node)
{
    visited[node] = true;

    for(int next : graph[node])
    {
        if(!visited[next])
        {
            dfs(next);
        }
    }
}

---

격자 탐색

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

for(int i=0;i<4;i++)
{
    int nx = x + dx[i];
    int ny = y + dy[i];
}

---

4. 알고리즘 패턴

Prefix Sum (누적합)

vector<int> psum(n+1);

for(int i=1;i<=n;i++)
{
    psum[i] = psum[i-1] + arr[i];
}

구간합

sum = psum[r] - psum[l-1];

---

Two Pointer

int l = 0;
int r = 0;

while(r < n)
{
    sum += arr[r];

    while(sum > target)
    {
        sum -= arr[l];
        l++;
    }

    r++;
}

---

Binary Search

int l = 0;
int r = n-1;

while(l <= r)
{
    int mid = (l+r)/2;

    if(arr[mid] == target)
        break;

    if(arr[mid] < target)
        l = mid + 1;
    else
        r = mid - 1;
}

---

5. math

#include <cmath>

함수	설명
abs(x)	절댓값
sqrt(x)	루트
pow(a,b)	거듭제곱
ceil(x)	올림
floor(x)	내림