onlyhim   6달 전

자꾸 시간초과 / 런타임에러 가 뜨는데

해결방법좀 알수있을까요??ㅠㅠ


indioindio   6달 전

매번 합을 구하는 방식으로는 시간 내에 해결하기가 어려울 것 같습니다.

iljimae   6달 전

안녕하세요! 우선 시간복잡도가 O(WN)이어서 시간초과가 나는 것 같습니다. Prefix sum으로 O(N)만에 합을 미리 구하면 a에서 b 사이의 합은 O(1)만에 구할 수 있습니다. 그리고 이중 루프에서 변수 j를 재사용하는것도 문제가 되는 것 같아요. 

Hibbah   6달 전

20a64fc6c7a4b69b386a663952ac2e73.png

위와 같은 단순한 코드도 10억 번을 반복하면 생각보다 제법 오랜 시간이 필요합니다. (제 컴퓨터에서는 2.5~3.5초 정도 걸리네요)

문제에서 데이터(N)가 최대 10만개, 질의(M)의 수가 최대 10만개라고 했고.. 최악의 경우 매 질의마다 배열 전체 범위 (0~99999)가 입력될 수도 있기때문에

작성하신 솔루션의 경우, M개의 질의마다 N번의 덧셈을 수행하기 때문에 일지매님이 언급해주신 Big-O표기법으로 시간복잡도를 표현하면 O(MN)이 됩니다.

단순히 10억번(10^9)의 덧셈을 수행하는데 3초 정도가 걸리는데, MN번(10^10)의 덧셈을 수행하는데는 더 많은 시간이 걸리겠죠.

또, 상수시간( O(1) )의 연산도 단순한 연산이 아닌 조금 더 시간이 필요한 연산(곱셉, 나눗셈, 함수호출..)이 있을수도 있고, 연산 자체가 많이 포함되어 있을수도 있습니다.

정석적인 방법은 아니지만, 작성한 솔루션을 Big-O로 표현하여 대략적으로 계산한 값에 대해, '1억 == 1초'로 생각하고 문제를 풀면 본인이 작성한 코드가 주어진 시간제한 안에 수행이 가능할지 얼추.. 예측해 볼 수 있습니다.




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