daily temperatures 문제 질문
523
작성한 질문수 3
안녕하세요! 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로 질문 남겨주세요. 화면공유 해서 설명드릴게요!
노션 공유 링크
0
92
2
수업 중간에 내주신 문제는 해답을 알 수 없는걸까요?
0
79
2
최신 강의와 비교
0
88
2
Min Cost Climbing stairs 질문
0
77
2
노션 공유 부탁드립니다!
1
89
2
for 문에 sort 함수 를 사용하면
1
91
2
노션 공유 부탁드립니다.
0
105
2
디스코드가 올바르지 않다고 뜹니다..!
0
107
1
그래프
0
100
2
노션 공유
1
123
2
시간복잡도 질문
2
125
3
11강 질문
1
78
2
노션 공유 부탁드립니다
0
84
2
linkedList - BrowserHistory 코드 질문
0
77
1
list1.append(list2)와 list1.append(list2[:])의 차이가 무엇인가요?
1
169
1
라이브러리 사용
1
137
2
문제 교재는 따로 없는 거 맞나요?
1
202
2
LCA 관련해서 질문이 있습니다.
1
118
2
[Unique Paths] 완전탐색 / DP (후반부)
0
108
1
dp 계단오르기최소비용질문입니다.
0
109
1
Dynamic Array 의 size 정보가 저장되는 곳
2
161
2
노션공유가 안된듯 합니다
1
165
2
[코테 적용] 👉 [3번 문제] 완전탐색 (DFS, BFS) (전반부)
1
122
1
강의자료 만들 때 사용하신 프로그램이 뭘까요?
1
205
1