[백준] 15552번 : 빠른 A+B - [C++]

 

www.acmicpc.net/problem/15552

15552번: 빠른 A+B

 

 

 

 

 

 

 

 

---

• 문제

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

이 부분은 반복문 보다는 입출력에 관한 지식을 필요로 하는 문제다.

C언어 혹은 C++ 의 경우 scanf(), printf()를 사용하면 이 입출력 자체가 매우 빠른 편이라 쉽게 통과하지만, 다른 언어의 경우는 조금 사정이 다르다.

 

C++에서도 사실 Standard 입출력인 cin, cout을 사용하고자 하면 시간초과가 날 것이다.

 

 

그러면 어떻게 해결해야하냐, 좀 더 빠른 입출력을 할 수 있도록 해주어야 하는데, 그 방법은 매우 많으니 차근차근 하나씩 알아보자.

 

 

 

방법 1 : C 표준 입출력 stdio.h 쓰기

 

C언어의 표준 입출력인 scanf()와 printf()를 쓰는 방법이다. 

해당 입출력은 매우 빠른편이라 무난하게 풀릴 것이다. 즉, 아래와 같이 쓰는 것이다.

 

for(int i = 0; i < T; i++) {
	int a, b;
	scanf("%d %d", &a, &b);
	printf("%d\n", a + b);
}

 

 

위 방법으로 해주어도 된다. 아마 가장 간단한 방법일 것이다.

 

 

 

 

 

방법 2 : iostream의 default 설정을 수정하기

 

cin, cout만 쓸 경우에는 시간초과가 난다. 즉, 위 방법에 비해 상대적으로 느린 입출력이라는 것이다.

왜 느릴까?

 

 

 

1) C++와 C 표준 스트림의 동기화 해제

 

ios_base::sync_with_stdio(false);

 

기본적으로 C++에서는 C++와 C의 표준 스트림이 동기화가 되어있다. 무슨 말인가 하면, C++에서 C와 C++ 각각의 스타일로 입출력을 받아도 서로 동기화하여 우리가 입력 혹은 출력하고자 하는 순서대로 결과를 얻을 수 있다. 즉, C와 C++가 동일한 버퍼를 공유한다는 것이다.

(만약 스트림에 대한 개념이 없다면 C와 C++가 입출력을 항시 공유상태라고 이해하는 것이 좀 더 이해가 수월할 것이다.)

 

이러한 동기화는 성능을 저하시키는 원인이 되지만, 두 스트림의 동기화는 우리가 입출력에 있어 C와 C++의 IO(Input-Output)을 혼용하여 쓸 때 매우 합리적이고 스레드로부터 안전하기 때문에 원래는 동기화 상태로 두는 것이 올바르긴 하다.

 

예로들면 입력의 경우 std::cin은 stdin과 동기화 되며, std::cout은 stdout과 동기화가 된다고 보시면 된다.

 

 

다만, 알고리즘 문제 풀이에서는 예외 처리나 멀티스레드 작업을 필요로 하지 않기 때문에 두 동기화를 끊어주어도 무방하다.

 

그럼 동기화를 끊는다는 것은 무엇일까? 앞서 C 스트림과 C++ 스트림이 서로 동기화 되어있다고 했다. 이 동기화를 끊는 다는 것은 C++ 표준 스트림이 독립적으로 IO 버퍼링을 할 수 있다는 것이다. 그렇게 되면 상당히 많은 양의 입출력이 있을 경우 동기화 되어있는 상태에 비해 성능이 많이 좋아진다.

 

즉, 이러한 작업을 위해 ios_base에 있는 sync_with_stdio() 을 활용하여 위 코드처럼 적용시키면 동기화가 해제 된다. 직역을 해보면 stdio와의 싱크(동기화) 메소드인 것을 알 수 있다. 여기에 파라미터로 false을 해주면 동기화가 해제되게 된다.

 

그리고 중요한 점은 동기화를 해제했기 때문에 C와 C++ 스타일 중 하나를 선택해서 써야 한다. 혼용하여 쓰면 안된다.

 

 

 

 

2) 입력과 출력 연결을 끊어주기

 

cin.tie(NULL);	// 또는 cin.tie(nullptr), cin.tie(0) 으로 대체 가능

 

 

우리가 그동안 많은 입출력을 했지만, 잘 모르고 있던 것이 있다.

기본적으로 입력과 출력은 연결되어있다는 것이다.

 

무슨 말인가 하면, 기본적으로 입력 요청이 들어오면 그 전에 출력 작업이 있었을 경우(출력 버퍼에 내용이 있는 경우) 버퍼를 비워(flush) 출력을 하게 된다.

좀 더 쉽게 말하자면 입력 요청을 통해 읽어들이게 될 경우 이 전에 있던 출력 작업들을 콘솔창에 보이도록 버퍼를 비운다는 것이다.

 

예시로 들면 이렇다.

 

[입출력이 묶여있는 경우]

#include <iostream>

using namespace std;

int main(int argc, char const *argv[]) {

	ios_base::sync_with_stdio(false);

	int a;
	for (int i = 0; i < 10; i++) {
		cout << i << "번 째 입력\n";
		cin >> a;
	}
	return 0;
}

 

위와같이 하면 콘솔 창에서는 다음과 같이 결과를 얻을 수 있을 것이다.

 

0번 째 입력
2
1번 째 입력
4
2번 째 입력
25
3번 째 입력
54
4번 째 입력
43
5번 째 입력
23
6번 째 입력
43
7번 째 입력
6336
8번 째 입력
4352
9번 째 입력
24

 

 

 

 

 

하지만, 입력과 출력의 묶음을 풀어준다면? 즉 입력이 들어 올 때 출력이 자동으로 비워주도록 되어있는 tie()를 풀어버린다면?

 

 

[입출력이 분리되어있는 경우]

#include <iostream>

using namespace std;

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int a;
	for (int i = 0; i < 10; i++) {
		cout << i << "번 째 입력\n";
		cin >> a;
	}
	return 0;
}

 

 

다음과 같은 결과를 볼 수 있다.

 

32
24
14
52
25
24
23
1
34
342
0번째 입력
1번째 입력
2번째 입력
3번째 입력
4번째 입력
5번째 입력
6번째 입력
7번째 입력
8번째 입력
9번째 입력

 

 

 

아마 대부분의 경우 두 번째 코드를 실행해보아도 위 결과처럼 안나오고 첫 번째 결과처럼 나올 것이다.

이유는 OS(운영체제)마다의 버퍼링 차이가 있는데, 윈도우의 경우에는 기본적으로 출력 하자마자 버퍼링 없이 콘솔에 출력이 된다. 반대로 리눅스 계열의 경우 줄(개행)을 입력 받을 때 까지 버퍼링이 된다.

 

그래서 실제로 리눅스에서 실행시키면 위와 같은 결과를 얻을 수 있다.

 

 

 

그리고 백준 채점 서버는 우분투다. (참고링크 : www.acmicpc.net/help/judge)

 

 

 

그리고 백준에서는 입력과 출력을 별도로 분리하고 있어 "출력문"만 채점 파일과 동일하면 되기 때문에 굳이 매번 출력 할 필요가 없다.

 

즉, 출력문만 동일하면 되기 때문에 굳이 입력 후에 해당 값을 매 번 출력 해줄 필요가 없다. 즉, 매번 출력을 flushing 시키지 않고 나중에 한 번에 비우도록 하는 것이다.

 

 

 

 

3) endl 대신 "\n" 쓰기

 

C++ 입출력을 배우셨다면 알겠지만, endl은 단순히 개행(줄바꿈)만 해주는 것이 아니라 출력 버퍼를 비우는 역할까지 한다. 즉, 매 줄 바꿈마다 endl 을 쓰면 우리가 2번에서 다루었던 tie을 끊어주는 것의 효과를 볼 수가 없다.

 

바로 위에서 말했듯, 매 번 출력 할 필요가 없으니 자주 출력 버퍼를 비울 이유가 없다.

이 출력 버퍼를 비우는 작업도 상당히 시간을 잡아먹는 작업이기 때문에 마지막 한 번에 출력을 비우는 것이 좋다. (물론 버퍼가 꽉 차면 알아서 비워주니 걱정안하셔도 된다.)

 

 

 

 

즉, 다음과 같이 해주면 된다.

 

ios_base::sync_with_stdio(false);	// C, C++ 동기화 해제
cin.tie(NULL);	// 입력과 출력을 분리

for(int i = 0; i < T; i++) {
	int a, b;
	cin >> a >> b;
	cout << a + b << "\n";	// endl 대신 \n 을 쓰기
}

 

 

 

 

 

 

그 외에 입출력을 직접 구현하는 방법도 있다만.. C, C++에서는 이정도로도 충분하게 빠르다고 생각하기 때문에 별도로 다루지는 않겠다.

 

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

오늘 위 알고리즘에서 설명한 두 가지 방식을 통해 풀이하겠다.

 

 

 

 

1. C 표준 입출력 stdio.h 쓰기

2. iostream의 default 설정을 수정하기

 

 

 

 

---

• 풀이

- 방법 1 : [C 표준 입출력 stdio.h 쓰기]

 

#include <stdio.h>

int main(int argc, char const *argv[]) {

	int T, a, b;

	scanf("%d", &T);
	for(int i = 0; i < T; i++){
		scanf("%d %d", &a, &b);
		printf("%d\n", a + b);
	}

	return 0;
}

 

 

가장 쉬운 방법일 것이다.

 

 

---

- 방법 2 : [iostream의 default 설정을 수정하기]

 

 

 

 

알고리즘 설명에서 했던 두 번째 내용을 적용시킨 방법이다.

 

 

#include <iostream>

using namespace std;

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int T, a, b;

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

	return 0;
}

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 20597227  -  방법 2 : iostream의 default 설정을 수정하기

채점 번호 : 20597227  -  방법 1 : C 표준 입출력 stdio.h 쓰기

 

 

 

---

• 정리

 

이 번 문제는 입출력에 대한 이해를 필요로 해서 조금 어려웠을 수도 있다.

위 ios_base::sync_with_stdio 와 cin.tie 는 이후 알고리즘풀이에서 많은 데이터 입출력이 있을 때 많이 쓰이게 될 것이다. 그러니 미리 기억을 해두시면 좋을 것 같다.

 

물론 성능이 좋다고 무조건 좋은 코드는 아니기에 남용하기 보다는 정확한 기능에 대한 이해를 하고 적절하게 사용하는 것이 중요할 것이다. 프로그램을 개발하거나 할 때에는 정말 필요로 하지 않는 한 쓰지 않는 것이 좋긴 하다. 만약 어렵거나 이해가 되지 않은 부분이 있다면 언제든 댓글 남겨주시면 최대한 빠르게 답변드리겠다.