[알고리즘/백준] 15552번 :: 빠른 A+B (C++)

문제 ✍🏻 :: [15552번] 빠른 A+B

(초록색 글자 클릭 시 문제로 이동)

시간 초과 나지 않게, 테스트케이스 개수에 맞춰 빠르게 A+B출력하게

알고리즘 (접근방법) 💻

기존 A+B 문제에서 성능에 더 중심을 둔 문제이다.

문제에서 준 힌트를 무시하고 한번 해보았다.

💡1번째 시도💡

앞서 푼 문제와 같은 형식으로 풀면 된다.

테스트 케이스 t를 입력 받는다.
t만큼 반복하여 a와 b를 입력받고 그 합을 출력하는 for문을 작성한다.

#include <iostream>
using namespace std;

int main()
{
	int t, i, a, b;
	cin >> t;

	for (i = 0; i < t; i++) {
		cin >> a >> b;
		cout << a + b << "\n";
	}
	
	return 0;
}

⬇⬇ 이대로 작성하면 결과는 다음과 같다 ⬇⬇

🚨시간초과를 막기 위해서는?🚨

(여기서cin.tie(NULL)과 sync_with_stdio(false)를 사용하는 이유 등 자세한 설명은 Stranger's LAB님의 티스토리에서 설명을 잘 해놔서, 이 게시물에 적힌 글을 요약하여 적었다.

백준 사이트에는 다음과 같이 나와있다.

cin.tie(NULL)과 sync_with_stdio(false)를 둘 다 적용해 주고, endl 대신 \n를 쓰자

C언어, C++의 경우 scanf(), printf()를 사용한다. 이 경우 입출력 자체가 매우 빨라 쉽게 통과한다. 그러나 C++의 standard 입출력 cin, cout을 사용하면 시간 초과가 난다. C++ 뿐 아니라 JAVA, Python도 마찬가지이다. (Python의 경우 원래 극도로 느리다.)

이 문제를 푸는 첫번째 방법은 C표준 입출력 stdio.h를 쓰는 것이다.
stdio.h로 풀면 간단하게 해결된다.
나는 iostream으로 풀어보고자 한다.

iostream으로 cin, cout만 쓰면 💡1번째 시도💡와 같이 시간초과가 뜬다.

stdio.h와 다르게 왜 느릴까?!

🔒1. 이유🔒

• C++은 C의 표준 스트림이 동기화되어있다. 즉, 동일한 버퍼를 공유한다!
• 동기화 => 성능⬇ / 합리적, 안전도 ⬆
  ex1. std::cin =동기화=> stdin
  ex2. std::out =동기화=> stdout

🔑2. 해결🔑 : "동기화를 끊어주면 된다!"

• 알고리즘 문제 풀이는 두 동기화를 끊어주어도 OK

• 동기화를 끊으면 => C++표준 스트림이 독립적으로 IO 버퍼링

• 이를 위해 ios_base에 있는 sync_with_stdio()를 활용! (파라미터는 false를 해줄 때 동기화 해제)

• 단, 동기화를 해제 했기때문에 C와 C++ 스타일 중 하나를 선택해서 써야 함!

cin.tie(NULL);

• 메인 함수 첫 줄에 선언
• cin과 cout 묶음을 풀어주는 구문
• cin으로 데이터를 읽을 때 출력 버퍼에 있는 내용을 비우는데 비우지 않고 먼저 입력

ios_base::sync_with_stdio(false);

• C와 C++버퍼 분리 역할

💡2번째 시도 : 동기화 해제하여 작성하기💡

#include <iostream>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int t, i, a, b;
	cin >> t;

	for (i = 0; i < t; i++) {
		cin >> a >> b;
		cout << a + b << "\n";
	}

	return 0;
}

이렇게 하면 성공!!

회고 🤔

cin.tie(NULL);와 ios_base::sync_with_stdio(false);를 몰라서 이 개념을 이해하기 위해 여러 참고 사이트를 이용했다. 그래서 이해하는데 시간이 오래걸렸다. 가장 이해가 잘 되었던 두 사이트를 아래 Reference에 첨부했다.
내가 모르는 개념을 계속 알아가고 싶다. 주춤하기 보다는 계속 채워가고 싶은 마음이다.

Reference

• https://st-lab.tistory.com/232
• https://travelerfootprint.tistory.com/121