[기초 다지기 - 0] 빠른 입출력

[Input & Output]
0 1 2 3 4 5 6 7 8 9 
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69
70 71 72 73 74 75 76 77 78 79
80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99

 

Input은 위와 같고 Output은 Input을 그대로 출력합니다.

 

일반적인 입출력이 존재하지만 충분히 많은 입출력에 대해서는 빠른 입출력이 필요합니다.

알고리즘 문제풀이를 하다보면 입출력만으로 시간초과가 나는 경우가 있으므로 숙지할 필요가 있습니다.

물론 위의 Input이 일반적인 널리 알려진 입출력 방식을 사용한다고 시간 초과가 발생할 만큼 충분히 많은 양은 아닙니다.

 

---

[Java]

 

> 기본 입출력

 

import java.util.*;

public class main1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int i = 0, j = 0;

        while (++i < 11) {
            while (++j < 11) {
                int in = sc.nextInt();
                System.out.print(in);
                System.out.print(' ');
            }
            j = 0;
            System.out.println();
        }

    }
}

 

가장 기본적으로 사용하는 Java의 입출력 Scanner와 Sysout입니다. Scanner는 받을 수 있는 자료형도 다양하고 위처럼 nextInt를 사용하여 토큰으로 입력을 받을 수 있어 매우 간편합니다. 하지만 느립니다.

원래도 느린 언어인 Java가 Scanner로 허비하는 시간은 치명적이라 할 수 있습니다.

 

또한 대부분의 상황에서는 출력이 작기 때문에 Sysout을 써도 무방하나, Sysout 역시 결코 빠르지 않습니다.

 

---

>  빠른 입출력

 

import java.io.*;
import java.util.StringTokenizer;

public class main1{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int i = 0;
        
        while(++i < 11) {
            st = new StringTokenizer(br.readLine());
            while (st.hasMoreTokens()) {
                sb.append(st.nextToken()).append(' ');
            }
            sb.append('\n');
        }

        System.out.println(sb.toString());
    }
}

 

빠른 입력을 위해 BufferedReader를 출력을 위해 StringBuilder를 사용하였습니다.

출력에 BufferedWriter를 사용하여도 무방합니다. StringBuilder가 미세하게 더 빠르다는 어느 글을 참고하여 StringBuilder를 사용합니다.

 

약간의 원리를 설명하자면,

 

• Scanner는 내부에 다양한 메소드를 구현하여 타입에 큰 구애를 받지 않는 장점과 아주 느리다는 단점을 갖게 됩니다.
• Stream이란 데이터의 흐름을 의미합니다. 우리는 데이터를 입력하거나, 출력받을 수 있습니다.
• 입력으로 설명을 계속하자면, 자바의 기본 입력 스트림인 InputStream은 Byte단위로 데이터를 가져옵니다. System.in은 InputStream 타입으로, 입력을 받습니다.
• 1바이트씩 입력을 받으면 당연히 Integer, Long 등 N바이트로 이루어진 입력을 받을 때 깨지게 됩니다.
• 이 때, InputStream을 바이트가 아닌 문자 단위로 받을 수 있게 하는 스트림이 InputStreamReader입니다.
• 또 문제가 생기는데, InputStream의 문제를 보완하는 InputStreamReader은 문자 단위로 받는다는 점입니다. 보통의 입력은 가변적으로 들어오는 문자열의 형태를 띠게 되는데 문자 단위로 받아오면 매번 배열을 생성하여 문자열의 형태로 받아줘야 합니다. 여기서는 Buffer를 이용하여 들어오는 문자들을 쌓아 놨다가, 한 번에 문자열처럼 보내주는 BufferedReader로 문제를 해결할 수 있습니다. (그래서 BufferedReader는 readLine()을 사용하여 String으로만 받을 수 있습니다.)
• 입력을 String형태로 받기 때문에 "0 1 2 3"과 같은 입력에서 각 숫자를 꺼내와야 하는 경우 난감합니다. Character단위로 받아 ' '를 제외한 문자들을 빼오는 방법도 있겠지만 Java에서 이럴 때 쓰라고 만들어준 StringTokenizer라는 함수를 사용합니다. ' ', ',' 과 같은 것들을 기준으로 끊어 Token화 해줍니다.
• StringBuilder는 불변성을 띠는 String과는 다르게 가변적입니다. 많은 출력을 전부 String에 덧붙이는 방식을 사용한다면 Java에서는 새로운 String을 할당하여 두 문자열을 붙이고 하나가 남은 문자열은 가비지 콜렉터가 회수하는 방식이라서 비효율적입니다. 가변적인 StringBuilder를 사용하면 위의 문제를 해결할 수 있습니다. (StringBuffer는 StringBuilder보다는 느린 대신 멀티쓰레드 환경에서 사용할 수 있습니다.)

간략하게 설명한 내용이므로 자세한 설명을 원한다면 https://st-lab.tistory.com/41를 참고하시면 됩니다.

 

---

 

[C++]

 

 > 기본 입출력

 

#include <iostream>
using namespace std;

int main(void) {
    int a = 0;
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            cin >> a;
            cout << a << ' ';
        }
        cout << endl;
    }

    return 0;
}

 

가장 기본적으로 배우는 방법입니다. cin, cout, endl를 사용하여 느립니다. cin, cout은 C의 printf, scanf보다 편리하다는 큰 장점이 있지만, 역시나 느립니다.

 

---

> 빠른 입출력

 

#include <iostream>
using namespace std;

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

    int a = 0;
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            cin >> a;
            cout << a << ' ';
        }
        cout << '\n';
    }

    return 0;
}

 

빠른 입출력을 위해 코드 세 줄을 추가하고, endl 대신 '\n'을 사용하였습니다.

위의 코드 세 줄을 추가하는 대신 scanf, printf를 사용하여도 무방하지만 cin, cout이 간편하기 때문에 cin, cout을 사용하면서도 빠르게 동작할 수 있게 코드 세 줄을 추가하였습니다.

 

약간의 원리를 설명하자면,

 

• cin, cout은 iostream헤더로 사용가능하나, stdio.h와도 동기화가 되어 있습니다. ios_base::sync_with_stdio, 즉 stdio.h와의 동기화(synchronize)를 끊어버리는 코드입니다. 동기화를 해제하여 iostream의 버퍼만 사용하게 되고 stdio.h와의 동기화 작업이 없어지게 되어 효율이 상승하게 됩니다.
• stdio.h와의 동기화를 해제했으므로 stdio의 입출력을 사용하면 cin, cout과의 순서를 보장할 수 없습니다. 또한 멀티쓰레드 역시 사용 불가합니다.
• cin은 사용 시 cout의 버퍼를 비우고 cout은 반대의 역할을 합니다. cin.tie(NULL), cout.tie(NULL)를 사용하여 버퍼를 비우는 과정을 없애면 시간이 단축됩니다.
• endl 역시 개행과 동시에 버퍼를 비우는 작업을 동반합니다. 마찬가지로 버퍼를 비우는 과정을 없애면 시간이 단축되므로 '\n'을 사용합니다.
• 알고리즘 문제풀이와 같은 싱글스레드 환경에서는 버퍼를 고려하지 않아도 괜찮습니다.

 

---

[Python]

 

> 기본 입출력

 

for i in range(10):
    a = list(map(int, input().split()))
    for n in a:
        print(n, end=' ')
    print()

 

input과 print를 이용한 기본적인 입출력입니다.

Java, cpp에서 배운 내용을 토대로 input, print가 느린 이유를 추측할 수 있을 것입니다. 버퍼를 비우는 과정, 기본적인 함수이다 보니 최적화가 되어 있는 것 정도가 느린 이유가 될 것입니다.

 

---

> 빠른 입출력

 

import sys

br = sys.stdin
bw = sys.stdout

for i in range(10):
    a = list(map(int, br.readline().split()))
    for n in a:
        bw.write(str(n))
        bw.write(" ")
    bw.write("\n")
    
bw.close()
br.close()

 

input, print 대신 sys.stdin, sys.stdout을 사용하였습니다.

자바의 br, bw처럼 사용 가능 하도록 br과 bw를 정의하여 사용하면 간편합니다.

 

약간의 원리를 설명하자면

 

• 우선 input()이 느린 이유는 input()은 인자로 Prompt Message를 받는데 이를 출력하는 기능을 갖고 있습니다. 여기서 시간의 차이가 나게 됩니다.
• 추가로 sys.stdio.readline()을 이용하면 모아놨다가 한 번에 버퍼에 넣게 되는데, input()을 사용하면 입력 한 줄마다 계속 버퍼에 넣게 됩니다. 입니다.
• 추가로 input()은 string으로 입력을 받기 때문에 split하여 list형으로 변환하고 map함수를 이용하여 int형으로 바꾼 후, map타입을 다시 list로 형변환하여 a에 저장하였습니다. 

 

정리

결국 모든 언어에서의 빠른 입출력의 핵심은 버퍼에 넣고 빼는 과정의 최소화를 통해 시간을 단축하는 것입니다.

(Java의 BufferedReader / C++의 cin.tie(NULL), cout.tie(NULL) / python의 sys.stdio.readline, sys.stdout.write)

 

C++에서의 ios_base::sync_with_stdio(false)처럼 언어의 특징으로 빠른 입출력을 가능하게 하는 경우도 있습니다.