[코딩테스트 4일차] BAEKJOON 2741번 : N찍기

[BAEKJOON 2741번 : N 찍기]

[문제]

---

 

[고찰]

문제를 보면, 단순히 for문을 사용하면 될 것 같은 문제입니다.

물론 주요 알고리즘은 for문을 사용하는 것이 맞습니다.

 

하지만 저는 문제를 틀리고 말았죠. 그 이유는 시간 초과 때문입니다.

 

시간이 초과된 이유에 대해서 검색을 하다보니, cin과 cout, endl의 수행시간에 관련된 글을 보게 되었습니다.

cin과 cout 또한 scanf와 printf를 비교했을 때 차이가 꽤 컸지만,

개행 문자를 사용하여 개행할 때와 endl를 사용하여 개행할 때의 차이가 더욱 컸습니다.

 

이 개념에 대해 확실히 정립하고자 이렇게 정리합니다.

 

---

 

[개념]

아래의 이미지를 보면 알 수 있듯이, scanf를 사용하는 경우와 std::cin을 사용하는 경우의 수행 시간 차이는 2배 이상이였습니다.

출처 : https://algospot.com/forum/read/2496/

 

C ++에서 scanf와 std::cin의 수행 시간 차이가 나는 이유는 정리하면 아래와 같습니다.

• 입출력 버퍼링
  
  • C 스타일 입출력 함수인 scanf는 기본적으로 버퍼링을 사용하지 않으며, 입력을 받을  때 직접적으로 표준 입력에서 읽어옵니다.
  • C++의 std::cin은 C++의 스트림 기반 입출력으로, 입력을 처리할 때 내부적으로 여러 가지 추가적인 처리를 수행합니다.
• C++과 C의 동기화
  
  • 기본적으로 std::cin과 C 스타일의 printf / scanf는 동기화되어 있습니다. 즉, C++의 입출력과 C의 입출력 함수가 함께 사용할 수 있도록 설정되어 있습니다. 이 동기화로 인해 추가적인 오버헤드가 발생할 수 있습니다.
• 형 변환
  • scanf는 입력 데이터를 원하는 형식으로 직접 읽어오기 때문에, 형 변환에 필요한 시간이 상대적으로 적습니다.
  • std::cin과 같은 C++의 스트림 입력 방식은 입력을 처리할 때 형 변환을 위한 추가적인 오버헤드가 발생할 수 있습니다.
• 사용자 정의 및 에러 처리
  • std::cin은 입력 오류를 처리할 수 있는 다양한 메커니즘을 제공하지만, 이로 인해 추가적인 시간 소모가 발생할 수 있습니다.
  • scanf는 이에 비해 상대적으로 간단한 에러 처리를 제공합니다.

---

 

개행을 위한 'std::endl'과 '￦n'에서도 수행 시간 차이가 많이 나게 됩니다.

 

std::endl은 출력 스트림에 개행 문자를 추가하는 것뿐만 아니라, 출력 버퍼를 플러시(flush)합니다.

즉, 현재까지 출력된 내용을 즉시 화면에 표시하도록 강제합니다. 이 플러시 작업이 I/O 작업을 수행하는 데 추가적인 시간을 소모하게 합니다.

 

그에 반해, 개행 문자 ￦n은 단순히 출력 스트림에 개행을 추가하는 역할만 합니다.

버퍼를 플러시하지 않으므로, 출력 내용이 화면에 즉시 나타나지 않고, 나중에 버퍼가 가득 차거나 명시적으로 플러시될 때까지 기다리게 됩니다.

 

이로 인해 성능상 개행 문자 ￦n이 std::endl보다 더 빠른 것입니다.

 

※ 버퍼(Buffer)와 플러시(Flush)

버퍼는 데이터 전송을 효율적으로 처리하기 위해 임시로 데이터를 저장하는 메모리 영역입니다.
I/O 작업에서 버퍼는 아래의 역할을 합니다.

• 속도 향상
  • I/O 작업은 상대적으로 느린 작업입니다. 예를 들어, 디스크에 데이터를 쓰거나 화면에 출력을 하는 것은 CPU 작업보다 느립니다. 버퍼를 사용하면 여러 데이터를 한 번에 처리하여 성능을 향상시킬 수 있습니다.
• 데이터 집합
  • 버퍼는 작은 단위의 데이터를 모아서 한 번에 전송함으로써 I/O 작업의 횟수를 줄입니다. 예를 들어, 여러 개의 출력 요청을 버퍼에 저장한 후, 버퍼가 가득 차거나 명시적으로 플러시될 때 한 번에 처리합니다.
• 비동기 처리
  • 버퍼를 사용하면 프로그램이 I/O 작업을 수행하는 동안 CPU가 다른 작업을 계속 수행할 수 있습니다. 이를 통해 프로그램의 전체적인 효율성을 높이는데 기여할 수 있습니다.

플러시는 버퍼에 저장된 데이터를 즉시 출력 장치로 보내는 작업을 의미합니다.

 

---

 

[정리]

그렇다면 해당 문제를 풀기 위해, 수행 시간을 줄이려면 어떤 방법을 사용해야 하냐에 대한 답변은 아래의 방법들이 존재합니다.

 

[syns_with_studio]

std::ios_base::syns_with_stdio(false);
// std::ios_base::syns_with_stdio(0);과 동일

 

해당 구문은 C++과 C의 동기화를 해제하게 하는 구문입니다.

 

C++과 C의 동기화를 해제하게 되면, C++만의 독립적인 버퍼를 생성하고 C의 버퍼들과는 병행하여 사용할 수 없게 됩니다.

대신 속도가 높아지게 됩니다.

 

[cin.tie]

std::cin.tie(nullptr);
// std::cin.tie(0); 과 동일합니다.

 

cin.tie()는 C++에서 스트림의 동기화와 관련된 함수로, 주로 입출력 성능을 개선하기 위해 사용됩니다.

 

C++의 표준 라이브러리에서 std::cin과 std::cout은 기본적으로 서로 동기화되어 있습니다.

cin.tie()를 통해 동기화를 해제하여 입력과 출력을 독립적으로 처리할 수 있게 되어, 성능이 향상될 수 있습니다.

 

std::cin과 std::cout이 동기화되어 있다는 말은, std::cin으로 입력을 받기 위해 기다리는 동안 std::cout이 선행되어 있을 때, std::cout을 통해 출력한 내용이 먼저 화면에 나타나야 한다는 출력 순서 보장을 의미합니다.

std:cout << "Enter a number : ";

int n;
std::cin >> n;

 

예를 들면, 위의 코드에서 "Enter a number : "이 먼저 출력되어야지 n을 입력받을 수 있다는 뜻입니다.

 

[std::endl -> "￦n"]

위의 [개념]에서 보다시피, std::endl은 ￦n보다 수행 시간이 더 소요될 수 있기에 이 문제는 개행  문자를 사용하여 풀면 되겠습니다.

 

---

 

[Solution : 개행 문자 사용]

#include <iostream>
using namespace std;
 
// BAEKJOON 소요 시간 8ms
int main()
{
	int n;

	cin >> n;

	for (int i = 1; i <= n; ++i)
	{
		cout << i << "\n";
	}

	return 0;
}

 

 

[Solution : std::ios_base::sync_with_stdio(false) + cin.tie() 사용]

#include <iostream>
using namespace std;
 
// BAEKJOON 소요 시간 4ms
int main()
{
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);  

	int n;

	cin >> n;

	for (int i = 1; i <= n; ++i)
	{
		cout << i << "\n";
	}

	return 0;
}

 

 

[Solution : std::ios_base::sync_with_stdio(false) 사용]

#include <iostream>
using namespace std;
 
// BAEKJOON 소요 시간 8ms
int main()
{
	std::ios_base::sync_with_stdio(false);

	int n;

	cin >> n;

	for (int i = 1; i <= n; ++i)
	{
		cout << i << "\n";
	}

	return 0;
}

 

 

[Solution : printf, scanf 사용]

#include <iostream>
using namespace std;

 // BEAKJOON 소요시간 8ms
int main() { 
	int n;
	scanf_s("%d", &n);

	for (int i = 1; i <= n; i++) {
		printf("%d\n", i);
	}
}