[BaekJoon/백준] 3단계 "for문"

이번엔 3단계 "for문" 에 대해서 풀어보았다.

이에 해당하는 문제는 2739번, 10950번, 8393번, 15552번, 2741번, 2742번, 11021번, 11022번, 2438번, 2439번, 10871번으로 총 11문제였다.

 

이 중 알고 넘어가면 좋다고 생각되는 문제는 15552번, "빠른 A+B" 이다. 해당 문제는 실행 속도가 매우 중요한 문제이다.

문제의 내용이 너무 주옥같고, 중요하게 알고 가야 할 내용이라 정리해보려고한다.

 

해당 문제는 단순히 A와 B의 입력을 받아서, A+B의 값을 출력하면 되는 문제지만, 프로그램의 실행 속도에 대한 제약이 크다.

따라서 일반적인 풀이로는 풀 수 없을지도 모른다. 해당 문제를 약간 인용하자면,

 

-백준 15552번-

" C++을 사용하고 있고 cin/cout을 사용하고자 한다면, cin.tie(NULL)과 sync_with_stdio(false)를 둘 다 적용해 주고, endl 대신 개행문자(\n)를 쓰자. 단, 이렇게 하면 더 이상 scanf/printf/puts/getchar/putchar 등 C의 입출력 방식을 사용하면 안 된다.

 

Java를 사용하고 있다면, Scanner와 System.out.println 대신 BufferedReader와 BufferedWriter를 사용할 수 있다. BufferedWriter.flush는 맨 마지막에 한 번만 하면 된다. "

 

이렇게, 알고 가면 정말 좋을 중요한 내용을 설명해주면서 밥을 떠먹여준다. 문제에서 알려주는데로만 코딩한다면 문제는 간단히 끝나지만, 왜 그런지에 대한 부연설명을 좀 적어보려고 한다. ( 내가 풀이 가능한 언어는 C/C++/JAVA인데, C는 일반적인 printf, scanf만 써도 속도가빠르므로 C++과 JAVA에 대해서만 다루려고 한다 )

 

▶︎ C++

∙ sync_with_stdio(false)

C 표준 stream과 C++ 표준 stream의 동기화를 비활성화합니다. 

기본적으로 모든 표준 stream들은 동기화가 되어 있어서, C와 C++의 입출력방식을 자유롭게 병행할 수 있습니다.

C++에서 sync_with_stdio(false)를 통해 동기화를 끊게되면 C++ 스트림들은 독립적인 버퍼를 갖게 되고, C 입출력방식을 병행하여 쓸 수 없게 됩니다. 하지만 버퍼의 수가 줄어들기 때문에 실행 속도는 향상되는 효과가 있습니다.

 

∙ cin.tie(NULL)

기본적으로 cin과 cout은 tie 되어 있는데, 프로그램이 사용자에게 입력을 요청하기 전에 출력이 플러시(flush, 화면에 보여진다라고 생각) 되는 상태입니다.

cout << "enter key : ";
cin >> n;

이런 코드가 있을 경우, tie 상태에선 입력을 받기 전에 "enter key : " 가 출력이 되어 있지만 untie 일 경우 수동적으로 flush를 시켜주지 않는 한 출력이 이루어지지 않습니다. 디폴트는 tie로, 코드 내에 cin이 실행되기 전에 출력스트림이 flush되나, untie를 해줌으로써 이를 설정 해제하는것이죠.

 

∙ endl 대신 "\n"

endl은 개행작업과 더불어 출력버퍼를 비우는 작업까지 진행하기 때문에, "\n"를 사용하는 것이 속도측에서 빠릅니다.

 

 

▶︎ JAVA

BufferReader와 BufferWriter는 버퍼를 사용하기 때문에 속도가 빠릅니다.

 

버퍼를 사용하지 않는 입력은 키보드를 누르는 즉시 프로그램에게 키보드의 입력이 넘겨지는데

버퍼를 사용하는 경우, 키보드를 누를 때 마다 키보드의 입력이 버퍼라는 임시 공간에 저장되었다가, 버퍼가 가득 차거나 개행문자가 나타나면 버퍼의 내용을 한번에 프로그램에게 전송하는 방식입니다.

 

출력 역시 BufferWriter.write()를 호출한다고 해서 한번에 전송이 되는 것이 아니라, 버퍼라는 임시공간에 저장해놓았다가 flush() 함수를 호출하여 한번에 전송하는 방식입니다.

 

ps. BufferWriter의 write함수는 System.out.println 함수처럼 자동 개행처리가 되지 않기 때문에 BufferedWriter.newLine()를 활용하면 개행처리가 가능하나, 이건 "\n"에 비해 속도가 느리다고 하니 "\n" 을 활용해 개행처리를 하는 걸 권장합니다.

(참고로 스캐너도 버퍼가 존재하나 이 크기는 1024 chars로, BufferedReader의 8192 chars 버퍼 사이즈에 비하면 매우 작습니다. 이 외에 다른 성능들에 대해서도 BufferedReader 가 Scanner보다 우세합니다.)