March 20, 2021 18:49

개요

2017년 여름 본격적으로 BOJ에서 문제 풀이를 시작한 이래로 저는 많은 문제들에 데이터 추가 요청을 해왔습니다. 조금 사악한 취미일지도 모르겠으나, 문제를 풀어서 ‘맞았습니다!!’를 받는 것 이상으로 즐거웠던 것이 추가한 데이터에 의해 많은 ‘맞았습니다!!’를 받았던 코드들이 ‘틀렸습니다’ 내지는 ‘시간 초과’, 또는 ‘런타임 에러’ 등으로 바뀌는 것을 지켜보는 것이었습니다. 문제를 더 견고하게 만들었다는 뿌듯함과, 많은 분들이 놓쳤을 법한 포인트를 찾아 특이한 형태의 데이터를 제작하는 과정이 즐거웠습니다.

추가한 데이터들 중에는 단순히 기존의 데이터가 빈약해서 그다지 특이할 것 없는 형태의 데이터로 많은 저격이 되는 경우도 있었지만, 어떤 문제들에서는 특수한 형태의 잘못된 풀이나 실수를 저격하기 위해 극단적인 케이스를 고민해서 만들어야 하는 경우들도 있었습니다. 이번 글에서는 지금까지 추가해 본 데이터들 중 흥미로운 점이 있었던 것들을 일부 소개하려고 합니다.

1654번 - 랜선 자르기

처음으로 구체적인 테스트 케이스를 제시하여 추가 요청한 문제입니다. 기본적인 이분 탐색 문제로 많이 풀지만, 이분 탐색의 범위 설정을 조심해야 하는 케이스가 있습니다. 지금은 스포일러 방지 차원에서 케이스를 지웠지만, 여기에 그 케이스 중 하나를 올려보면 다음과 같습니다.

1 1
1

이 케이스가 저격하는 코드의 예시로는 다음과 같은 것이 있습니다.

#include <bits/stdc++.h>
using ll = long long;
using namespace std;

ll a[10001];

int main(void)
{
	ll k, n, i;
	cin >> k >> n;
	for (i = 0; i < k; i++)
		cin >> a[i];
	sort(a, a + k);
	ll hi = a[k - 1];
	ll lo = 0;
	while (1)
	{
		if (lo > hi)
			break;
		ll c = 0;
		ll mid = (hi + lo) / 2;
		for (i = 0; i < k; i++)
			c += a[i] / mid;
		if (c >= n)
			lo = mid + 1;
		else
			hi = mid - 1;
	}
	cout << hi;
}

이분 탐색의 범위를 $0$부터 가장 긴 랜선의 길이까지로 설정하고 있는데, 문제 조건상 답이 0이 되는 일은 있을 수 없으므로 0은 불필요한 탐색 범위입니다. 그런데, 이 문제에서는 단순히 불필요한 것을 넘어 프로그램의 정상적인 동작이 불가능하도록 하는 케이스도 존재할 수 있는데, 이것이 바로 1 1 1이라는 케이스입니다. 프로그램이 진행되다 보면 hi가 1까지 내려오게 되는데, 이때 mid가 0이 되면 c += a[i] / mid;에서 0으로 나누기가 발생하여 런타임 에러를 맞게 됩니다.

데이터 추가가 처음이었기 때문에 재채점 하던 당시 재채점 결과를 하나 하나 지켜보며 뿌듯해했던, 좋은 추억이 있는 데이터 추가 요청입니다.

1005번 - ACM Craft

이 문제 역시 추가한 데이터 자체는 글에서 지웠으나, 많은 동적 계획법 문제들에서 흔히 실수하는 사항을 저격했습니다.

이 글에서 저격하고자 하는 코드는 재귀를 통해 메모이제이션을 수행할 때 글에 남긴 것과 같이 dp[n]이 0보다 클 때에만 바로 값을 반환하는 코드입니다. 이 문제에서는 가중치가 0이 될 수 있기 때문에 dp[n]이 0이 계산 결과로 나올 수 있고, 따라서 이 값이 0이더라도 이미 계산이 끝난 결과라면 바로 반환이 되어야 올바르게 메모이제이션을 수행할 수 있습니다. 메모이제이션이 되지 않으면 최악의 경우 완전 탐색을 하는 것과 같기 때문에 지수 형태의 시간 복잡도가 만들어집니다. 그러나 dp의 초기값을 0으로 설정하고 0이 아닐 때에만 반환하는 코드가 많아 상당히 많은 코드들이 ‘맞았습니다!!’에서 ‘시간 초과’로 바뀌게 되었습니다.

이와 비슷한 경우를 저격한 데이터 추가 요청으로 2186번 - 문자판 등이 있습니다.

2624번 - 동전 바꿔주기

이 문제는 지문의 조건이 부실했던 것으로 결론이 나면서 데이터를 추가하는 데에는 실패했지만 데이터를 만드는 과정이 재미있었습니다. 기존의 조건에서 답이 $2^{31}$을 초과하지 않는다고 했기 때문에 답이 정확히 $2^{31}$일 경우 C나 C++, Java 등의 int형에 담을 수 없어 int로 푼 모든 코드가 틀리게 될 뻔했습니다.

정확히 답이 $2^{31}$이 되는 케이스를 찾는 것은 간단하지 않았습니다. 동전의 종류를 하나 추가할 때마다, 개수를 조정할 때마다 답에 미치는 영향을 정확하게 식으로 계산해내기가 어려웠기 때문입니다. 그래서 우선 세부 조정이 쉽도록 목표 금액을 높게 잡고, 금액이 작은 동전을 여러 개 사용 가능하게 하면 답을 크게 증가시키는 경향이 있음을 이용해서, 금액이 10~18인 동전들을 적절하게 사용하여 $2^{31}$을 넘지 않으면서 최대한 $2^{31}$에 가까워지도록 개수를 조정하고 목표 금액도 수정했습니다. 그 후 남은 몇 가지 경우의 수는 반대로 매우 큰 동전들을 하나씩 배치함으로써, 그 동전을 사용할 경우 목표 금액을 만들 수 있는 방법이 매우 적도록 만들어 한 자릿수 단위의 경우의 수를 추가했습니다. 예를 들어 금액이 $982$인 동전을 하나 사용할 경우 그 후 목표 금액인 $992$를 만들어낼 유일한 방법은 금액이 $10$인 동전을 하나 더 사용하는 것뿐일 것입니다.

1850번 - 최대공약수

이 문제도 비슷하게 조건이 부실하여 수많은 long long 풀이들을 저격할 뻔했으나 조건이 바뀌면서 무산되었습니다. 기존의 조건에서는 주어지는 수가 19자리 이하임만을 보장했기 때문에, 19자리로 만들 수 있는 최댓값인 9999999999999999999을 케이스에 추가하면 8바이트 부호 있는 정수형의 최댓값은 9223372036854775807이므로 long long으로 입력받을 수가 없습니다. 조건을 그대로 따라 데이터를 만들고 unsigned long long만 통과되게 했으면 매우 사악한 문제가 될 뻔했습니다.

7576번 - 토마토

이 문제는 BFS를 처음 접하는 초보자에게 ‘시작 정점을 여럿으로 한다’는 조금 어려운 생각을 요구합니다. 그러나 이전에는 이 글과 같이 모든 토마토에 대해 거리가 갱신되는 지점에 대해서만 BFS를 수행한 코드가 통과되었습니다.

추가한 데이터를 $n=20$으로 설정하고 같은 패턴으로 만들면 아래와 같이 됩니다.

20 20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

원리는 간단합니다. 왼쪽 위에서 출발한 익은 토마토가 익지 않은 토마토들을 따라 오른쪽 아래 끝에 도달하려면 기다란 지그재그를 따라 끝까지 탐색해야 하지만, 오른쪽 아래에 있는 익은 토마토들에서 시작할수록 그 거리는 점점 짧아지게 됩니다. 결국 새로운 토마토를 발견할 때마다 긴 지그재그를 전부 끝까지 따라가며 BFS를 해야 하기 때문에 총 $\mathcal{O}((NM)^2)$이라는 최악의 시간 복잡도에 해당하는 케이스를 만들어낼 수 있습니다.

1927번 - 최소 힙

쿼리 문제에서 이와 같은 데이터는 반드시 필요합니다. C++의 경우 별도의 처리 없이 cin과 cout을 번갈아 사용하면 cin을 사용할 때마다 cout에 flush가 발생하기 때문에, 쿼리형 문제에서 모든 쿼리를 출력하는 쿼리로 만들면 엄청나게 많은 flush가 발생하여 코드를 매우 느려지게 만들 수 있습니다.

1753번 - 최단경로

이 데이터는 이전에 쓴 글 잘못 구현한 다익스트라 알고리즘 저격하기에서 제시한 잘못된 코드 중 간선의 가중치를 기준으로 우선순위 큐에서 정점을 뽑는 코드들을 저격한 데이터입니다. 다익스트라 알고리즘은 각각의 실수에 대해 인위적인 저격을 하지 않으면 빠르게 통과되는 경우가 많음을 느낄 수 있는 부분입니다.

비슷한 저격 사례로 15730번 - 수영장 사장님 문제도 있습니다.

14698번 - 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)

개인적으로 가장 기억에 남는 데이터 추가입니다. 문제의 조건이 매우 독특해서, “~로 나눈 나머지를 출력한다”류의 문제임에도 불구하고 실제로 계산 과정에서 나올 수 있는 값이 많이 크지 않기 때문에 랜덤 케이스로는 저격이 잘 안 되는 경우였습니다.

정해대로라면 우선순위 큐에 넣는 원소는 모듈로를 취하지 않은 수를 그대로 넣고, 모듈로는 정답 계산 시에만 해줘야 하는 것이지만, 모듈로를 취한 수를 우선순위 큐에 넣더라도 그에 의해 실제 계산 결과가 달라지려면 다음과 같이 흔치 않은 상황이 만들어져야 했기 때문에 쉽게 틀리지 않을 수 있었습니다.

1. 우선순위 큐에 원소가 3개 이상 들어가 있고
2. 모듈로를 취해서 작아진 값이 원래는 우선순위 큐에 있는 원소들 중 가장 작은 두 값 중 하나가 아니어야 하지만 작아지는 바람에 해당되게 됨

이와 같은 상황이 $N=4$에서 만들어지려면 입력값들을 오름차순으로 $a$, $b$, $c$, $d$라고 할 때, 처음으로 연산되는 곱인 $a \times b$가 모듈로 값인 $1000000007$보다 커야 하고 모듈로된 값은 $c$나 $d$ 둘 중 하나보다는 작아야 하며, 문제의 조건에 의해 $a \times b \times c \times d$는 $2 \times 10^{18}$ 이하가 되어야 합니다. 만일 이 제한이 그냥 $10^{18}$이었다면 $c \times d \ge a \times b \gt 10^9$이기 때문에 제한에 맞는 케이스를 만들 수 없었겠지만 운이 좋았습니다. 추가한 데이터인 31623 31623 31624 31624는 이 모두를 만족시키는 매우 드문 케이스입니다.

1939번 - 중량제한

이 문제를 푸는 방법에는 여러 가지가 있지만, 잘못된 방법으로 시도한 분도 많았습니다. 그 중에는 “BFS를 하되, 현재까지 거쳐온 경로에서 가장 제한이 작은 다리의 제한이 더 커질 때에만 그 정점을 큐에 넣고, 큐에서 뺀 후 방문 체크를 하지 않는” 풀이도 있었습니다. 이 풀이의 문제점은 큐에 들어간 정점이 큐에서 나올 때 최적의 답을 가지고 있지 못할 수 있다는 점인데, 일반적인 랜덤 케이스로는 잘 저격이 되지 않는다는 특징이 있습니다.

이를 저격하기 위해 다음과 같은 케이스를 만들어 보았습니다. $1$번 정점에서 $2$번 정점으로 가는 것이 목표인데, 간선은 $1$번 정점에서 $N$번 정점으로 가는 간선 $\cfrac{M}{2}$개가 가중치의 오름차순으로 주어지고, $N$번 정점에서 $2$번 정점으로 가는 간선이 $\cfrac{M}{2}$개 있는 케이스입니다. 이렇게 하면 $1$번 정점에서 $N$번 정점으로 가는 간선 $\cfrac{M}{2}$개를 체크하는 내내 항상 $N$번 정점에 대한 답의 갱신이 일어나기 때문에 큐에 $\cfrac{M}{2}$개의 $N$번 정점이 들어갑니다. 이후 큐에서 빠지는 $\cfrac{M}{2}$개의 정점이 방문 체크를 하지 않아 모두 자신과 연결된 $M$개의 간선을 전부 체크하기 때문에 시간 복잡도가 $\mathcal{O}(M^2)$이 됩니다.

3079번 - 입국심사

풀이 자체는 간단한 이분 탐색으로 가능하지만, Python과 같이 bigint가 기본으로 지원되지 않는 언어라면 오버플로의 함정에 빠지기 매우 쉬운 문제입니다. 입력 범위는 int 내에 들어오지만, 최악의 경우 답은 $N=1$이고 $M=10^9$, $T_1=10^9$ 인 경우로 long long 범위까지 잡아야 구할 수 있을 뿐 아니라, 이러한 경우를 처리하기 위해 이분 탐색 범위를 $10^{18}$까지 잡고 그대로 연산하다가는 반대로 $T_k$가 작은 경우 엄청나게 큰 수들을 계속 더해나갈 여지가 있기 때문입니다. 그러나 기존 데이터에는 그런 오버플로를 저격하는 데이터가 없었습니다.

재채점 결과에서 보이듯이 상당히 많은 코드가 저격되었고, solved.ac 기여 페이지를 보면 이후에 문제를 푸는 분들에게도 상당히 까다로운 케이스로 작용하고 있는 것으로 보입니다.

2108번 - 통계학

실수형 사용시 얼마나 주의해야 하는지 알려주는 데이터 추가입니다. float의 유효숫자가 여섯 자리밖에 되지 않기 때문에 float 사용 시 충분히 큰 케이스에서는 산술평균을 올바르게 구하지 못할 수 있는데, 미묘한 오차로 반올림 방향이 반대가 되도록 만들어야 했기에 역시 랜덤 케이스로는 잘 틀리지 않았던 것으로 보입니다.

17070번 - 파이프 옮기기 1

문제의 조건 중 “방법의 수는 항상 1,000,000보다 작거나 같다.”는 아마도 완전 탐색을 해도 통과될 수 있게 하겠다는 의도를 담은 것으로 보입니다. 실제로 충분히 빠른 언어로 충분히 효율적으로 구현만 한다면 완전 탐색이어도 여유 있게 통과가 가능합니다.

하지만 그 의도와는 달리 이 조건은 완전 탐색 풀이에 추가적인 여유를 부여하는 데에는 거의 도움이 되지 못했습니다. 이 요청에서 추가한 데이터는 최대한 오랫동안 완전 탐색을 하게 하면서도, 딱 마지막 칸에는 절대로 도달할 수 없게 만듦으로써 방법의 수 제한도 지키고 있습니다. 결국 완전 탐색을 좀 더 비효율적인 언어로 비효율적으로 푼 코드들이 상당수 저격당하고 말았습니다.

17472번 - 다리 만들기 2

이런 종류의 문제가 대부분 그렇듯이 이 문제도 방대하고 정교한 구현을 요구합니다. 그에 비해 한두 군데 실수가 있어도 대부분의 케이스를 통과할 가능성도 상당히 높습니다. 문제가 올라온 초기에 정답률이 상당히 높았기에 의문을 품고 공개된 정답 코드들을 모두 열고, 직접 제작한 스트레스 프로그램을 통해 수백 개 이상의 랜덤 케이스를 각각 실행시켜 보았고, 그 결과 상당히 많은 수의 코드를 저격할 수 있었습니다.

이와 비슷하게 1243번 - 팰린드롬, 3019번 - 테트리스 문제들도 스트레스를 통해 여러 코드를 저격한 바가 있습니다.

마치며

‘맞았습니다!!’를 받는 것이 정말로 코드에 전혀 결점이 없음을 보장해주지는 않습니다. 아마도 실제로 BOJ에서 ‘맞았습니다!!’로 처리된 코드들을 모두 확인해볼 수 있다면 상당히 높은 비율의 코드가 저격이 가능한 상태이지 않을까 생각합니다. 문제를 푸는 과정도 재미있지만, 이러한 코드들을 찾아서 저격해보는 것도 상당히 재미있는 작업이라고 생각합니다.