인터랙티브 문제 로컬 디버깅하기

마지막 수정 시각: 2020-10-26 22:03:12

인터랙티브 문제를 처음 접하면, 틀릴 때 도대체 왜 틀렸는지 모르겠는데 디버깅하는 방법도 알 수가 없어서 굉장히 헤매게 된다. 모든 인터랙티브 문제에서 사용할 수 있는 방법은 아니지만 인터랙터의 구현이 어렵지 않은 경우 쉽게 쓸 수 있는 코드 구조가 있어 간단히 정리해본다. 대부분의 인터랙티브 문제가 인터랙터 구현이 심플하기 때문에 이 방법만으로도 어지간해서는 로컬 디버깅을 어렵지 않게 할 수 있다.

인터랙터 흉내내기

인터랙티브 문제의 로컬 디버깅에서의 어려움은 일단 확실한 해결 방법이 하나 있다. 바로 문제에서 제시된 인터랙터(쿼리에 대한 응답을 하는 프로그램)를 그대로 로컬에 구현한 다음 이걸 이용해서 디버깅을 하는 것이다. 하지만 인터랙터를 별개의 프로그램으로 만든 후 이 인터랙터를 통해서 채점하는 시스템을 로컬에 다 구축하는 건 당연히 대회 중에 할 수 있을 만큼 간단한 일이 아니다. 그러니 이 부분을 어떻게 하면 쉽게 해결할 수 있는지에 초점을 맞춰보자.

여기서 쓸 수 있는 좋은 도구로 컴파일러 플래그(compiler flag)가 있다. 온라인 저지의 경우 대부분 C++ 채점에서 빌드시 ONLINE_JUDGE 플래그를 주고 컴파일을 한다. 사이트마다 조금 다를 수 있는데 보통 어딘가 공지에 있으므로 그 공지를 확인해보면 된다(BOJ와 코드포스, 앳코더의 경우 모두 ONLINE_JUDGE 플래그를 주게 되어 있다). 따라서, ONLINE_JUDGE 플래그가 정의되어 있는 경우 실제 인터랙터를 통해 쿼리를 하게 만들고, ONLINE_JUDGE 플래그가 정의되어 있지 않은 경우 로컬에서 흉내낸 인터랙터를 통해 쿼리 결과를 주게 코드를 짜면 손쉽게 디버깅을 할 수 있다.

예시 문제를 통해 정확히 어떤 식으로 구현할 수 있는지 알아보자.

Codeforces Round 669 C - Chocolate Bunny

최근 라운드에 나왔던 인터랙티브 문제다. 문제 요약은 다음과 같다.

길이 n의 순열(1 부터 n까지의 수가 정확히 한 번씩 나타나는 수열)이 있다. 정확히 2n 번의 쿼리를 통해 해당 순열의 값이 무엇인지를 알아내야 한다. 사용할 수 있는 쿼리는 다음과 같다.

? x y : 배열의 x번째 인덱스 값을 y번째 인덱스 값으로 나눈 나머지를 반환한다.
! (배열) : 정답을 추측한다. ! 뒤에 넘긴 배열이 답과 일치하지 않는 경우 오답.

이제 이 각각의 쿼리를 함수로 분리한다고 생각해보자. ? x y 꼴은 query(x, y)라는 함수, ! (배열) 꼴은 answer(arr) 이라는 함수로 정의한다.

int query(int x, int y)
{
	cout << "? " << x << " " << y << endl;
	int res;
	cin >> res;

	return res;
}

void answer(const vector<int>& arr)
{
	cout << "! ";
	for (int i = 1; i < arr.size(); i++)
		cout << arr[i] << " ";

	cout << endl;
}

이렇게하면 제출했을 때 채점 인터랙터와는 잘 상호작용하지만, 이것만으로는 로컬에서 내가 짠 게 올바른지 테스트를 할 수가 없다. 이제 이를 위해 인터랙터를 흉내내 보자.

인터랙터의 경우 정답을 알고 있어야 올바르게 동작할 수 있으므로, 로컬에서 테스트할 때만 동작하는 인터랙터 초기화용 init 함수를 정의할 것이다. init 함수는 인터랙터가 사용할 정답 순열을 입력 받아서 초기화하는 역할을 한다.

#ifndef ONLINE_JUDGE
vector<int> input;
#endif

void init(int n)
{
#ifndef ONLINE_JUDGE
	input.resize(n + 1);
	for (int i = 1; i <= n; i++)
		cin >> input[i];
#endif ONLINE_JUDGE
}

코드를 보면 로컬 인터랙터가 사용하는 부분은 #ifndef 를 통해 ONLINE_JUDGE 플래그가 없을 때에만 동작하게 되어 있다. 이렇게 해야 실제 제출시 로컬에서 인터랙터를 흉내냈던 부분이 아예 동작하지 않게 만들 수 있다.

이제 인터랙터가 필요한 데이터를 모두 초기화 했기 때문에 위에서 정의한 answer 함수와 query 함수도 이 입력받은 input을 기반으로 로컬에서 실행시 interactor의 동작을 흉내내게 수정할 수 있다.

#ifndef ONLINE_JUDGE
int qcount = 0;
#endif

int query(int x, int y)
{
#ifdef ONLINE_JUDGE
	cout << "? " << x << " " << y << endl;
	int res;
	cin >> res;

	return res;
#else
	qcount++;
	return input[x] % input[y];
#endif
}

void answer(const vector<int>& arr)
{
	cout << "! ";
	for (int i = 1; i < arr.size(); i++)
		cout << arr[i] << " ";

	cout << endl;

#ifndef ONLINE_JUDGE
	cout << "query: " << qcount << endl;
#endif
}

이렇게, query 함수의 경우 ONLINE_JUDGE가 정의되어 있지 않으면 쿼리 횟수를 세고(qcount), init 함수에서 초기화한 input 정보를 기반으로 인터랙터가 응답으로 줬어야 할 값(input[x] % input[y])을 반환하게 만든다.

answer의 경우 어떤 정답을 찍었는지 보여주는 부분은 굳이 바꿀 필요가 없으므로 내버려두고, 로컬에서 실행 시 쿼리 횟수를 확인해볼 수 있게 qcount를 출력하는 부분을 추가해준다.

이렇게 코드를 작성한 다음, main 함수에서는 위의 init, query, answer만을 이용해 답을 찾게 코드를 구성하면 로컬에서 완벽하게 인터랙터의 동작을 흉내낼 수 있다.

int main()
{
	int n;
	cin >> n;

	init(n);

	int q1 = query(1, 2);
	int q2 = query(3, 2);
	int q3 = query(1, 3);
	int q4 = query(2, 1);

	answer({ q1, q2, q3, q4 });

	return 0;
}

대충 이런 식으로. 이렇게 한 다음 일반적인 PS 문제 풀듯이, 입력 파일에 인터랙터의 초기화 과정에서 필요한 입력을 넣어주면 로컬에서 모든 동작을 디버깅해볼 수 있고, 여러 가지 테스트 케이스도 넣어볼 수 있다.

물론, 이 방법은 로컬에서 인터랙터를 직접 구현해주어야 하므로 조금 품이 들고 적응형 인터랙터를 가진 문제 등 인터랙터의 구현이 복잡할 경우 사용할 수는 없는 방법이다. 하지만 대부분의 인터랙티브 문제는 굉장히 심플한 형태의 인터랙터를 갖고 있기 때문에 이 방법만으로도 대다수의 인터랙티브 문제를 해결할 수 있고 디버깅 과정에서 아주 유용하게 쓸 수 있다.

요약하자면,

인터랙터를 필요로 하는 모든 동작을 함수로 추상화
함수의 내부 구현에서 ONLINE_JUDGE 플래그가 있는 경우 실제 인터랙터를 거치게, 그게 아닌 경우 내부에서 인터랙터의 동작을 흉내내서 값을 반환하게 구현
로컬에서 인터랙터의 동작에 필요한 입력 데이터를 받아서 인터랙터 초기화하기, 이 때 실제 로직에서 인터랙터만 써야하는 입력 데이터 건드리지 않고 로직 작성하게 주의(사실 추상화한 함수 인터페이스만 쓰면 건드릴 일 없음)
여러 가지 테스트 케이스를 넣어보면서 디버깅하기

와 같은 구조를 짜면 인터랙터 구현이 쉬운 문제의 경우 로컬에서도 어렵지 않게 디버깅할 수 있다.