인프런 커뮤니티 질문&답변
작성한 질문수
daily temperatures 문제 질문
작성
·
448
5
안녕하세요! Leetcode daily temperature 문제 해설을 보다 질문이 생겨서 남깁니다!
while 문으로 stack을 돌면서 대소 비교를 하는데, 여기서의 시간복잡도가 O(n)이 될 걱정은 안해도 되나요?
어렴풋이 생각하기에, stack에 temperatures의 원소가 들어가기 때문에 n개의 원소가 들어갈 것이고, for문으로 길이가 n인 temperatures를 돌면 결과적으로 worst case로 O(n^2)이 될 수도 있지 않나 ... 라는 생각이 들었습니다.
시간복잡도 개념이 아직 부족해서 헷갈리는 것 같은데 제가 어떤 부분을 간과했을까요?
답변 1
5
안녕하세요 욱님.
열심히 하시네요 굳굳
충분히 헷갈릴 수 있는 내용이에요.
우리가 시간복잡도를 계산할 때, 이중 반복문이 있으면 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로 질문 남겨주세요. 화면공유 해서 설명드릴게요!