원래 이번 포스트는 탐색으로 쓰려고 했는데
그래프 그리기 귀찮아서 stl을 쓰기로 했어요 ㅠㅠ
stl만 다루는 건 아니고, 문제풀이에 사용되는 몇 가지 스킬들에 대해서도 이야기하려고 해요.
원래 map, set, list 등등 많이 다루려고 했는데
포스트가 교내대회 교육용이기도 하고… 출제범위 밖이기도 하고… 귀찮기도 하고…
그리고 제일 중요한 건! 이 포스트에서는 stl의 사용법에 대해서 다루지 않습니다.
대신 stl을 어떻게 사용해야하는지, stl의 활용법에 대해서 다룹니다.
문법에 대한 건 http://www.cplusplus.com 여기에 다 나와있어요 >_<
그리고 또 어차피 stl 컨테이너가 다 거기서 거기 아니겠어요? 하하하하하
push, push_back, pop, size, length, empty, top, front, end, begin 다 똑같아요 ㅎㅎ
Honey Tip
여러가지 꿀팁들에 대해서 설명합니다.
define
사실 저는 define을 딱히 자주 쓰는 편은 아니에요.
const로 할 수 있으면 const를 선호해요.
하지만 꼭 define을 사용하는 경우가 있어요.
#define y1 WhoDefinedFuckingY1FunctionAtMathHeader
진짜 이거 화납니다.
int x1, y1, x2, y2하면 에러나요…
그리고 define을 이렇게 쓰면 코드가 깔끔해지기도 합니다.
#define first fst
#define second snd
pair<int, int> pos;
int nx = pos.fst, ny = pos.snd;
저는 배열 이름이나 변수 이름 같은 걸 3글자로 줄여서 쓰는 걸 선호하는 편인데,
저렇게 쓰면 코드가 엄청 깔끔해져요.
대회에서는 이렇게 써서 시간단축/실수방지 하기도 합니다.
#define pb(x) push_back(x)
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
const
const int MOD = 1e9 + 7;
const int IT_INF = 987654321;
const ll LL_INF = 1234567890123456789ll;
이런 건 대회에서 너무너무너무 자주 쓰는 것들이에요.
저는 또 이런 것도 좋아해요.
const int n_ = 1e6 + 1;
int arr[n_], dst[n_], idx[n_];
vector<int> gph[n_];
코드가 간결하고 깔끔해져요.
typedef
자료형 이름을 짧게 축약하는 거에요.
typedef long long ll;
typedef unsigned long long ull;
typedef double dbl;
typedef long double ldb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
그래서 저걸 이런 식으로 쓸 수 있어요.
vector<pii> abc;
dbl dst[n_];
ll cnt_max = LL_INF;
STL
문제 풀이에서 흔하게 사용되는 stl의 활용에 대해서 설명합니다.
vector
아주 훌륭한 녀석입니다.
같은 크기의 배열에 비해서 메모리랑 시간을 조금 더 많이 먹긴 하지만 (사실 이건 모든 stl 종특이에요)
배열인데, 크기가 변하는 배열이에요.
시도때도 없이 vector를 쓰는 건 손해지만, 상황에 맞게 쓰는 건 아주 좋아요.
가장 대표적으로 그래프를 표현할 때 vector를 사용해요.
인접행렬로 돌리는 dfs는 O(V^2)이 걸리지만 vector를 사용하는 dfs는 O(V+E) 밖에 걸리지 않아요.
vector<int> gph[n_];
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
gph[u].push_back(v);
gph[v].push_back(u);
}
그리고 갯수가 정해지지 않은 결과값을 저장하기도 편해요.
for (int i = 0; i < n; i++) {
if (!chk[i]) {
int ret = dfs(i);
ans.push_back(ret);
}
}
for (auto abc : ans) printf("%d ", ans);
stl의 킬링파트 바로 이거죠! 너무 편해요!
string str;
for (auto ch : str) printf("%c", ch);
vector<edg> gph[n_];
for (auto nxt : gph[now]) if (!chk[nxt]) dfs(nxt);
vector<vector<int> > res;
for (auto aux : res) for(auto tmp : aux) printf("%d ", tmp);
아 그리고 gcc에서는 vector<vector<int>> 이거 에러납니다.
>>를 비트 연산자로 인식해서 vector<vector> >로 띄어서 써주어야 해요.
priority queue
정말 좋아요.
힙을 직접 짜지 않아도 돼요.
다익스트라 짜기도 정말 편해요.
priority_queue<edg> pq;
while (!pq.empty()) {
edg now = pq.top();
pq.pop();
if (now.dst != dst[now.idx]) continue;
for (auto nxt : gph[now.idx]) {
if (dst[nxt.idx] > dst[now.idx] + nxt.dst) {
dst[nxt.idx] > dst[now.idx] + nxt.dst;
pq.push(edg(nxt.idx, dst[nxt.idx]));
}
}
}
여러모로 쓸모가 많아요.
sort, lambda, struct, operator
보통 sort의 compare 함수를 작성해서 사용하는데
stl sort의 기본 operator를 아래처럼 struct에 정의하거나, 람다로 간편하게 쓸 수도 있어요.
bool compare(const edg &i, const edg &j) {
return i.dst > j.dst;
}
sort(arr, arr+n, compare);
//////////////////
sturct edg {
int idx, dst;
edg() {}
edg(int idx, int dst) : idx(idx), dst(dst) {}
bool operator <(edg A)const { return dst > A.dst };
} arr[n_];
sort(arr, arr+n);
//////////////////
sort(arr, arr+n, [](const edg &i, const edg &j){ return i.dst > j.dst; });
사실 이건 cpp의 영역이라 몰라도 상관없긴 해요.
하지만 알아두면 너무 편해요.
으악
나중에 마저 써야지
아무말
stl, standard template library, vector, pair, stack, queue, sort, algorithm, using namespace std, 벡터, 백터, 페어, 스택, 스텍, 큐, 알고리즘, 표준 템플릿 라이브러리, define, const, 람다, lambda, struct, 구조체, operator, priority queue, 우선순위 큐