wnscjf   2년 전

처음에 def없이 for문 2번쓰는방버으로 해서 시간초과가 떠서 def를 정의해서 해봤는데도 똑같이 시간초과가 뜨네요 ㅠㅠ

어떻게 하면 좋을지 모르겠습니다. 제 생각에는 숫자가 10^9까지 커지면 if문을 하나하나 해보기에는 시간이 오래걸려서 인거같은데 

어떤방법을 써야할지 모르겠네요

bupjae   2년 전

def 안으로 옮겼을 뿐, 이 프로그램도 for 문 내부에 또 다시 for 문이 들어가 있는 형태로, 시간복잡도는 O(n^2) 이 됩니다.

이 문제에서 시간 초과를 보지 않기 위해서는 O(n log n) 알고리즘을 사용해야 합니다.

좀 더 구체적으로는, 5~12번째 줄에서 하고 싶었던 일을 O(n) 이 아닌 O(log n) 으로 수행할 수 있어야 합니다. 

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