2-T. 번 강의 질문 스택 풀이시 시간복잡도
안녕하세요.
강의 잘듣고잇습니다.
단순하게 풀엇을떄 2중 forloop 시간복잡도 O(N^2) . 시간초과 발생하였습니다.
스택 풀이로 하면 통과는 하게되는데,
시간복잡도는 여전히 O(N^2). 인 것 아닌가요?
답변 3
0
안녕하세요 ㅎㅎ
그게 아니고, N+N 이 되는걸까요?
>> 네 맞습니다. 예를 들어 최악의 경우를 생각해봤을 때 저 while문이 최대치로 도는 경우는... 계속해서 pop이 안되는 경우겠죠.
그렇다면 for문으로 N번 돌았을 때 그대로 stack에는 N개가 쌓이다가 마지막 N개에서 POP을 하게 됩니다.
이경우 FOR문 N번, STACK에 쌓인 N개의 요소들을 POP하게 되어 총시간복잡도 2N = O(N)이 되게 됩니다.
감사합니다.
0
안녕하세요!!
만약 4,3,2,5 라는 입력이 주어지면
스택에 3개가 쌓이고, 쌓인 스택에서 while 문을 통해 순서대로 ret 배열에 값을 넣어주게 되니까 N^2 이라 생각했는데
그게 아니고, N+N 이 되는걸까요?
감사합니다.^^
0
안녕하세요 성욱님ㅎㅎ
시간복잡도는 여전히 O(N^2). 인 것 아닌가요?
>>
for(int i = 0; i < n; i++){
cin >> a[i];
while(s.size() && a[s.top()] < a[i]){
ret[s.top()] = a[i]; s.pop();
}
s.push(i);
}음.. 혹시 이게 N^2라고 생각하시는 이유가 있으실까요?
감사합니다.
살구클럽 아이디 없음 문제
0
5
0
1-O 코딩살구클럽 채점관련 질문
0
19
2
히든 테스트 케이스가 사라졌습니다
0
14
1
채점서버 혹시 다른 언어 지원도 가능하게 해주실 수 있나요
1
30
2
살구 클럽 채점 관련 문의(테스트 케이스)
0
29
2
1-H 문제 채점하기 오류
0
19
3
코딩살구클럽 2주차 2-L 문제 채점하기 오류
0
28
2
살구 클럽 채점 관련 문의
0
35
2
코딩 살구 클럽 실전 세션
0
28
2
코딩살구클럽 채점 관련 질문
0
36
2
코딩살구클럽 컴파일에러
0
64
2
5-B
0
46
2
4 - A
0
49
2
코딩살구클럽 입장이 안됩니다
0
108
2
4-F 경우의 수 질문입니다.
0
47
2
코딩살구클럽 가입이 안됩니다.
0
106
2
살구 클럽에 대한 질문있습ㄴ디ㅏ
0
73
1
교안 158페이지 문의드립니다
0
53
2
코딩살구클럽 관련 건의사항
0
148
1
코살에 19942 다이어트 문제에 N의 범위가 빠져있슴니다
0
54
1
진행 방법 질문드립니다!
0
98
2
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
65
2
2주차 개념#12 트리 순회
0
34
2
백준사이트가 종료된다고 합니다.
0
330
2