baekjoon   4년 전

미리 읽는 결론: 환경이 다르고 데이터의 구성이 다르기 때문에 사용한 시간의 직접적인 비교는 아무 의미가 없습니다.

안녕하세요.

https://www.acmicpc.net/workbo...

위의 문제집(삼성 SW 역량 테스트 기출 문제)에 포함된 모든 문제의 출제자입니다.

관련 문제와 관련해 사용한 시간 및 시간 제한에 대한 의견이 인터넷에 많이 있어서 제 의견을 남깁니다.

먼저, BOJ에서 사용하는 용어와 테스트를 준비하는 사람들이 사용하는 용어가 조금 다르기 때문에, 이 부분부터 정리해봅니다.

  • 문제에 나와 있는 예제 입/출력
    • BOJ: 예제
    • 테스트: 테스트 케이스 (테케)
  • 채점할 때 사용하는 데이터 입/출력
    • BOJ: 채점 데이터
    • 테스트: 히든 테스트 케이스 (히든테케)

첫 번째로 BOJ는 단일 테스트 케이스 방식(1000번: A+B 같은 방식)을 선호하고 있고, 위의 테스트는 테스트 케이스 방식(10950번: A+B - 3 같은 방식)을 사용하고 있습니다.

BOJ는 한 데이터당 사용한 시간의 최댓값을 사용한 시간으로 사용하고 있고, 테스트는 단일 데이터에 여러 개의 테스트 케이스를 넣고 한 번만 실행시키고, 그 시간이 사용한 시간이라고 추정하고 있습니다.

BOJ의 걸린 시간 * (테스트에서 사용한 것으로 추정되는 테스트 케이스의 수)와 테스트의 시간 제한을 비교해서 시간 초과여부를 판단하는데 이 방식은 전혀 의미가 없습니다. 의미가 없는 이유는

  1. 두 프로그램이 실행된 환경이 다릅니다.
  2. BOJ의 사용한 시간은 최댓값입니다. 테스트의 단일 데이터가 모두 가장 큰 제한을 이용해서 만들지 않았을 수도 있습니다.
    1. 예를 들어, N 제한이 2 ≤ N ≤ 1,000,000인 경우 BOJ는 대부분 N = 1,000,000인 경우의 시간이 사용한 시간이 됩니다. 
    2. 하지만, 테스트는 여러 개의 N이 포함되어 있을 수 있기 때문에, 테스트 케이스의 구성에 따라서 사용한 시간이 매우 크게 다를 수 있습니다.

따라서, BOJ에서 맞은 소스가 테스트에서는 시간 초과가 날 수도 있고, BOJ에서 시간 초과가 난 소스가 테스트에서 맞을 수도 있습니다.

두 번째로 BOJ는 연습하는 곳, 테스트는 시험입니다.

시험에서는 맞았습니다/시간 초과만이 의미가 있지만, BOJ는 맞았을 때 걸린 시간을 보는 것도 매우 크게 의미가 있습니다. 같은 "맞았습니다"도 방식에 따라서 시간이 매우 크게 다를 수 있기 때문입니다.

연습하는 곳인 BOJ에서는 소스 코드의 일부를 변경했을 때 시간의 변화를 보는 곳이 매우 크게 의미가 있습니다. 따라서, 테스트에서 통과한 것으로 추정되는 소스만 "맞았습니다"를 받게 시간 제한을 수정하는 것이 BOJ에게는 의미가 없습니다.

마지막으로 BOJ와 테스트는 채점 데이터의 구성도 당연히 다를 것이고, 데이터의 개수도 BOJ쪽이 많기 때문에, 두 곳에서의 결과가 같지 않을 수도 있습니다. 예를 들면, BOJ에서는 틀린 소스가 테스트에서는 맞을 수도 있고, BOJ에서는 맞은 소스가 테스트에서는 틀릴 수도 있습니다.

BOJ에서는 사용한 시간이 의미가 있기 때문에, 이 문제에 대한 시간 제한 수정 요청 이유가 "테스트에서 시간 초과날 것으로 추정되는 소스가 맞았습니다를 받았습니다" 라면 시간 제한을 수정하지 않고 요청을 거절합니다.

    jh05013   4년 전

    https://www.acmicpc.net/workbook/view/1152 에 이 글로 링크가 걸리면 좋을 것 같습니다.

    startlink   4년 전

    안그래도 그렇게 만드려고 노력하고 있습니다.

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