dong6788   4년 전

안녕하세요, 알고리즘 문제를 풀다가 의문점이 생겨서 고수님들께 질문 드립니다

먼저 사정상 문제를 정확히 공개할 수는 없는 점 양해 부탁드립니다.

input, output 이 100,000개 이하로 이루어진 문제가 있습니다. 입출력은 각각 N<=10^5 개의 long long int입니다.

저는 O(N) 알고리즘을 생각해 코드를 작성하였고, 로컬 테스트 결과 worst case 에서도 알고리즘 부분의 실행시간은 0.1초 이하임을 확인했습니다.

(시간체크는 visual studio 2015 환경에서 clock() 함수를 이용해 진행하였습니다)

그런데 문제는 100,000 개 (long long) int 로 이루어진 데이터를 넣어보면, scanf, printf 를 10만번 도는 데만 몇십 초가 소요됩니다. 문제에는 5초 제한이 있는데 말이죠.

심지어 scanf/printf 는 입출력 방식 중 가장 빠른 축에 속한다고 알고있는데도 이 정도면 뭔가 이상한 것 같아서,

그래서 저 나름대로 가설을 몇 개 세워봤습니다.

  1. 내 컴퓨터의 성능 문제이며 채점 서버는 고성능 처리 능력을 가지고 있으니 괜찮다!
    -> 백준 문제는 아니지만 해당 채점서버에 제 O(n) 코드를 제출했을때 max test_case 가 들어간 경우에 TLE가 뜨는 것을 수차례 확인했습니다 ㅠㅠ
  2. 사실 input / output 에 소요되는 시간은 채점 서버에서 알아서 빠진다!
    -> 그렇다고 하기엔 5초 제한에 알고리즘이 돌아가는 시간이 0.1초도 안되는 점이 뭔가 이상하기도 하고, 무엇보다 TLE가 뜨는 점을 확인했습니다..
  3. 대용량의 input 도 test 해야 하기 때문에 채점서버에서는 fscanf / fprintf 로 알아서 치환되어 사용된다!
    -> 실제로 이 경우에도 로컬에서는 0.1초대로 돌아가는 것을 확인했으나, 채점서버에서 TLE가 난 것을 보면 아닌 듯 합니다..

제가 알기로는 채점서버에 여러 test case 에 대한 input가 정답 data들을 저장해 두고 print 된 유저의 답안과 정답을 계속 비교하는 방식으로 알고 있는데,

그러면 scanf printf 시간도 온전히 포함되는 것인지, 혹은 파일 입출력으로 처리되어 좀 더 빠르게 되는 것인지, 혹은 채점 서버는 고성능 CPU를 사용해 로컬보다 좀 시간을 덜어서 생각해도 되는 것인지 궁금합니다.

만일 로컬에서의 test 시간이 채점 서버에서도 거의 그대로 적용된다면.. 수많은 10만 이상의 input/output 을 가지는 문제들은 최소한 채점 서버가 몇십초 이상씩 할당해야 한다는 말인데, 그렇게 비효율적으로 설계되지는 않았을 것 같아서요.

요약 : 문제를 채점할 때 scanf / printf 에 소요되는 시간도 고스란히 채점시간에 포함되는지가 궁금합니다!!

djm03178   4년 전

입출력 시간 모두 계산이 됩니다. 중요한 건 그걸 어떻게 측정해보셨냐는 것인데, 단순히 콘솔에 입력을 넣고 콘솔로 출력을 해보셨다면 이 콘솔에 내용이 나타나는 것이 매우 오래 걸립니다.

파일 입출력으로 파일에서 읽어 파일에 쓰게 테스트해보셔야 합니디.

dong6788   4년 전

네 안그래도 콘솔이 한참 내려가긴 하더라구요..

그래서 파일 입출력으로도 테스트 해 봤는데 각각의 test case 에 대해서 많아야 0.1~0.2초대이고

전체 tc에 대해서도 50번을 해 봤는데 한번도 1초를 넘지 않았습니다. 그런데도 채점 서버(명시된 조건은 5초)에서는 TLE가 나서 멘붕이네요 ㅠㅠ

다른 의심가는 부분으로는, 현재 코드에 dfs를 recursive 하게 도는 부분이 있는데, 여기서 재귀의 깊이가 최대 100,000 번 내려갑니다.

그래서 콜스택에서 메모리를 꽤 먹기는 할텐데, 그런데 이 경우라면 stack overflow 에러가 떠야하지 왜 TLE가 나는지 잘 모르겠습니다 ㅠㅠ

사실은 메모리 문제인데도 특정 요인으로 인해 로그는 TLE로 뜨는 경우도 있으려나요?

djm03178   4년 전

어느 채점 환경인지 모르기 때문에 정확히는 알 수 없지만, 시간 초과가 아닌 것을 시간 초과로 채점하는 곳은 아마 없을 거라고 생각합니다.

Worst case O(N)이라고 하셨는데 정말로 그게 worst인지 다시 확인해보시는 것이 제일 좋습니다. 예를 들어 quickselect라는 알고리즘은 나이브하게 구현하면 평균 O(N)이지만 최악의 경우 O(N^2)입니다. 시간 복잡도라는 건 단순히 입력량이 많다고 해서 높아지는 것이 아니고 같은 입력량으로도 더 많은 수의 문장이 실행되게 만들어야 합니다.

그리고 코드에 undefined behavior가 있다면 무슨 동작을 할지 모르기 때문에 환경에 따라서 무한 루프에 걸리는 일이 벌어질 수도 있습니다.

dong6788   4년 전

아무래도 코드를 첨부하는게 이해가 빠르실듯 해 제 답안을 첨부합니다.

대강 설명드리면 root가 있고 방향이 존재하는 connected tree graph (모든 edge 의 weight는 1) 에서 K개의 (a,b) 가 주어졌을 때, a->b의 path의 edge의 weight 만 모두 0으로 했을 때

모든 vertex 간 최단 경로의 합이 얼마나 줄어드는지를 구하는 문제입니다.

indexing이 조금 naive 하기는 하지만 문제에서 a, b는 조상->자식 관계가 보장되어 있기 때문에 제 생각으로 엉뚱한 메모리로 튀는 경우는 없는 것 같습니다.

제 코드에서 dfs 를 도는 부분이 두 번 있긴 한데, 총 순회 횟수는 최대 N을 넘지 않기 때문에 O(N)이라고 생각했고, 실제로 다양한 case에 대해 dfs 함수 호출시마다 cnt++; 하여 찍어봤을 때도 N이었습니다. 그 외의 부분은 정말 단순한 반복문이라 의심의 여지 없는 O(N) 이구요.

혹시 어딘가 제가 잘못했거나 혹은 실행시간을 더 줄일 수 있는 여지가 있을까요?

djm03178   4년 전

의심되는 부분이라면 57번째 줄에서 tree[0]을 해제하고 있다는 점이네요. tree[1]부터만 해제해야 할 것 같습니다.

dong6788   4년 전

앗 그러네요.. 번개같이 다녀왔으나 역시 TLE 네요 ㅠㅠ

참고로 말씀드리면 주어진 sample TC와 채점 TC의 숫자가 같아서 동일한 종류일 것 같은데,

3만 정도까지는 맞았다고 처리되다가 N=K=100,000 인 case가 마지막에 3개 있는데 그 부분만 걸리는 듯 합니다. O(N)인데 왜인진 모르겠지만..

그나저나 주말 아침부터 실시간으로 남의 코드 읽고 답변해주시는 djm님 정말 감사합니다 ㅠㅠ

dong6788   4년 전

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWK3jPa6Fv0DFAWJ


채점 서버는 이쪽을 사용했습니다. 무단 복제가 안된다고 써있어서 공개해도 되나 싶었는데, 사외로도 공개된 사이트라 괜찮을 것 같네요

djm03178   4년 전

setbuf(stdout, NULL)이 문제일 것 같습니다. 이 때문에 출력을 할 때마다 flush가 발생해서 매우 느릴 것으로 보입니다.

테케마다 한 번씩만 flush해주면 될 것 같으니, 한 케이스 끝날 때마다 fflush(stdout); 만 해줘도 되지 않을까 싶습니다.

dong6788   4년 전

와 저걸 제거할 생각을 못 해봤네요... 역시나 저 부분 제거했더니 예상대로 런타임 에러(콜스택 오버플로우)가 발생했고, 재귀가 아닌 방식으로 바꾸어 해결했습니다.

템플릿에 꼭 넣으라고 명시가 되어있었는데 flush 비용도 시간에 들어가네요. 덕분에 하나 배워갑니다.

답변 너무너무 감사합니다!

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