Batch 유형 문제

Batch 유형 문제는 정해진 입력을 읽어 정답인 출력을 내는 가장 기본적인 형태입니다.

문제 해결 방식

Batch 유형의 문제를 풀이하는 방식은 입력과 출력을 주고받는 방법에 따라 크게 표준 입출력 방식과 함수 구현 방식으로 나뉩니다.

표준 입출력 방식

표준 입출력 방식은 터미널 등으로 데이터를 입력받아 터미널 화면에 결과를 출력하는 방식입니다. C++의 cin과 cout, 또는 scanf와 printf를 사용합니다.

앞선 $A+B$ 문제의 경우, 참가자는 아래와 같이 입력부터 연산, 출력까지 모두 포함된 전체 main 함수 코드를 작성하여 제출해야 합니다.

#include <iostream>

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    cout << a + b << "\n";
    return 0;
}

함수 구현 방식

함수 구현 방식은 main 함수를 직접 작성하지 않고, 문제에서 요구하는 특정 함수만 완성하여 제출하는 방식입니다. 국제정보올림피아드(IOI)를 비롯한 여러 대회에서 주로 사용합니다.

참가자는 문제 지문에 명시된 함수 시그니처에 맞춰 파일 안에 해당 함수만 선언한 뒤, 내부 로직을 완성합니다. 입력을 읽어 변수에 저장하고 이 함수를 호출한 뒤 결과를 출력하는 과정은 채점 서버의 별도 프로그램이 전담합니다.

함수 구현 방식 주의사항

가장 먼저 유의해야 할 점은 표준 입출력 사용을 삼가야 한다는 것입니다. 채점기가 별도로 입출력을 관리하고 있기 때문에, 제출할 함수 안에서 cin, cout, printf 등을 사용하면 원래 출력해야 할 내용과 섞여 오답 처리될 수 있습니다. 디버깅 목적으로 출력문을 사용했다면 제출 전에는 모두 지워야 합니다.

다음으로 고려해야 할 사항은 함수의 다중 호출에 따른 전역 변수 초기화입니다. 한 번의 프로그램 실행 동안 채점기가 참가자의 함수를 여러 번 호출할 수 있습니다. 이는 문제 지문에 "이 함수는 각 테스트 케이스에 대해 최대 50번 호출된다."와 같은 형태로 명시됩니다. 이 경우 전역 변수를 사용하게 되면, 이전 호출의 연산 상태가 그대로 남아 현재 호출의 결과에 영향을 주게 됩니다. 따라서 전역 변수를 사용한다면 매 호출 시마다 상태를 명시적으로 초기화하는 과정을 포함해야 합니다.

IOI 환경과 제공 파일 (providing.zip)

함수 구현 방식을 사용하는 대회에서는 참가자가 로컬 환경에서 코드를 작성하고 테스트할 수 있도록 압축 파일 형태의 자료를 제공합니다. 이 압축 파일에는 코드를 작성하고 검증하는 데 필요한 여러 파일이 포함되어 있습니다.

1. 스켈레톤 코드 (problem.cpp)

참가자가 직접 작성해야 할 함수의 껍데기만 들어있는 파일입니다. 참가자는 이 파일의 내부 로직을 완성하여 제출합니다.

#include "problem.h"

int add(int a, int b) {
    return 5;
}

2. 헤더 파일 (problem.h)

스켈레톤 코드와 채점기가 서로 함수 구조를 알 수 있도록 공유하는 파일입니다.

#ifndef PROBLEM_H
#define PROBLEM_H

int add(int a, int b);

#endif

3. 채점기 (grader.cpp)

main 함수가 들어 있으며, 표준 입력을 읽어 스켈레톤 코드의 함수를 호출하고 결과를 표준 출력으로 내보내는 코드가 작성되어 있습니다.

#include <iostream>
#include "problem.h"

using namespace std;

int main() {
    int a, b;
    if (cin >> a >> b) {
        int ans = add(a, b);
        cout << ans << "\n";
    }
    return 0;
}

4. 예제 입출력 파일 (sample.in, sample.out)

추가로 채점기 실행 결과를 로컬에서 테스트해 볼 수 있도록 실제 예제 입출력 텍스트 파일이 동봉됩니다.

sample.in:

2 3

sample.out:

5

테스트 케이스와 서브태스크

제출된 코드는 서버에서 여러 개의 테스트 케이스를 통해 평가됩니다. 각각의 테스트 케이스는 특정한 상황을 가정한 입력 데이터와, 그에 대해 프로그램이 출력해야 하는 올바른 정답 데이터로 구성됩니다. 예를 들어 정수 $A$와 $B$가 주어졌을 때 $A+B$를 구하는 문제라면, 파일에 입력된 2 3이라는 문자열을 읽고 5를 출력하는지 확인하는 과정 하나가 독립된 테스트 케이스입니다.

문제에 따라 여러 개의 테스트 케이스를 묶어 하나의 서브태스크(Subtask)로 구성하기도 합니다. 서브태스크는 주로 변수의 조건이나 데이터의 크기에 따라 나뉩니다. 실제 정보올림피아드 문제 지문에서는 서브태스크를 다음과 같은 표 형태로 제시합니다.

앞선 $A+B$ 문제의 전체 조건이 $1\le A,B\le {10}^9$라고 가정할 때, 지문에는 다음과 같이 서브태스크가 주어질 수 있습니다.

서브태스크	점수	추가 조건
1	30	$A,B\le 100$
2	70	추가적인 제한이 없다.

실제 채점 서버에는 수십에서 수백 개의 비밀 테스트 케이스 파일들이 미리 준비되어 있습니다. 출제자는 각 테스트 케이스가 어떤 제약 조건을 만족하는지에 따라 이 파일들을 여러 그룹으로 묶어 서브태스크를 구성합니다.

예를 들어 전체 50개의 테스트 케이스가 있다면, $A,B\le 100$ 조건을 만족하는 1번부터 15번까지의 테스트 케이스들을 묶어 서브태스크 1에 할당하고, 값이 큰 나머지 16번부터 50번까지의 테스트 케이스들을 서브태스크 2에 할당하는 방식입니다.

하나의 서브태스크에 할당된 모든 테스트 케이스를 하나도 빠짐없이 통과해야만 해당 서브태스크의 배점을 얻을 수 있습니다. 만약 효율적이지 못한 알고리즘을 작성하여 서브태스크 2의 큰 테스트 케이스에서 시간 초과나 오답이 발생하더라도, 서브태스크 1에 묶인 15개의 작은 테스트 케이스를 모두 통과한다면 30점의 부분 점수를 획득하게 됩니다.

컴파일 및 실행 방법

함수 구현 방식에서는 채점기 파일과 작성한 스켈레톤 파일을 함께 컴파일해야 합니다. grader.cpp와 problem.cpp가 주어졌을 때 컴파일 명령어는 다음과 같습니다. 실제 문제에서 파일명이 다르게 주어진다면, 압축 파일 안에 있는 파일명에 맞춰 명령어를 바꿔야 합니다.

g++ grader.cpp problem.cpp -std=gnu++20 -O2 -pipe -Wall -o main

현재 디렉토리에 컴파일해야 할 C++ 파일이 grader.cpp와 problem.cpp뿐이라면, 다음처럼 *.cpp를 사용해도 됩니다.

g++ *.cpp -std=gnu++20 -O2 -pipe -Wall -o main

컴파일이 완료되면 실행 파일(main)이 생성됩니다. 생성된 프로그램에 예제 입력 파일(sample.in)을 리다이렉션하여 결과를 확인합니다. 터미널에서 아래와 같이 실행하면 채점기가 sample.in의 내용을 읽고 스켈레톤 코드의 add 함수를 호출하여 그 결과인 5를 화면에 출력합니다. 이 출력값이 sample.out의 내용과 일치하는지 비교하여 올바르게 구현했는지 확인할 수 있습니다.

./main < sample.in
5

참고로, 제공되는 grader.cpp는 로컬 테스트 용도이므로 참가자가 중간 변수를 출력하는 등 디버깅을 위해 코드를 약간 수정하여 실행할 수 있습니다. 단, 실제 채점 서버에서는 참가자에게 제공된 샘플 채점기와 다른 채점기가 사용될 수 있습니다.