[ 문제 한줄평 ]
cout, cin 수행 시간 쓰레기
11438번 : LCA 2
플!레!티!넘!
근데 딱히 문제 자체가 어려운건 아니고 메모리 초과와 시간 초과를 잘 헤쳐나갈 방법을 아는가? 모르는가?의 문제인 듯 하다. 그게 문제 자체가 어려운거잖아 그리고 사실 메모리 초과는 나만 멍청해서 난거임
어쨋든 이번 문제는 LCA Binary Lifting을 일단 알아야 하는 문제이다. 이 개념을 모른다면 시간 초과를 벗어나지 못할 것! 아직 binary lifting 포스팅 안했다
이번 문제에서 알게 된 것은 두 개가 있다. 밑에 정리해보도록 하겠다.
cin, cout의 수행 시간은 쓰레기이다
그렇다. 제목 그대로이다. cin, cout 편해서 자주 썼는데, 안쓸거다.
cin과 cout이 <cstdio>에 들어 있는 C언어 타입의 입출력인 printf, scanf보다 느리다는 것은 알고 있긴 했지만, 이렇게 느려 터졌을 줄이야.
ios::sync_with_stdio(false); 를 사용하면 된다?
예전에 한번 cin, cout 때문에 시간 초과가 발생했을 때, ios::sync_with_stdio(false); 이 친구를 입출력 전에 쓰면 cin, cout이 빨라진다고 해서 그냥 그런갑다 하고 썼었다.
얘가 뭘 하는 자식인지 이제서야 알아보니, ios::sync_with_stdio는 C++ 표준 스트림들이 C 표준 스트림들과 각각의 입출력 연산 후에 동기화할지 여부를 설정한다고 한다. ios::sync_with_stdio(true)가 기본값으로, 동기화된 C++ 스트림들이 자신들의 버퍼를 사용하지 않고 C++ 스트림의 입출력 연산들이 이에 대응되는 C 스트림 버퍼를 직접 사용한다는 의미와 같다.
고로, 기본값인 ios::sync_with_stdio(true)를 이용할 때는 C++ 스트림이나 C 스트림이나 모두 C 스트림 버퍼를 이용하기 때문에 C++ 입출력 연산과 C 입출력 연산들을 혼합해서 사용할 수 있으며, 입출력 순서가 보장된다.
그렇다면, ios::sync_with_stdio(false)는 말 그대로 동기화를 하지 않는다는 의미이다. 이럴 경우, C++ 표준 스트림들은 더 이상 C 스트림 버퍼를 이용하지 않고 자신들의 버퍼를 이용하게 된다. 이제 C 스트림과 C++ 스트림이 따로 논다는 의미이다.
C 스트림과 C++ 스트림이 따로 놀게 되니, C++ 입출력 연산과 C 입출력 연산을 혼합해서 사용할 경우 입출력의 순서가 보장되지 않는다. C 스트림이 먼저 처리될지, C++ 스트림이 먼저 처리될지 모르기 때문이다.
이 때문에 ios::sync_with_stdio(false)를 사용할 경우, (cout, cin) 과 (printf, scanf)를 혼합하여 사용하지 말고 아싸리 한쪽만 사용하라는 것이다.
결론적으로는 printf와 scanf 쓰자
근데 ios::sync_with_stdio(false) 얘를 써도 printf랑 scanf가 더 빠르다.
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
코드포스 관련 게시글에 어떤 유저가 입출력 형식을 다르게 했을 때 수행 시간을 측정한 것이 있는데, 그래 그냥 printf랑 scanf가 넘사벽이다.
아 cout이랑 cin 다시 쓰나 봐라 진짜
로그 구하기
별건 아니고.. 를 만족하는 k값을 구하는 for loop이 신박해서 사실 뭐 없는데 내가 코딩 쓸액희라 이런것도 신기해함 잊지 말자는 의미로.. 가져와봄
for (log = 1; (1 << log) <= V; log++);
log--;이번 문제에서 메모리 초과를 피하기 위해서는 나는 처음에 피하지 못했지 조상님들을 저장해 놓을 배열의 크기를 개만큼 잘 지정해야 한다. 저 위의 for loop을 이용한다면 두번째 줄의 log--만 없애면 된다.
문제풀이
그래프의 edge들을 다 받은 후, parent node를 알기 위해 BFS를 돌렸다. 시간 초과를 막기 위해 LCA binary lifting 기법을 이용하였다.
#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
using namespace std;
void BFS(vector<int> *node, int *parent, int *depth, int V, int start)
{
queue<int> q;
bool check[V + 1] = {false};
check[start] = true;
parent[start] = 0;
depth[start] = 0;
q.push(start);
while (!q.empty())
{
int now = q.front();
q.pop();
for (int i = 0; i < node[now].size(); i++)
{
int next = node[now][i];
if (!check[next])
{
parent[next] = now;
depth[next] = depth[now] + 1;
check[next] = true;
q.push(next);
}
}
}
}
void makeGraph(vector<int> *node, int *parent, int *depth, int V)
{
int E = V - 1;
while (E--)
{
int u, v;
scanf("%d %d", &u, &v);
node[u].push_back(v);
node[v].push_back(u);
}
BFS(node, parent, depth, V, 1);
}
void makeLCA(int *parent, int *depth, vector<vector<int>> &LCA, int V)
{
int log;
for (log = 1; (1 << log) <= V; log++)
;
for (int i = 0; i <= V; i++)
{
vector<int> tmp(log, 0);
LCA[i] = tmp;
}
for (int i = 1; i <= V; i++)
LCA[i][0] = parent[i];
for (int j = 1; (1 << j) < V; j++)
for (int i = 1; i <= V; i++)
if (LCA[i][j - 1] != 0)
LCA[i][j] = LCA[LCA[i][j - 1]][j - 1];
}
int findLCA(vector<vector<int>> &LCA, int *depth, int u, int v)
{
if (depth[u] < depth[v])
swap(u, v);
// depth[u] > depth[v]
int log = 1;
for (log = 1; (1 << log) <= depth[u]; log++)
{
}
log--;
for (int i = log; i >= 0; i--)
if (depth[u] - (1 << i) >= depth[v])
u = LCA[u][i];
if (u == v)
return u;
else
{
for (int i = log; i >= 0; i--)
if (LCA[u][i] != 0 && LCA[u][i] != LCA[v][i])
{
u = LCA[u][i];
v = LCA[v][i];
}
return LCA[u][0];
}
}
int main()
{
int N;
scanf("%d", &N);
vector<int> node[N + 1];
int parent[N + 1];
int depth[N + 1];
makeGraph(node, parent, depth, N);
vector<vector<int>> LCA(N + 1);
makeLCA(parent, depth, LCA, N);
int M;
scanf("%d", &M);
while (M--)
{
int u, v;
scanf("%d %d", &u, &v);
printf("%d\n", findLCA(LCA, depth, u, v));
}
}참고한 사이트
https://www.acmicpc.net/board/view/8074
http://codeforces.com/blog/entry/44543
https://www.acmicpc.net/board/view/1294
https://modoocode.com/281
