tmdghdhkd23   1년 전

다른 언어에서는 sort()와 이진탐색만 써도 시간초과 없이 정답처리가 되나 C++에서는 sort(), 이진탐색, 그리고 추가로 vector까지 사용했음에도 시간초과가 발생합니다. 여기서 시간을 더 줄일 수 있는 방법이 있을까요?

o98123   1년 전

bool binary_search(vector a, int val) 부분을 bool binary_search(vector&a, int val)로 바꾸시면 될 것 같습니다.

bool binary_search(vector a, int val)의 경우에는 vector b를 a라는 새 vector에 O(N)의 시간 복잡도로 복사하게 됩니다. 하지만 bool binary_search(vector&a, int val)의 경우에는 vector b를 a라는 새 vector에 복사하지 않고 vector b를 그대로 사용해 실행 속도가 빨라집니다.

제 필력이 부족해 이해하기 어려우실 수 있지만, 조금이나마 도움이 되었으면 좋겠네요. 👍

tmdghdhkd23   1년 전

해당 매개변수를 새로 생성하지 않고 그대로 사용하는 방법으로도 부족해서 계속 찾아보니 iostream 모듈 사용시 cin, cout만 쓰는 것이 아닌 ios::sync_with_stdio(false); cin.tie(0); cout(0).tie;를 작성해 stduo.h 모듈과의 혼동을 차단한 뒤에 cin과 cout를 사용하는 방법도 사용해야 했습니다. 해결에 도움주어 감사합니다.

o98123   1년 전

입출력 속도 향상도 필요하다는 점을 간과했네요. 도움이 되었다니 다행입니다.

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