인프런 커뮤니티 질문&답변
작성한 질문수
1-H 질문 있습니다!
작성
·
217
0
선생님 안녕하세요 !
제가 푼 문제 코드는 다음과 같습니다.
http://boj.kr/3475d11fa8a2499bba282e226bdc5e92
제가 풀었을 떄는 시간초과가 났었습니다.
여기서 여쭤볼 것이 있습니다.
Q1. 제가 작성한 코드에서 시간 복잡도를 계산할 떄 최악의 수를 생각하고 계산을 합니다. N이 100,000이고 K는 1일 떄 제가 작성한 코드는 대략 3N의 시간복잡도가 나오는 것으로 계산하였습니다. 또한 선생님의 풀이를 저는 2N의 시간복잡도로 생각을 합니다. 그러면 만일 실전에서 제가 작성한 3N이 시간 초과가 뜬다면 2N으로 줄일 방안을 생각하는 것이 맞을까요?!?
답변 1
0
큰돌
지식공유자
안녕하세요 ㅎㅎ
Q1. 제가 작성한 코드에서 시간 복잡도를 계산할 떄 최악의 수를 생각하고 계산을 합니다. N이 100,000이고 K는 1일 떄 제가 작성한 코드는 대략 3N의 시간복잡도가 나오는 것으로 계산하였습니다.
>> 이코든 3N이 아닙니다.
for(int j=0;j<N-K+1;j++){
int ho=j;
for(;ho<j+K;ho++){지금 보면 n과 k가 중첩으로 반복문이 작동됩니다.
이는 (N - K + 1) * K 라고 할 수 있습니다.
예를 들어 N이 10만, K가 5만이라고 한다면,
5만번 * 5만번정도 작동하지 않을까요?
제가 작성한 3N이 시간 초과가 뜬다면 2N으로 줄일 방안을 생각하는 것이 맞을까요?!?
>> 네 맞습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.