unta   2년 전

들어가기에 앞서

아래에서 설명하는 내용은 리눅스 기준이며 윈도우 등 다른 운영체제에서는 제대로 동작하지 않을 수 있습니다.
다만, 백준 채점 서버는 리눅스를 사용하므로 아래의 방법을 따라서 구현해도 무방합니다.

tl;dr

  1. 바이너리 형식의 입력은 32비트 정수형으로 연속해서 들어옵니다.
  2. 따라서 4바이트씩 끊어서 입력을 처리하면 됩니다.
  3. 그런데 원본이 123이면 입력은 321으로 자릿수가 역전된 형태의 리틀 엔디안으로 입력이 들어오므로 이를 뒤집어주어야 합니다.

최종 코드

#include <stdio.h>

int parse_int() {
    unsigned char bytes[4] = { 0, };

    if (scanf("%c%c%c%c", bytes + 0, bytes + 1, bytes + 2, bytes + 3) == 0) {
        return 0;
    }

    return (bytes[3] << (3 * 8)) +
           (bytes[2] << (2 * 8)) +
           (bytes[1] << (1 * 8)) +
           (bytes[0] << (0 * 8));
}

int main(void) {
    int rows = parse_int();
    int cols = parse_int();
    printf("%d %d\n", rows, cols);

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            int cell = parse_int();
            printf("%d ", cell);
        }
        printf("\n");
    }
    printf("\n");

    while (1) {
        int x = parse_int();
        int y = parse_int();

        if (x == 0) {
            break;
        }

        printf("%d %d\n", x, y);
    }

    return 0;
}

위 코드를 통해 예시로 주어진 바이너리 형식의 입력을 읽어보면 아래와 같이 텍스트 형식으로 출력됨을 확인할 수 있습니다.

$ cat 9265.in | ./a.out
2 4
1 5 10 10
2 10 20 99

10 99
2 9
100 1000
10 10

개요

본 문제에서 주어지는 입력은 일반적으로 다른 문제에서 주어지는 텍스트 형식의 입력과는 조금 다르게 주어집니다.

이 글에서는 문제에서 주어지는 바이너리 입력의 의미와 그것을 입력받는 방법을 소개합니다.

텍스트 형식과 바이너리 형식

일반적으로 다른 문제에서 주어지는 텍스트 형식의 입력은 아래와 같이 사람이 읽을 수 있는 형태로 주어집니다.

6
10 20 10 30 20 50

위의 입력은 14003 가장 긴 증가하는 부분 수열 5의 예제 입력으로 사람이 읽고 이해할 수 있습니다.

본 문제에서 주어지는 예제 입력도 아래와 같이 사람이 읽고 이해할 수 있게 주어집니다.

2 4
1 5 10 10
2 10 20 99

10 99
2 9
100 1000
10 10

그러나 바로 아래의 힌트 문단을 보면 아래와 같이 적혀 있습니다.

Sample Input, here in text form, not binary, for obvious reasons.

바이너리 형식의 예제 입력은 https://www.acmicpc.net/data/9265.in 에서 받을 수 있다.

예제 입력은 바이너리 형식이 아닌 텍스트 형식으로 주어지며 실제 입력은 바이너리 형식으로 주어짐을 알 수 있습니다.

첨부된 링크에서 받을 수 있는 파일을 열어보면,

    
 
  
  c 
 c       d Ϩ 
 
 

와 같이 사람이 읽고 이해할 수 없는 것을 알 수 있습니다.

그런데 이를 xxd라는 프로그램을 통해 바이트 단위로 살펴보게 되면,

00000000: 0200 0000 0400 0000 0100 0000 0500 0000  ................
00000010: 0a00 0000 0a00 0000 0200 0000 0a00 0000  ................
00000020: 1400 0000 6300 0000 0a00 0000 6300 0000  ....c.......c...
00000030: 0200 0000 0900 0000 6400 0000 e803 0000  ........d.......
00000040: 0a00 0000 0a00 0000                      ........

와 같이 나오는 것을 볼 수 있습니다.

바이너리 형식 해석하기

위의 바이너리 형식을 해석하기 위해 첫 줄을 가져와봅니다.

00000000: 0200 0000 0400 0000 0100 0000 0500 0000  ................

이때 지문에서 "The input file is a binary file containing 32-bit integer numbers."라고 32비트 정수형이 입력됨을 알려주고 있으므로 주어진 입력을 32비트 단위로 끊어서 읽으면 됩니다.
xxd는 각 바이트를 16진수 형태로 표시하므로 하나의 숫자가 4비트를 표시할 수 있습니다.

따라서 입력을 32비트 단위로 쪼개어 읽기 위해선 8개 숫자 단위로 끊어서 읽으면 됩니다.

첫 번째 숫자를 해석하기 위해 첫 8개 숫자를 가져와봅시다.

0200 0000

이는 입력으로 주어지는 첫 번째 숫자의 16진수 표현입니다.

그렇다면 0200 0000은 아래에 있는 텍스트 형식의 입력에서의 첫 번째 수와 동일하므로 2가 되어야 합니다.

2 4
1 5 10 10
2 10 20 99

10 99
2 9
100 1000
10 10

그런데 이상합니다. 일반적으로 2를 표기할 때에는 그냥 2만 적거나 앞에 0 등을 붙여 002와 같이 형식을 맞춰주는 것이 보통입니다.
그런데 0200 0000은 이상합니다.

이것을 이해하기 위해 컴퓨터가 정보를 어떻게 저장하는지 알아야 합니다.

빅 엔디언과 리틀 엔디언

123이라는 수가 있다고 생각해봅시다. 123는 오른쪽부터 왼쪽 방향으로 자릿수가 커지는 형식입니다.
즉, 가장 오른쪽에 1의 자리수가 오고 그 다음에 10의 자리수가 오고 그 다음에 100의 자리수가 오는 형태입니다.

이런 식으로 가장 오른쪽에서부터 왼쪽으로 자릿수가 점점 커지도록 표기하는 방법을 빅 엔디언이라고 합니다.
처음으로 보이는 숫자인 1이 자릿수가 가장 크므로 빅 엔디언이라고 이해하면 쉽습니다.

컴퓨터는 반대로 왼쪽에서 오른쪽으로 자릿수가 점점 커지도록 정보를 저장합니다.
123은 컴퓨에에서 321로 저장될 것입니다.

이렇게 저장하면 덧셈 뺄셈과 같이 자릿수가 낮은 쪽에서 시작하여 높은 곳으로 올라가는 연산을 할 때 연산을 더 쉽게 처리할 수 있습니다.

이런 식으로 가장 왼쪽에서부터 오른쪽으로 자릿수가 점점 커지도록 표기하는 방법을 리틀 엔디언이라고 합니다.
처음으로 보이는 숫자인 3이 자릿수가 가장 작으므로 리틀 엔디언이라고 이해하면 쉽습니다.

다시 실제 입력으로 돌아와서 입력을 살펴보면,

0200 0000

이상하게 나타난 숫자들의 의미를 파악할 수 있습니다.

먼저, 컴퓨터는 정보를 바이트 단위로 처리하므로 입력을 2개 숫자씩 끊어보면,

02 00 00 00

이 됩니다.

위에서 컴퓨터는 리틀 엔디언, 즉 일반적으로 사람이 사용하는 표기법과는 반대로 수를 쓴다는 것을 고려해 이를 뒤집어보면,

00 00 00 02

이 됩니다.

이제 이를 다시 붙여보면 00000002로 형식을 맞추기 위해 앞에 0이 7번 붙은 2가 나타납니다.
그리고 2는 앞서 텍스트 형식으로 봤던 첫 번째 숫자 2와 일치합니다.

구현하기

상술한 내용에 의하면 입력으로 주어지는 바이너리 형식은 바이트 단위로 뒤집어져 주어짐을 알 수 있습니다.
따라서 32비트 정수형을 만들기 위해 먼저 4바이트를 입력받은 후 이를 바이트 단위로 뒤집어주면 됩니다.

바이트 단위로 입력받기 위해서 unsigned char와 scanf를 사용합니다.

int parse_int() {
    unsigned char bytes[4] = { 0, };

    scanf("%c%c%c%c", bytes + 0, bytes + 1, bytes + 2, bytes + 3);

    return (bytes[3] << (3 * 8)) +
           (bytes[2] << (2 * 8)) +
           (bytes[1] << (1 * 8)) +
           (bytes[0] << (0 * 8));
}

바이트를 입력받을 unsigned char 배열을 선언합니다.
총 네 개의 바이트를 받을 것이므로 길이는 4로 지정합니다.

배열의 0번째부터 3번째까지 차례대로 %c형식으로 입력받습니다.
이렇게 하면 단일 바이트를 입력받을 수 있습니다.
(%d, %u, %hhu 등은 입력을 정수형으로 처리하려고 하기 때문에 단일 바이트를 있는 그대로 입력받을 수 없습니다.)

이후 각 바이트를 비트 연산을 활용해 순서를 뒤집어 더해주면 끝입니다.

int main(void) {
    int rows = parse_int();
    int cols = parse_int();

    printf("rows: %d\n", rows);
    printf("cols: %d\n", cols);

    return 0;
}

위와 같이 main 함수를 정의해 첫 두 개의 정수, rows와 cols를 입력받아봅시다.

$ cat 9265.in | ./a.out
rows: 2
rows: 4

2와 4를 성공적으로 읽은 것을 볼 수 있습니다.

EOF 판단하기

이제 바이너리 형식으로 주어진 정수를 읽을 수 있게 됐습니다.
그런데 지문에는 "An unspecified number of integers, representing the (X,Y) pairs, one pair at a time."와 같은 문장이 있습니다.

(X, Y) 꼴로 정수가 두 개씩 짝지어 주어질 것인데 그 개수를 주지 않을 거랍니다.
즉, 입력이 끝나는 지점을 알아서 판단해야 합니다.

이 문제는 scanf의 반환값을 통해 해결할 수 있습니다.

scanf의 반환값

scanf는 사실 반환값을 갖는 함수입니다.
거두절미하자면 scanf는 성공적으로 입력받은 변수의 개수를 반환합니니다.

scanf("%c%c%c%c", bytes + 0, bytes + 1, bytes + 2, bytes + 3);

위에 코드에서 scanf는 %c 형식으로 총 네 개의 변수에 입력을 받고자 하고 있습니다.
만약 네 개의 변수에 입력을 성공적으로 받았다면 scanf는 4를 반환합니다.

그렇다면 입력의 끝에 도달하여 더 이상 입력을 받을 수 없다면 scanf는 0반환할 것입니다.

int parse_int() {
    unsigned char bytes[4] = { 0, };

    if (scanf("%c%c%c%c", bytes + 0, bytes + 1, bytes + 2, bytes + 3) == 0) {
        return 0;
    }

    return (bytes[3] << (3 * 8)) +
           (bytes[2] << (2 * 8)) +
           (bytes[1] << (1 * 8)) +
           (bytes[0] << (0 * 8));
}

위와 같이 scanf의 반환값이 0이면 0을 반환하도록 할 수 있습니다.
(주어지는 입력이 모두 자연수이므로 0은 정상적인 입력과 비정상적인 입력을 구분하는 데 쓰일 수 있습니다.)

최종 코드

#include <stdio.h>

int parse_int() {
    unsigned char bytes[4] = { 0, };

    if (scanf("%c%c%c%c", bytes + 0, bytes + 1, bytes + 2, bytes + 3) == 0) {
        return 0;
    }

    return (bytes[3] << (3 * 8)) +
           (bytes[2] << (2 * 8)) +
           (bytes[1] << (1 * 8)) +
           (bytes[0] << (0 * 8));
}

int main(void) {
    int rows = parse_int();
    int cols = parse_int();
    printf("%d %d\n", rows, cols);

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            int cell = parse_int();
            printf("%d ", cell);
        }
        printf("\n");
    }
    printf("\n");

    while (1) {
        int x = parse_int();
        int y = parse_int();

        if (x == 0) {
            break;
        }

        printf("%d %d\n", x, y);
    }

    return 0;
}

위 코드를 통해 예시로 주어진 바이너리 형식의 입력을 읽어보면 아래와 같이 텍스트 형식으로 출력됨을 확인할 수 있습니다.

$ cat 9265.in | ./a.out
2 4
1 5 10 10
2 10 20 99

10 99
2 9
100 1000
10 10

lcr7324   2년 전

정성스러운 글 감사합니다.

약간 첨언하자면, 값의 '해석' 또한 백준 채점 서버를 포함한 대부분의 환경에서 little endian으로 이루어진다는 점에 착안해 아래와 같이 parse_int 함수를 작성하는 것도 가능합니다.

1) bytes의 주소에서 찾을 수 있는 비트열을

2) int*형 주소로 취급합니다.

3) 이를 dereference 하면 해당 주소에서 읽은 데이터를 int형으로 '해석'하며, little endian 환경의 경우 이를 little endian으로 해석하게 되므로 원하는 값으로 읽히게 됩니다.

zenith82114   2년 전

확신은 없는데 alignment 제약이 더 강한 타입으로의 포인터 캐스팅은 UB인 것으로 알고 있습니다(misaligned pointer를 지원하지 못하는 플랫폼들도 수용하기 위해서). 즉 bytes 배열의 시작 주소가 4의 배수가 아니어서 misaligned pointer가 되면 우리가 상상하는 그 동작이 일어나지 않을 수 있습니다. alignas struct를 씀으로써 이를 회피할 수 있고, x86 계열 프로세서들은 misaligned access도 괜찮다는 것 같습니다(이유는 모르겠습니다).

댓글을 작성하려면 로그인해야 합니다.