degurii   2년 전

다름이 아니라 이번에 문제를 출제하게 되었는데요...

이쪽으로는 아예 처음이라 힘든 점이 많습니다 ㅜㅜ

제가 궁금한건, 혹시 테스트데이터 같은 경우 어느 정도의 범위로 얼마나(데이터 개수라 해야하나요?) 만들어 놓으시는지 궁금합니다.

예를들어

https://www.acmicpc.net/proble... (구간 합 구하기) 이 문제 같은 경우에

N, M, K의 수많은 조합이 생길 수 있잖아요?

이때 모든 N에 대해 몇개씩 데이터를 만든다거나, 특정한 N들(ex) 1, 50, 100, 150, ..., )에 대해서만 몇 개씩 만든다거나

아니면 다른 기준이 있을까 해서 질문드립니다

감사합니다!

djm03178   2년 전

테스트 데이터의 경우 전체 개수는 크게 중요하지 않습니다. 자기가 통과시키려고 한 솔루션들은 통과시키고, 막으려고 한 솔루션들은 막을 수만 있으면 됩니다.

구간 합 구하기 문제의 경우 전체적으로 답을 잘 출력하는지 보려면 N, M, K 최대로 랜덤하게 몇 개만 해보더라도 괜찮습니다. 출력의 양 자체가 많기 때문에, 틀린 알고리즘이었다면 매우 높은 확률로 1개의 랜덤 테스트에서도 오답을 출력할 가능성이 높기 때문입니다.

하지만 저 문제에서 또 막아야 하는 것이 있습니다. 우선 long long을 쓰지 않고 int를 쓴 솔루션이 통과되지 못해야 합니다. 그런 솔루션을 방지하기 위한 테스트를 또 한두 개 만들면 됩니다.

그리고 또한 naive하게 구간의 합을 구하는 솔루션 역시 막아야 하는데 이건 어떻게 하면 좋을까요? 최대 N 크기에서 처음부터 끝까지의 합을 계속 출력하게 하면 최악의 케이스가 될 것입니다.

그런데 이런 걸 또 뚫고 싶은 사람들이 메모이제이션 같은 걸 할 수도 있습니다. [a, b]에 대한 합을 구한 적이 있고 그 사이에서 값을 변경한 적이 없다면 이전에 구해둔 결과를 그대로 출력해버리는 식으로요. 그럼 이걸 어떻게 막으면 좋을까요? 값 변경과 합 출력을 번갈아가면서 하거나, 아니면 [a, b], [a, b - 1], [a, b - 2], ... 과 같이 범위는 넓게 유지하되 매번 조금씩 다른 구간을 넣어줄 수도 있습니다.

이런 식으로 "통과되어서는 안 되는 코드"가 어떤 것들이 있을지 생각해보고, 그들을 저격하는 데이터들을 만들어내는 걸 중점적으로 생각하시면 됩니다.

djm03178   2년 전

그리고 최소 입력에 대한 처리는 항상 어떤 이유에서든지 실수하기 쉽기 때문에 그에 대한 데이터도 꼭 있는 것이 좋습니다.

degurii   2년 전

자ㅣ세한 답변 정말 감사합니다!

chogahui05   2년 전

저는 보통 데이터 갯수 40개를 default로 두고..

검수 단계에서 약한 테케가 발견되면 2개 ~ 3개씩 추가를 합니다. 그렇게 해서 테케가 78개가 된 것도 있네요. ㅠㅠ

계속 추가해도, 제 naive한 풀이나, 비효율적인 풀이에 또 뚫려서..


저는 아예 문제를 제작할 때 평가 목표랑 

테스트 케이스 별 세부 분배 표를 먼저 만듭니다. 제 문제 중에서 쉬운 문제였던 업힐과 가희 같은 경우..

(1) 분수 처리를 할 수 있는가? (30%)

(2) 내분점, 외분점에 대해서 알고 있는가? (70%)

정도 주고 제작했는데요. 이렇게 평가 목표를 정하면, 어떤 식으로 테스트 케이스를 만들어야 할 지도 알 수 있더라고요.

degurii   2년 전

답변을 늦게 봤네요

정말 감사합니다

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