알고리즘 시간 줄이기 (입출력 시간 줄이기 : 버퍼 비동기화 & io untied)

저번 정렬 알고리즘 포스팅에서 살짝 언급했던 입출력 시간 줄이기를 해보려고 한다. 

 

백준 2751 문제를 풀기 위해 <algorithm> 헤더파일에 있는 sort() 함수를 사용하려 했는데, sort() 함수의 복잡도가 O(nlogn) 인데도 불구하고 시간초과가 났었다. merge sorting 알고리즘도 같은 O(nlogn) 복잡도를 가지지만 시간초과가 나지 않는 것을 보면 sort() 함수 문제가 아니라 다른 부분에서 시간을 많이 잡아 먹는 다는 뜻인 것 같았고, 그래서 입출력에서 시간을 줄이는 방법을 찾아보기로 하면서 해당 부분들을 공부했다. 

 

 

흔히 쓰는 방법 3가지가 있다고 한다. 그냥 코드만 붙여주면 되는 단순한 작업이지만 원리를 이해해서 능동적으로 활용하고 싶었다.

 

•  c++ 입출력 버퍼와 c 입출력 버퍼를 비동기화 시키기
• cout 과 cin 간의 연결 끊기 
• 줄바꿈 함수 endl 대신 c 스타일의 '\n' 사용하기

 

 

1.  c++, c 의 버퍼 비동기화

 

ios_base::sync_with_stdio(false);

이 코드를 main 함수 안에 넣으면 되는데 원리를 이해해 보자.

 

 

cpp는 입출력 작업을 수행할 떄 iostream이라는 헤더파일을 주로 사용한다. 이 헤더파일은 사용자들의 편의성을 제공하기 위해서 cpp 입출력 문법과 c 의 입출력 문법을 같이 제공해 준다. 그래서 이 헤더파일을 사용하면 사용자들은 하나의 프로그램 환경에서 cpp 의 입출력 문법과 c 의 입출력 문법을 섞어서 쓸 수 있다.

 

이 서비스를 원활히 하기 위해 iostream 에서는 cpp의 버퍼와 c의 버퍼를 동기화 시킨다. 그래서 cpp 입출력 문법만 쓰더라도 c의 버퍼를 같이 쓰기 때문에 입출력을 수행하는데에 시간이 많이 든다. 그래서 입출력의 시간을 줄이기 위해서 cpp 버퍼와 c 버퍼를 비동기화 시킬 필요가 있는데 그게 위의 코드이다. 

 

비동기화 시킬 시 장점과 단점이 있다. 

 

장점: 입출력 시간이 줄어든다. 

단점: cpp 입출력 문법과 c의 입출력 문법을 프로그램 내에서 같이 사용하면 원하는 순서로 입출력 되지 않을 수 있다. 또한 멀티 스레드를 사용할 경우 입출력 순서가 예상한 것과 다르게 나타날 확룰이 높다. 

 

버퍼 간 동기화가 되지 않으니 cpp와 c의 입출력을 같이 쓰면 cpp 입출력을 먼저 작성하더라도 c의 입출력 구문이 먼저 실행될 수 있다는 것이다. 멀티스레드에서도 같은 개념으로 이해하면 된다. 

백준 문제처럼 주로 싱글 스레드를 사용하는 경우에는 해당 구문이 입출력 시간을 줄여주므로 오히려 이득이다. 내가 작성하는 프로그램 상황이 어떤지를 파악하고 적절히 이용하는 것이 좋겠다. 

 

 

2.  cout 과 cin untied 시키기

 

cin.tie(NULL);

이 코드도 main 함수 안에 넣어주면 되는데 원리를 이해해 보자.

 

 

iostream에서는 default로 cin 과 cout 이 묶여있다. (= tied 상태이다.) cin과 cout이 묶여있으면 cout이 실행되고 그 다음 cin이 실행될 것을 예상해서 자동으로 버퍼를 비워준다. 

 

int a, b;

for(int i=0; i<5; i++){
	cin >> a >> b;
    cout << a+b << endl;
}

 

위의 코드처럼 a와 b를 입력받으면 a+b를 출력하는 프로그램이 있고 입력을 5번 받는 프로그램이 있다고 해보자. 보통의 프로그램은 a와 b를 입력 받으면 바로 console에 a+b를 출력한다. 즉 console에 찍히는 형태가 

3 3

6

5 7

12

 

이런식으로 찍힌다는 것이다. 자 그럼 여기서 버퍼의 상황을 알아보면 3 3이 버퍼에 들어오고 6을 출력하고 버퍼를 비운다. 즉 cout 이 실행될 때마다 버퍼를 비우는 작업을 수행한다는 것이다. 반복문 횟수가 5번이라서 크게 안느껴지지만 숫자가 커지면 버퍼를 쓸데없이 비우는 행위는 프로그램 시간 증가 요인에 크게 적용된다. 이를 막기 위해서는 cout 뒤에 cin 이 오지 않게 해야하는데 프로그램을 짜다보면 그렇지 못한 경우가 많다. 그래서 cin과 cout을 untied 시켜주는 것이다. 

 

그러면 코드의 순서대로 입출력이 이루어지는 것이 아니라 입력을 우선적으로 다 받고 출력이 진행된다. console에 찍히는 형태를 보면 

3 3

5 7

6 4....

6

12

10

이렇게 찍힐 것이다. 코드 상에서 cin 다음에 cout이 있다고 해도 둘의 관계는 untied 이니까 cin을 우선적으로 진행하고 cout이 진행된다. 즉 버퍼를 효율적으로 사용한다는 것이고 버퍼를 비우는 시간을 줄이니까 입출력 시간이 줄어드게 된다. 

 

* 근데 cin.tie(NULL) 뿐만 아니라 ios_base::sync_with_stdio(false) 도 같이 써주면 저렇게 실행된다. 

 

 

 

3.  endl 대신 '\n' 사용하기

 

이건 간단하다. 둘 다 개행(줄바꿈)을 하는 것인데 endl은 줄바꿈을 하면서 버퍼를 비우는 작업을 하기 때문에 단순 개행을 하는 '\n' 보다 시간이 오래 걸린다. 만약 반복문으로 개행을 할 소요가 많아지면 endl 보단 '\n'을 쓰는 것이 출력의 시간을 줄이는 데에 도움이 된다. 

 

 

 

 

========================================================================================================================================================================================

 

 

결론

백준 2751 번 문제를 풀면서 sort() 함수의 복잡도가 크기 않음에도 시간초과가 생기는 상황을 파헤치다가 입출력 시간을 줄이는 법, 버퍼를 효율적으로 사용하는 법에 대해서 학습할 수 있었다. 단순히 두 문장을 추가하면 되는 간단한 작업이지만 내가 짜는 프로그램의 상황에 맞지 않는 상황에서 사용할 시 오히려 독이 될 수 있다는 점을 인지하면서 적절한 상황에 예외는 없지를 생각하면서 (싱글 스레드 프로그램인지, 입출력 순서는 상관없는지 등) 사용하는 것이 좋을 듯하다. 그리고 항상 입출력을 하면서 버퍼의 상황을 생각하는 습관을 들이면 예상하지 못한 console 화면이 나와도 쉽게 해결할 수 있을 것 같다.