C,C++] cin/cout, scanf/printf

알고리즘 문제를 풀다 보면, Time Limit(시간 제한)에 대해서 신경 쓰지 않을 수가 없다.

제한된 메모리에서 최대한 빠른 시간 내에 정확한 답을 찾는 것이 좋은 알고리즘이고,

그렇지 못한 알고리즘은 TLE나 시간 초과 등을 이유로 답을 처리해주지 않는다.

입출력이 수천 번에 머무르면 시간 초과가 발생하면

거의 대부분 알고리즘에 문제가 있지만,

입출력이 수십만 개, 수백만 번에 이르면 이야기가 좀 다르다.

한 예를 들어서 설명을 해볼까 한다.

https://www.acmicpc.net/problem/11004

백준 사이트의 11004번 : K번째 수라는 문제다.

N개의 숫자들을 입력 받고 오름차순 정렬을 했을 때,

K번째의 수를 출력하는 것이다.

문제는 되게 간단하다.

입력 값이 5백만개에 이르며 숫자 중복도 가능하고,

정렬별 최악의 케이스도 입력될 수 있다는 걸 감안하면

최대한 시간 복잡도가 복잡하지 않은 선에서 정리해야 한다고 생각하게 될 것이다.

정렬을 전부하는 것도 낭비라고 생각해서

Quick Selection을 사용하려고 했는데 난 데 없이 시간 초과가 발생했다.

다른 사람들은 std::sort를 이용해 정렬까지 다 해서 풀었는데...?

믿기지가 않아서 다시 나도 그 방법을 이용했는데 여전히 시간 초과가 발생했다.

cin, cout 문제가 갑자기 생각나서 scanf, printf로 다 돌려버렸더니

std::sort를 써도 시간 제한인 1.5초내에 안착하고,

애당초 짰던 Quick Selection은 그보다 더 빨랐다.

cin, cout이 C library의 stdio buffer와 sync를 맞추려고 하다 보니,

scanf, printf보다 느려지는 현상이 발생할 수 있다고 한다.(링크 참조)

속 편하게 그냥 scanf, printf 바꾸는 것도 좋지만 cin, cout을 그대로 사용하고 싶다면,

std::ios_base::sync_with_stdio(false);

를 삽입해주면 해결할 수 있다.