한 줄 요약: 알고리즘 풀 땐 "\n"이 답이다. printf가 더 빠르니 잘 활용하자.
백준 11659번 ‘구간 합 구하기 4’ 문제를 풀다가 어처구니없는 경험을 했다. 로직은 완벽한데 계속 ‘시간 초과(TLE)‘가 뜨는 상황. 원인은 알고리즘이 아니라 고작 출력 한 줄에 있었다.
1. 현상
과 이 각각 10만이라 매번 합을 구하면 당연히 터진다. 그래서 O(1)만에 구간 합을 구하는 누적 합(Prefix Sum) 알고리즘을 썼다. 그런데도 시간 초과가 났다.
혹시나 해서 딱 한 부분을 바꿨더니 바로 통과됐다.
C++
// ❌ 시간 초과 코드
cout << Sum[end] - Sum[start-1] << endl;
// ✅ 통과 코드
cout << Sum[end] - Sum[start-1] << "\n";
2. 왜 이런 차이가 날까?
결론부터 말하면 endl이 단순히 줄만 바꾸는 게 아니기 때문이다.
-
std::endl: 줄바꿈(\n)을 하고 나서 출력 버퍼를 강제로 비우는(flush) 작업까지 수행한다. -
"\n": 줄만 바꾸고 데이터는 버퍼에 쌓아둔다.
컴퓨터한테 출력(I/O)은 아주 비싼 작업이다. 10만 번 출력하면서 매번 “지금 당장 버퍼 비우고 화면에 뿌려!”라고 명령하는 endl은 병목 현상을 일으킬 수밖에 없다. 반면 "\n"은 버퍼에 모아뒀다가 한꺼번에 처리하니 훨씬 빠르다.
3. 교훈
출력이 많은 알고리즘 문제에서 endl은 독이다. 특히 이번처럼 쿼리 개수()가 많은 문제는 더더욱.
앞으로 C++로 문제 풀 때는 무조건 다음 규칙을 지켜야겠다.
-
endl대신"\n"쓰기. -
ios_base::sync_with_stdio(false); cin.tie(NULL);설정으로 입출력 가속하기.
알고리즘이 맞는데도 터진다면 로직을 의심하기 전에 출력 방식부터 체크하자.