오타/오역/요청 게시판에 올라오는 글들에 대해 자주 언급하게 되는 사항들에 대해 정리해 보았습니다.
0. 질문은 질문 게시판에
오타/오역/요청 게시판은 관리자의 권한이 필요한 요청 사항들을 올리는 곳입니다. 코드의 어디가 틀렸는지, 반례는 무엇인지 등의 질문은 질문 카테고리에 올려주세요. 예제부터 이상하게 느껴지는데 많은 사람들이 맞았다면 문제가 잘못되었을 가능성은 거의 없으니, 질문으로 먼저 물어보세요.
1. 틀려야 할 코드의 제출 번호
오타/오역/요청 게시판 공지사항에 강조되어 적혀 있습니다. 데이터 추가 요청 시에는 이 데이터가 어떤 제출을 틀리게 만들어야 하는지 꼭 알려주세요. 본문에 코드를 올리는 것이 아니라, 실제로 통과된 그 제출이 뭔지 제출 번호나 링크를 알려주셔야 됩니다(코드 공유 기능 X). 가능하면 그 코드는 공개로 설정해서 정말 그 데이터가 그 제출을 틀리게 만들 수 있는지 다른 사람들도 검증할 수 있게 해주시면 좋습니다.
지금은 모든 변수에 대한 입력 범위가 명확하게 제시되는 것이 당연한 것으로 여겨지지만, 테스트 케이스의 수의 경우에는 불과 10년 전만 하더라도 그렇지 않았습니다. 단순히 질이 낮은 대회들뿐만이 아니라 비교적 크고 전통이 있는 대회들(ICPC 등)에서도 테스트 케이스의 수 제한만큼은 제시가 안 되어있는 경우가 많았습니다. 이러한 경우 대개는 "출제자가 의도한 수준의 시간 복잡도를 가진 풀이를 작성했다면 웬만하면 통과되게 해주겠다" 정도의 의미를 내포합니다.
그러면 지금이라도 명시를 하면 괜찮지 않겠나 생각할 수 있는데, 여기에는 문제가 있습니다. 예를 들어 N 제한이 최대 100만인, 의도된 풀이가 O(NlogN)인 문제가 있다고 합시다. 이러한 문제에 N이 100만인 테스트 케이스를 1000개 넣는다면 아무리 효율적인 프로그램이라고 하더라도 분 단위의 시간이 걸리게 될 것입니다. 그런데 실제로 이런 문제들에는 테스트 케이스의 수가 수백, 수천 개인 경우들이 있습니다. 다만 N이 100만인 것을 그만큼 넣는 것이 아니라, 훨씬 작은 N들에 대해서만 그렇게 많은 수의 케이스를 한 번에 채점하고, N이 최대에 가까운 경우에는 케이스의 수를 그만큼 작게(보통은 N이 최대인 경우 케이스는 1개만) 하는 방식으로 "상식적인" 수준을 유지하는 방식을 취합니다.
그렇기 때문에 단순히 테스트 케이스의 수가 최대 몇 개임을 명시하는 것은 많은 경우 문제의 제한을 명확하게 알려주는 데에 큰 도움이 되지 못합니다. 테스트 케이스의 수 제한을 명시하는 순간, 이 "출제자의 의도"가 깨지지 않는 다른 제한들, 예를 들면 "한 파일에서의 N의 총합은 얼마 이하이다" 등을 함께 추가해주어야만 하는데, 이 "출제자의 의도"와 어느 정도까지 통과되기를 원했는지 등을 명확히 알아내는 것은 매우 어렵고 번거로운 일입니다. 그래서 이 부분에 대한 현재까지의 합의는 보통 "이대로 두는 것이 출제자의 의도를 살리는 최선의 방법"입니다.
3. 입력의 마지막의 개행 문자
무조건 있어야 하는 것이 맞습니다. 만일 입력의 마지막이 개행 문자로 끝나지 않았다면 그건 그 데이터가 잘못된 것이므로 수정 요청을 올리면 됩니다. 각 '줄'의 뒤에는 항상 개행 문자가 오는 것이 전제된 사항이고 이는 '줄'을 설명할 때 포함할 필요가 없습니다. 그렇기 때문에 "각 줄에 개행 문자가 포함될 수 있는지 등을 명시해야 합니다"와 같은 요청은 잘못된 요청입니다.
4. 조건 그 자체를 확인
"조건대로라면 이렇게 해도 맞아야 하는데 틀립니다"와 같은 것은 맞왜틀에 불과합니다. 정말로 입력 내용이 문제에 제시된 조건과 상이한 것 같다면, 입력을 받자마자 조건에 위배되지 않는지 그 자체를 검사하는 구문(assert 등)을 넣어서 확인하고, 그 확인용 제출 코드를 공개 설정하여 링크로 올려주세요.
5. 틀려야 할 데이터를 제시
"이 코드의 로직이 잘못되었는데 통과됩니다"와 같은 문구만으로는 실제로 그 로직을 틀리게 만들 수 있는 데이터가 존재하는지 알 수 없습니다. 겉으로는 이상해 보이는 로직이어도 정답을 도출하는 데에는 영향을 주지 않을 수도 있습니다. 실제로 그 코드가 오답을 출력하게 만드는 입력과 그에 대한 올바른 정답을 요청글에 함께 제시해 주세요.
실행한 환경이 다르면 동작, 특히 수행 시간이 크게 달라질 수 있습니다. 단순히 컴퓨터의 성능 차이도 있겠지만, 윈도우와 리눅스, Visual Studio와 GCC는 여러 방면에서 차이를 내며, 특히 디버깅에 관련된 최적화 여부는 수십 배 이상의 시간 차이도 낼 수 있습니다. 100 ms에 통과된 코드가 내 컴퓨터에서는 평범한 데이터에 10초가 걸렸다면 최적화 옵션을 적절하게 주었는지를 먼저 확인해 보세요.
djm03178 2년 전 17
(이 글은 저의 주관적인 의견이며, BOJ의 공식적인 입장이 아닙니다.)
오타/오역/요청 게시판에 올라오는 글들에 대해 자주 언급하게 되는 사항들에 대해 정리해 보았습니다.
0. 질문은 질문 게시판에
오타/오역/요청 게시판은 관리자의 권한이 필요한 요청 사항들을 올리는 곳입니다. 코드의 어디가 틀렸는지, 반례는 무엇인지 등의 질문은 질문 카테고리에 올려주세요. 예제부터 이상하게 느껴지는데 많은 사람들이 맞았다면 문제가 잘못되었을 가능성은 거의 없으니, 질문으로 먼저 물어보세요.
1. 틀려야 할 코드의 제출 번호
오타/오역/요청 게시판 공지사항에 강조되어 적혀 있습니다. 데이터 추가 요청 시에는 이 데이터가 어떤 제출을 틀리게 만들어야 하는지 꼭 알려주세요. 본문에 코드를 올리는 것이 아니라, 실제로 통과된 그 제출이 뭔지 제출 번호나 링크를 알려주셔야 됩니다(코드 공유 기능 X). 가능하면 그 코드는 공개로 설정해서 정말 그 데이터가 그 제출을 틀리게 만들 수 있는지 다른 사람들도 검증할 수 있게 해주시면 좋습니다.
2. 테스트 케이스의 개수
https://www.acmicpc.net/board/... 에 간략하게 설명되어 있지만, 여기서 조금 더 자세하게 이야기해보려 합니다.
지금은 모든 변수에 대한 입력 범위가 명확하게 제시되는 것이 당연한 것으로 여겨지지만, 테스트 케이스의 수의 경우에는 불과 10년 전만 하더라도 그렇지 않았습니다. 단순히 질이 낮은 대회들뿐만이 아니라 비교적 크고 전통이 있는 대회들(ICPC 등)에서도 테스트 케이스의 수 제한만큼은 제시가 안 되어있는 경우가 많았습니다. 이러한 경우 대개는 "출제자가 의도한 수준의 시간 복잡도를 가진 풀이를 작성했다면 웬만하면 통과되게 해주겠다" 정도의 의미를 내포합니다.
그러면 지금이라도 명시를 하면 괜찮지 않겠나 생각할 수 있는데, 여기에는 문제가 있습니다. 예를 들어 N 제한이 최대 100만인, 의도된 풀이가 O(NlogN)인 문제가 있다고 합시다. 이러한 문제에 N이 100만인 테스트 케이스를 1000개 넣는다면 아무리 효율적인 프로그램이라고 하더라도 분 단위의 시간이 걸리게 될 것입니다. 그런데 실제로 이런 문제들에는 테스트 케이스의 수가 수백, 수천 개인 경우들이 있습니다. 다만 N이 100만인 것을 그만큼 넣는 것이 아니라, 훨씬 작은 N들에 대해서만 그렇게 많은 수의 케이스를 한 번에 채점하고, N이 최대에 가까운 경우에는 케이스의 수를 그만큼 작게(보통은 N이 최대인 경우 케이스는 1개만) 하는 방식으로 "상식적인" 수준을 유지하는 방식을 취합니다.
그렇기 때문에 단순히 테스트 케이스의 수가 최대 몇 개임을 명시하는 것은 많은 경우 문제의 제한을 명확하게 알려주는 데에 큰 도움이 되지 못합니다. 테스트 케이스의 수 제한을 명시하는 순간, 이 "출제자의 의도"가 깨지지 않는 다른 제한들, 예를 들면 "한 파일에서의 N의 총합은 얼마 이하이다" 등을 함께 추가해주어야만 하는데, 이 "출제자의 의도"와 어느 정도까지 통과되기를 원했는지 등을 명확히 알아내는 것은 매우 어렵고 번거로운 일입니다. 그래서 이 부분에 대한 현재까지의 합의는 보통 "이대로 두는 것이 출제자의 의도를 살리는 최선의 방법"입니다.
3. 입력의 마지막의 개행 문자
무조건 있어야 하는 것이 맞습니다. 만일 입력의 마지막이 개행 문자로 끝나지 않았다면 그건 그 데이터가 잘못된 것이므로 수정 요청을 올리면 됩니다. 각 '줄'의 뒤에는 항상 개행 문자가 오는 것이 전제된 사항이고 이는 '줄'을 설명할 때 포함할 필요가 없습니다. 그렇기 때문에 "각 줄에 개행 문자가 포함될 수 있는지 등을 명시해야 합니다"와 같은 요청은 잘못된 요청입니다.
4. 조건 그 자체를 확인
"조건대로라면 이렇게 해도 맞아야 하는데 틀립니다"와 같은 것은 맞왜틀에 불과합니다. 정말로 입력 내용이 문제에 제시된 조건과 상이한 것 같다면, 입력을 받자마자 조건에 위배되지 않는지 그 자체를 검사하는 구문(assert 등)을 넣어서 확인하고, 그 확인용 제출 코드를 공개 설정하여 링크로 올려주세요.
5. 틀려야 할 데이터를 제시
"이 코드의 로직이 잘못되었는데 통과됩니다"와 같은 문구만으로는 실제로 그 로직을 틀리게 만들 수 있는 데이터가 존재하는지 알 수 없습니다. 겉으로는 이상해 보이는 로직이어도 정답을 도출하는 데에는 영향을 주지 않을 수도 있습니다. 실제로 그 코드가 오답을 출력하게 만드는 입력과 그에 대한 올바른 정답을 요청글에 함께 제시해 주세요.
6. 범위에 포함되지만 존재할 수 없는 입력
변수의 기본 상하한이 주어졌다고 해서 그 범위 내의 모든 입력이 반드시 존재할 수 있어야만 하는 것은 아닙니다. https://djm03178.tistory.com/3... 를 참고하세요.
7. 실행 환경의 차이
실행한 환경이 다르면 동작, 특히 수행 시간이 크게 달라질 수 있습니다. 단순히 컴퓨터의 성능 차이도 있겠지만, 윈도우와 리눅스, Visual Studio와 GCC는 여러 방면에서 차이를 내며, 특히 디버깅에 관련된 최적화 여부는 수십 배 이상의 시간 차이도 낼 수 있습니다. 100 ms에 통과된 코드가 내 컴퓨터에서는 평범한 데이터에 10초가 걸렸다면 최적화 옵션을 적절하게 주었는지를 먼저 확인해 보세요.
8. Undefined Behavior
코드에 undefined behavior가 있다면 다른 데에서는 틀려도 채점 서버에서는 맞을 수도 있습니다. 로컬에서 틀리는 원인이 undefined behavior라면 그러한 데이터가 없다고 확정지으면 안 되고, 있음에도 불구하고 채점 서버에서는 운 좋게 틀리지 않는 방향으로 컴파일이 됐을 가능성을 생각해야 합니다. 비슷한 데이터가 없는지를 먼저 조건을 확인하는 제출로 조사해보는 것도 좋습니다.