1-H 질문 있습니다!
283
작성한 질문수 6
선생님 안녕하세요 !
제가 푼 문제 코드는 다음과 같습니다.
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점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
코딩 살구클럽 가입 문의
0
66
2
코딩살구클럽 가입문의
0
69
2
3-K private case 질문
0
64
2
안녕하세요. 코딩살구클럽 문의드립니다!
0
77
2
7:41 듣다가 질문합니다
0
77
2
코드 리뷰 요청드립니다!
0
83
2
코딩살구클럽 계정 문의
0
79
2
SK하이닉스 대비 강의수강
0
217
3
코딩살구클럽 등록부탁드립니다.
0
78
2
7-F 재귀로 풀시 런타임애러
0
74
1
1-N 문제 질문입니다. (+ 채점오류)
0
82
2
코딩살구클럽 가입 확인 부탁드립니다.
0
86
2
직장인 코테 합격 공부방법 문의
0
127
2
코딩살구클럽 가입 방법
0
96
2
6-H 체점 관련 질문
0
74
1
채점서버 연결 관련 질문입니다
0
101
2
삼성 s직군
0
88
1
삼성 코테 없어짐
0
212
1
코딩살구클럽 가입부탁드립니다
0
87
2
코딩살구클럽 가입 요청 확인부탁드립니다
0
69
2
5-S 테스트 케이스 질문
0
78
2
코살 문제풀이 환경
0
88
2
2 - T 오큰수 문제가 있는 것 같습니다.
0
81
1
추천 추가문제들
0
74
2