알고리즘 문제풀이 TIP / ios::sync_with_stdio, cin.tie

알고리즘 문제는 대부분 시간 제한이 있습니다.

 

온라인 저지 시스템에서 시간 제한은 특정한 조건(최악의 수)에서 특정한 시간(제한 시간)내로 알고리즘이 동작하는 가를 판단하기 위해 존재합니다.

사용하는 언어에 따라서도 시간이 차이가 납니다.

(해당 포스트는 c++을 기준으로 작성되었습니다.)

 

시간복잡도에 관한 아티클은 매우 많으니 해당 글을 참고해주시면 감사하겠습니다.

 

추천:

https://stackoverflow.com/questions/11032015/how-can-i-find-the-time-complexity-of-an-algorithm

How can I find the time complexity of an algorithm?

 

---

ios::sync_with_stdio(bool sync)

다시 원래 이야기로 돌아와서,

일반적으로 알고리즘 문제를 풀 때 제한시간을 준수하려하고, 이때 입출력을 근소하게나마 빠르게 하기 위해 우리는 buffer를 수정하는 방식을 사용합니다.

 

사실 Performance자체에 직접적인 영향을 주진 않지만, execution time을 빠르게 해주는 것은 일종의 side effect입니다.

따라서 optimization처럼 보이긴 하지만 실질적으로 모든 프로그램을 해당 방식을 이용해서 짜는 것은 좋지 않습니다.

 

핵심만 설명하자면 ios:sync_with_stdio(false)는 C와 C++ standard streams의 동기화를 disable시키는 역할을 합니다.

따라서, C++ stream은 독립된 buffer를 갖는 것 같은 효과를 얻게 됩니다.

즉, 대응하는 C stream buffer를 사용할 수 있습니다

 

이때 동기화된 C++ stream은 thread-safe하다는 점은 인지하고 있어야합니다.

또한 각 thread에서 출력은 할 수 있으나, race condition이 발생하지 않습니다.

 

(buffer : 입출력을 위한 임시 저장 공간)

input&output icon from : stock.adobe.com/

---

cin.tie()

일반적으로 cin.tie(NULL)로 많이들 쓰곤 하는 문구입니다.

 

말그대로 cin을 cout으로 부터 untie시키는 것을 의미합니다.

Tied streams은 다른 stream에 I/O operation 전에 자동으로 flush시키는 것을 보장합니다.

(flush : buffer로부터 permanent memory로 이동시키는 것 / 더 쉽게 말하면 화면에 보이게 하는 것?)

 

기본값으로 cin은 cout에 tied(묶여)되어있는데 이는 sensibile user interaction을 위함입니다.

 

따라서 cin을 cout으로 부터 untie했다면, cin 이전에 cout을 통해 무언가 Flush(display)하고 싶다면 cout을 매번 manually flush해줘야 합니다.

 

---

결론 및 코드

1. 동기화를 끊었을 경우 buffer의 수가 줄어들고 실행 속도 자체는 향상됩니다.

2. cin, cout 의 실행 속도는 scanf, printf에 비해 현저히 느립니다.

3. std::endl 보다 '\n'이 훨씬 빠릅니다

4. 위의 예시들은 single thread에서만 활용하는 것이 좋습니다

5. 위의 예시들은 알고리즘 문제를 풀 경우에 고려할 대상이 됩니다. 실제 프로그램을 짜실 때에는 신중히 생각하세요!

 

ios::sync_with_stdio(false);
cin.tie(NULL);