Inflearn Community Q&A

asked

10-Week Completion C++ Coding Test | Algorithm Coding Test

2-T

2-T. 번 강의 질문 스택 풀이시 시간복잡도

Resolved

Written on

318

안녕하세요.

강의 잘듣고잇습니다.

단순하게 풀엇을떄 2중 forloop 시간복잡도 O(N^2) . 시간초과 발생하였습니다.

스택 풀이로 하면 통과는 하게되는데,

시간복잡도는 여전히 O(N^2). 인 것 아닌가요?

c++코딩-테스트

Quiz

그래프의 가장 기본적인 구성 요소 두 가지는 무엇일까요?

노드와 무게

간선과 경로

정점과 간선

정점과 무게

Answer 3

Instructor

안녕하세요 ㅎㅎ

그게 아니고, N+N 이 되는걸까요?

>> 네 맞습니다. 예를 들어 최악의 경우를 생각해봤을 때 저 while문이 최대치로 도는 경우는... 계속해서 pop이 안되는 경우겠죠.

그렇다면 for문으로 N번 돌았을 때 그대로 stack에는 N개가 쌓이다가 마지막 N개에서 POP을 하게 됩니다.

이경우 FOR문 N번, STACK에 쌓인 N개의 요소들을 POP하게 되어 총시간복잡도 2N = O(N)이 되게 됩니다.

감사합니다.

Questioner

감사합니다. 큰 도움 되었습니다.

Questioner

안녕하세요!!

만약 4,3,2,5 라는 입력이 주어지면

스택에 3개가 쌓이고, 쌓인 스택에서 while 문을 통해 순서대로 ret 배열에 값을 넣어주게 되니까 N^2 이라 생각했는데

그게 아니고, N+N 이 되는걸까요?

감사합니다.^^

Instructor

안녕하세요 성욱님ㅎㅎ

시간복잡도는 여전히 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라고 생각하시는 이유가 있으실까요?

감사합니다.

asked