minjun623   5년 전

천만개 이하의 데이터를 입력받아, 배열을 확인한 후 출력 하는 코드인데 왜 시간 초과가 발생할까요?

portableangel   5년 전

그 이유는 1천만 칸의 배열은 캐시에 올릴 수가 없어 지속적인 캐시미스로 인해 배열 접근 자체의 수행시간이 늘어나기 때문입니다.

  1. 훨씬 작은 사이즈의 배열로 체크할 방법을 찾거나
  2. 배열을 아예 쓰지 말고

풀어보세요. 둘 다 가능하고, 둘 다 통과합니다.

djm03178   5년 전

바로 그 천만개의 수를 입력받는 것이 오래 걸립니다. 게다가 방문 배열을 쓸 경우 캐시 미스 확률이 높아 추가적으로 많은 시간이 소요됩니다.

fast I/O를 하거나, O(1)의 공간복잡도로 해결할 수 있습니다.

chogahui05   5년 전

bitset으로 하니 아슬아슬하게 통과하더라고요.

bool type이 c++에서는 1byte일텐데 10M정도면..

1로 갔다 500만으로 갔다가 2로 갔다가 500만 1로 갔다가.. 이런 식의 데이터가 들어오면 

5M씩 껑충껑충 뛰어서 생각보다 시간이 많이 걸릴 거 같아요. ㅋㅋ

testtest4   4년 전

배열을 쓰지 않고 해결하는 방법에는 어떤 알고리즘이 있을까요? 생각을 계속 해보았는데 도무지 떠오르지 않네요..

djm03178   4년 전

1부터 N-1까지의 합 공식을 이용해 보세요.

testtest4   4년 전

아아 감사합니다!!!!

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