티스토리 뷰
백준 1717번 집합의 표현 에 Union-Find 알고리즘을 적용하여 문제를 풀었는데 같이 푼 다른 사람들은 다 맞는데 나만 시간초과가 났다.
같은 알고리즘의 같은 방식의 예외처리를 한 사람도 있었는데 도대체 왜 시간초과가 났을까?
친구에게 조언을 구해보니 문제는 cin과 cout에 있었다.
나는 c++을 사용할 때 입출력 함수로 cin과 cout을 사용하는데, cin과 cout은 printf와 scanf에 비해 어마무시하게 느리다는 사실을 듣게되었다.
왜 속도가 차이가 날까?
cstdio의 prinft, scanf는 데이터의 타입을 프로그래머가 지정해줘야해서 오류가 발생할 수는 있지만 더욱 빠른 속도를 내고
iostream의 cout, cin은 입출력 데이터의 타입을 프로그래머가 지정해주지 않아도 타입에 맞춰서 입출력이 진행이 되지만 그 때문에 >>, << 연산자의 작업에서 오버헤드가 발생해 속도차이가 나는 것이었다.
하지만 그것때문에 알고리즘 문제를 풀 때 시간초과가 날 만큼 차이가 나는 것은 아닌듯했다.
더 중요한 이유는 iostream이 cstdio의 버퍼 시스템을 사용한다고 한다.
cout, cin은 cstdio 버퍼와 자체 시간을 동기화하므로 cout과 printf, cin과 scanf를 모두 호출 할 수 있게 한다는 것이었다.
그렇다면 cout과 cin의 속도문제를 해결하고 사용하고 싶다면 어떻게 해야할까?
버퍼 시스템을 같이 사용해서 생기는 문제므로 동기화를 끊어주면 되는 것이었다.
동기화를 끊어 주는 함수는 아래와 같다.
ios::sync_with_stdio(false)
실제로 메인 함수 맨 위에 해당 함수를 호출하고 백준저지에 문제를 제출해보니 처리속도가 어마무시하게 빨라지는 것을 확인하였다. (어떤 문제 기준으로 2배보다 조금 더 빨랐다.)
하지만 해당 함수를 사용하게되면 버퍼 시스템을 끊었기 때문에 더이상 cstdio의 함수들인 printf, scanf 그 외에도 getchar 등등의 함수들을 사용할 수 없게된다.
따라서 알고리즘 문제에서 처리해야할 데이터가 많다면 printf와 scanf를 권장한다고 한다.
번외로 endl같은 경우도 \n에 비해 굉장히 느린데 endl은 개행뿐만 아니라 버퍼를 한 번 비우는 연산을 수행한다고 한다.