daily temperatures 문제 질문

안녕하세요 욱님.

열심히 하시네요 굳굳

충분히 헷갈릴 수 있는 내용이에요.

우리가 시간복잡도를 계산할 때, 이중 반복문이 있으면 n^2이겠거니 많이 생각을 하죠.

그런경우는 다음과 같은 상황이에요.

for i = 1 ~ n :

for j = 1 ~n:

이런경우 의심할 여지없이 n^2번 실행되서 시간복잡도는 O(n^2)이겠죠.

근데 반복문이 이중으로 쓰이긴 했는데, 매 순간 n번 반복하지 않을 때가 있어요. 보통 for + while형태로 많이 출몰합니다.

for i = 1~n :

while 조건문:

이 경우 for 반복문은 n번 반복 되는건 맞죠. 하지만 for문이 한 번 반복할 때 while문을 한번 실행할 텐데, while문은 몇번 반복할지 모르는 상황이요! 그래서 하나씩 따져봐야돼요.

과연 욱님이 말씀하신대로 최악의 상황에서 for 문이 한 번 반복할 때마다 while문이 n번 반복할 수 있을까요? 그럴 순 없어요. 왜냐면 while문을 실행시키면 stack에 저장되어 있는 데이터를 pop 하게 되죠. 그런데 stack에는 저장할 수 있는 데이터가 총 n개의 데이터 뿐이에요. n개의 데이터를 중복해서 stack에 저장할 수 는 없어요. 그러니까 결국 stack에 들어왔다가 나오는(push -> pop)할 수 있는 횟수는 아무리 많아도 n번이겠죠.

즉 for 반복문이 n번 진행되는 와중에 while문은 "총" n번만 실행되는거에요.

시간복잡도가 n^2이 되려면 for 반복문이 n번 진행되는 와중에 while문은 매 순간 n번 반복되어야 "총" n^2번 실행이 되게 되겠죠!!

이게 좀 어려울 수 있는 내용이라, 글을 읽고 이해가 안가신다면 discord로 질문 남겨주세요. 화면공유 해서 설명드릴게요!