pmon2648   2년 전

어떻게 시간초과를 안하게 다룰 수 있나요,,,

yukariko   2년 전

다양한 방법이 있겠지만 저는 정렬, 이진 탐색으로 해결했어요

Hibbah   2년 전

입력 데이터의 크기에 대한 프로그램의 수행시간 분석이 필요합니다.

일반적으로 1억 번의 기본연산(덧셈, 할당, 비교연산... 등)을 수행하는데 소요되는 시간을 1초로 생각합니다.

예를 들어, 아래의 코드는 제 PC에서 release모드로 0.028초가 나오네요.

작성하신 소스는 최대 10억 개의 숫자를 입력받아 배열 input[]에 저장하고, 또 검색 대상 숫자를 최대 10억 개를 받아서 배열 compare[]에 저장한 뒤,

compare[]에 있는 숫자를 하나씩 차례대로 input[]배열에서 찾아서 존재 여부를 출력하는 것으로 보입니다.

여기서, 이 문제에 대한 최악의 입력에 대한 예시로.

input[]에는 10만 개의 숫자가 모두 3이 입력되고, compare[]에는 10만 개의 숫자가 모두 1이 입력된다고 해봅시다.

찾을 대상 숫자가 1인데 input[]에는 1이 존재하지 않으므로, 프로그램은 input[]배열의 처음부터 끝까지 10만 개의 데이터에 대해 비교연산을 수행하게 됩니다.

그런데, compare[]의 크기도 10만개 이므로, 결론적으로 10만 번의 비교연산을 10만 번 수행하게 됩니다.

간략하게 요약하자면, 각각의 최대 크기가 10만인 변수 limit_compare, limit_input에 대해 반복문을 이중으로 수행하므로

작성하신 소스의 최악의 연산 수는 10만*10만 == 100억 번임을 알 수 있습니다.

결국 문제에서 요구하는 제한시간 이내에는 통과하기 힘든 소스입니다.

혹시 잘 모르겠거나 좀 더 힌트를 얻고 싶으시다면 또 알려드리겠슴니다

화이팅하십셔! 

appa   2년 전

해슁을 이용하여 문제를 해결할 수도 있습니다.

소스 첨부합니다~

appa   2년 전

해쉬값을 더 큰 값으로 하면 더 빨라질 줄 알았는데 꼭 그렇지도 않군요.... 1018이 940509보다 빠르다니..

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