strive71   2년 전

왜 계속 시간초과가 날까요...ㅠ

bamgoesn   2년 전

버블 정렬의 시간복잡도는 O(N^2)입니다. 이 문제에서 N은 최대 10,000,000으로 O(N^2)인 알고리즘은 시간 초과를 받습니다.

https://www.acmicpc.net/proble... 우선 이 문제를 통해 O(NlogN) 정렬 알고리즘을 사용하는 방법을 먼저 배우시는 걸 추천드립니다. 이 문제는 사실 일반적인 O(NlogN) 알고리즘도 메모리 제한때문에 힘듭니다. 입력을 저장하기만 해도 40,000,000B = 40MB거든요...

https://www.acmicpc.net/blog/v... 추가로 이 글의 알고리즘 항목에 정렬 관련된 팁이 나와 있는데, 이것도 참고해보세요.

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