PS를 하는 사람들은 다들 Wrong Answer를 받은 경험이 있을 것이다. WA의 원인으로는 틀린풀이, 구현실수 등 다양한 것들이 존재하며, 이들 중에는 쉽게 발견할 수 있는 것도 있는 반면, 좀처럼 발견되지 않아 이른바 맞왜틀을 연발하게 되는 실수들도 있다. 도무지 자신의 힘으로는 오류를 발견하지 못할 것 같은 극한 상황에서, 많은 PS러들은 최후의 무기, stress test를 하곤 한다.
0. 서론 - stress test란?
stress test는 문제의 자명한 naive 솔루션과 본인의 솔루션을 두고, 무수히 많은 testcase를 돌려 비교해보면서 반례를 찾는 기법이다. 일반적으로 naive 코드는 시간복잡도가 효율적이지 않은 대신 무조건 맞는 정답을 제공하고, 자신이 채점기에 제출한 main solution은 제한 안에 도는 효율적인 시간복잡도를 가진 대신 어딘가에 결함이 있어 WA를 받는 상태일 것이다. stress test는 naive 코드로도 돌릴 수 있는 작은 TC를 만들어 그 TC의 정답을 찾고, main solution이 해당 TC를 잘 통과하는지 확인하는 방식으로 작동된다.
솔브닥 디코나 다른 코포 랭커들의 라이브 방송을 몇번 보면서 느낀건, 사람들이 stress test를 사용하는 방법이 제각각이라는 것이다. 앞선 잡기술 주제였던 세팅은 그래도 몇개의 정해진 틀들이 있으나, 지금 다루는 stress test는 정말 그 방법이 너무 다양해서 더더욱 정답인 게 없다. 다만 개인적으로 별로라고 생각하는 방식이나 습관이 몇몇 있었고, 이 글에서는 그런 방식들이 좋지 않은 이유와 이들의 개선 방안 등을 다룬다. 이는 지극히 개인적인 의견이라 각자 알아서 걸러들으면 좋을 것 같다.
1. stress test를 한 파일에 몰아서 하지 말자.
과거 본인의 사례이다. n년 전의 kwoncycle은 stress test를 돌릴 때 냅다 한 코드에 몰아서 했었다. (그리고 아마 꽤 많은 PS러들이 저렇게 하지 않을까라는 개인적인 생각이 있다) 이게 무슨 말이냐면. 가령, WA가 뜬 solution 코드가 아래의 꼴이라면
int main(){
int input; cin >> input; // 입력을 받음
int ans = solve(input); // 열심히 풀이 로직을 구현
cout << ans << "\n"; // 구한 답을 출력
}
그럼 이 코드의 stress 코드를 이렇게 짰었다. (solve 함수라도 있으면 다행이고, 그런 거 없이 직접 구현된 경우가 더 많았다...)
int main(){
while(True){
int input; //cin >> input; // 입력을 받음
input = rand();
int ans = solve(input); // 열심히 풀이 로직을 구현
int ans0 = naive(input);
if(ans != ans0) cout << input;
//cout << ans << "\n"; // 구한 답을 출력
}
}
얼핏 보면 그냥 잘짠거 아닌가 싶지만, 그건 저 코드가 간단해서 그렇게 보이는것. stress code까지 동원할 정도면 높은 확률로 당신의 코드는 스파게티 범벅이 되었을테고, 그 위에 rand함수, naive함수, ans비교까지 다 넣으면 정말 모양새가 끔찍해진다. 예를 들어서,
- 만약 솔루션이 케이스워크 문제라 ans를 여러 곳의 if문에서 출력할 경우, naive 답 비교를 각각의 if에서 전부 다 할 것인가?
- 코드 실행 중 input 원본이 훼손되도록 코드를 짰을때, naive 코드는 어떻게 돌릴 것인가?
- 원래의 solution code를 어떻게 관리할 것인가?(애초에 하긴 할 것인가? 따로 백업 안하고 냅다 위에 stress code를 쓰는 사람들을 정말 많이 봤다.)
- 원래의 solution 코드에서 잘못된 걸 찾아 뜯어고쳤다. 그럼 그 수정 사항을 어떻게 stress 코드에 적용할 것인가?
뭐 이런 이유들로 stress test를 돌리는 데 많은 제약이 걸리게 된다. 24년 AllSolvedIn1557팀은 대회 중 스트레스 테스트를 거의 하지 않았는데, 저런 문제점들을 깔끔히 해결하지 못해서가 원인이었던 것 같다.
1.1 그럼 해결책은?
그냥 solve 코드와 naive 코드를 분리를 하면 된다! 각각의 solve.c++, naive.c++을 짠 후, 원하는 input을 각각 실행시켜 비교하는 것이다. 다소 귀찮아보이지만, 입력 받는 부분은 solve.c++에서 복붙하면 되니 생각보다 별 차이가 없다. 랜덤 input을 넣고 비교하는 과정은 사람마다 차이가 좀 있는데, 필자는 subprocess 모듈의 run을 기반으로 작성된 template 코드를 주로 사용한다.
from subprocess import run, PIPE
def sh(cmd, inp=None):
return run(cmd, input=inp, text=True, stdout=PIPE, check=True).stdout
# 컴파일
for src, out in (("input.c++","input"), ("naive.c++","naive"), ("solve.c++","solve")):
run(["g++", src, "-o", out], check=True)
for i in range(100000):
inp = sh(["./input"], str(i))
o1 = sh(["./naive"], inp)
o2 = sh(["./solve"], inp)
if o1 != o2:
print("=== input ===\n", inp, sep="")
print("=== naive ===\n", o1, sep="")
print("=== solve ===\n", o2, sep="")
break위 코드를 stress.py에 대충 저장해두고, 같은 폴더에 WA를 받는 solve.c++ 코드와 새로 짠 naive.c++ 코드, 그리고 input generator를 담당하는 input.c++ 코드를 넣고 stress.py를 실행하면 자동으로 generator의 input으로 stress test를 돌려준다.
이렇게 solve와 naive 코드를 분리하면 위에서 나온 문제점들을 다 해결할 수 있다. 유일한 문제점은 "귀찮다"인데, 템플릿 코드가 짧은 편이고 어차피 stress test를 해야할 시점이면 이정도의 귀찮음이 크게 문제가 되지 않을 상황일테니 괜찮을 거라고 생각한다.
2. 사소한 tactic들
필자가 위 템플릿으로 stress test를 돌려보면서 얻은 잡기술들이다.
2.1 tqdm 모듈을 쓰면 test의 진행상황을 쉽게 볼 수 있다.
...
from tqdm import tqdm
...
for i in tqdm(range(100000)):
....저렇게 쓰면 된다. 이걸 실행하면
이런 식으로 progress bar가 뜬다. 다만 나이브를 잘 짰다면 보통 반례가 빠르게 나오니 굳이 필요하진 않고, tqdm은 설치해야 하는 모듈이라 대회장에서도 못쓴다. 그래도 solve를 옳게 고치고 돌렸을 때 progress bar가 오르는 걸 보면 기분이 좋아진다!
2.2 input generator를 이렇게 짜면 망한다.
#include <bits/stdc++.h>
using namespace std;
int main(){
srand(0x1557);
int input = rand();
...
cout << input << "\n";
}위 코드는 안타깝게도 팀연습 중 l 모 군이 실제로 짰던 input.c++ 코드이다. 무엇이 문제인지 맞춰보자.
현재 random 함수의 seed로 0x1557을 고정으로 넣고 있는데, 이러면 input.c++에서 나오는 값이 매번 같아진다!! stress test의 목적은 무수히 많은 테케를 마구 넣어보면서 반례를 찾는 것인데, 이러면 동일한 테케로 애꿎은 실행만 10만번을 하게 된다.
다행히도 같이 팀연습 중이던 s 모 군이 금방 이 블런더를 발견했고, 코드를 아래처럼 수정했다.
#include <bits/stdc++.h>
using namespace std;
int main(){
srand(time(0));
int input = rand();
...
cout << input << "\n";
}
하지만 안타깝게도 이 코드에도 문제점이 있다. 한번 맞춰보자.
seed로 time(0)을 넣으면 매번 input.c++의 결과가 달라지는 듯 싶지만, time(0)의 값은 1초마다 바뀌기에 결국 1초에 하나씩 테케를 넣는 것과 다름이 없어진다. 잘 짠 stress test는 1초에 최소 1000개의 서로 다른 테케로 실행을 할 수 있기에, time을 seed로 쓰면 효율이 1/1000으로 줄어든다고 말해도 과언이 아니다.
그럼 이걸 어떻게 고쳐야하느냐. 필자는 아래 방식을 추천한다.
#include <bits/stdc++.h>
using namespace std;
int main(){
int SEED; cin >> SEED;
srand(SEED);
int input = rand();
...
cout << input << "\n";
}이러고, stress.py에서
...
for i in range(100000):
inp = sh(["./input"], str(i))
...로 직접 0부터 10만까지 seed를 직접 넣어주자. 매 실행마다 seed가 다르니 효과적으로 random input을 만들어줄수 있다. 이 방식은 좋은 장점이 또 하나 있는데, stress test에서 i=T일때 반례가 나왔다고 가정해보자. 이 반례를 기반으로 디버깅을 한 후 같은 반례에서 코드가 잘 돌아가는지 확인을 하고 싶을텐데, 위 방식은 seed만 같으면 테케가 그대로 보존이 되니 확인이 아주 편리하다. 또, 랜덤 테케 대신 모든 i=0...N까지 다 확인을 해보고 싶은 경우, inp = str(i)로 input.c++ 없이 직접 넣는 센스를 발휘해보자.
2.3 naive 코드를 잘 짜자
당연한 소리인데, 생각보다 지키기 힘든 법칙이다. stress test까지 동원되는 경우는 보통 대회가 멸망 직전 상태일 때가 많기에, 멘탈이 온전치 못할 때가 많다. 급한 마음으로 naive를 짜다가 실수를 하고, 그대로 stress test를 돌리다가 또 오류가 생기면서 디버깅할게 많아지기도 한다. naive를 짤 때는 그냥 무조건 맞는 코드를 짠단 마인드로 차분하게 짜고, 예제도 다 넣어보면서 꼼꼼하게 짜자.
마찬가지로 input generator도 차분하게 짜서 잘 돌아가는지 확인을 해보자.
2.4 special judge / interactive에서 stress test?
스페셜 저지의 checker가 짜기 매우 쉬운 경우, 그냥 stress.py 코드에서 직접 checker를 구현하면 된다. 만약 그렇지 않은 경우 check.c++를 추가로 구현해서 하면 되는데, 이때부터는 stress test를 위한 cost가 좀 커져서 필자는 선호하지 않는다. checker의 기준을 조금씩 완화해가면서 반례 날먹 각을 먼저 보고(ex. 출력한 답 array의 크기만 비교), 그래도 도무지 답이 나오지 않는다면 최후의 수단으로 checker를 짜자.
interactive 문제의 경우는 아예 얘기가 다른데, 이건 오히려 naive와 solve를 같은 코드에 구현하는 게 더 좋을 때가 많은 것 같다.
int Query(int args){
if(LOCAL) return naive(answer, args);
cout << args << endl;
int res; cin >> res;
return res;
}이런 식으로 LOCAL용 쿼리 응답기를 만든 후, 최종적으로 나온 답이 answer와 같은지를 확인하는 게 더 효과적인 것 같다. 이후 stress test를 위해 input generator로 answer를 직접 넣어주면 된다. 이건 필자도 아직 최적화를 완전히 시켜놓지 않았으니 알아서 걸러듣자.
3. 좋은 input 만들기
- input의 크기는 가능한 작게 하자. 결국 반례는 디버깅을 하기 위함이고, 작은 n이 훨씬 디버깅이 쉽다.
- 반대로 UB가 나는 반례를 찾고 싶을때는 input을 최대한 크게 만들자. ub 위치는 sanitizer로 찾으면 된다.
- input으로 tree를 만들어야 할땐,
1을 루트로 잡고, 각 i = 2...N을 원래 트리 밑에 붙이는 식으로 하면 편하다. i와 randint(1, i-1)을 이어주자.
루트 1이 맘에 안든다면, 적당한 D를 잡아서 노드 번호를 밀어주자.
- randint 대신 10^rand(0, logN)을 쓰는걸 고려해보자. 생각보다 유용하다.
- 그 외에도 문제마다 적절히 센스있게 잘 input을 만들어보자. 설명하기는 뭔가 힘들고, 그냥 많이 해보는게 정석 같다.
4. stress 쌀먹각은 이럴때
- naive 코드를 짜기 매우 쉬울때
ex) O(NlogN) 풀이는 온갖 더러운 걸 해야하지만, O(N^3)은 딸깍 DP로 금방 짤 수 있을 때. 혹은 O(2^N) 완탐.
- 이미 WA를 몇번 받았고, 반례가 쉽게 안 잡힐때, 혹은 반례가 파도파도 계속 나올때.
그리디 문제가 특히 저렇다. 그게 아니더라도 문제에서 "찍기"가 강요될 때 매우 유용하다.
- 케웍이나 구현이 너무 복잡해서 도무지 한번에 맞을 자신이 없을 때. 혹은 스코어보드에 불기둥이 그려져있을때.
Ex) UCPC 25 H번. changhw님이 풀이를 완성하기도 전에 내가 먼저 stress code와 checker를 전부 짜놨었다. 그 결과 미친 패널티 관리로 전체 2등을 할 수 있었다.
- 코딩하는 사람이 실수가 많고 멘탈이 약할 때
그 외에도 다양한 각이 있지만 생략하겠다.
개인적으로 위의 각들이 잘 부합하고, 어려운 문제인 경우 아예 제출 전에 stress test를 돌리고 내는 것도 꽤 괜찮다고 생각한다. 어차피 stress를 위해 소모되는 시간이 별로 크지 않고(잘 짜면 3분 이내인듯), 한번 틀릴때마다 생기는 패널티가 20분인걸 생각하면 상당히 optimal한 전략이다. 실제로 17년도 molamola 팀이 서울 리저널을 칠 당시, 셋이 쉬워서 올솔 + 패널티로 우승자가 정해지는 상황이 왔고, 대충 다이아부턴 내기 전에 stress test로 AC임을 확실히 보장 후 제출을 했다고 한다. PhoKing의 경우 다행히도 월파에서 푼 문제 대부분이 1트컷이었기에 저 전략을 사용할 일이 없었다. 휴~
5. 마치며
stress test는 기본적으로 문제 풀이 과정이 멸망했을 때 등장하기에, 쓸 일이 없는게 가장 좋긴 하다. 하지만 결국 한번씩은 대회장에서 개같이 말리는 일이 올테고, 그때를 대비해서라도 stress test를 능숙하게 다룰 수 있어야 한다고 생각한다. 이 글을 토대로 연습해도 좋고, 그게 아니더라도 자기가 익숙한 방식으로 연습을 해두면 언젠간 위기에 빠진 당신의 팀을 구원해줄 순간이 올 것이라고 믿는다.