시간복잡도 질문
안녕하세요.
Stack 2개를 활용하여 Queue를 만드는 시간복잡도 부분에서 질문이 있습니다.
강의에서는 dequeue의 경우에만 outstack이 비어있는 경우와 데이터가 있는 경우를 나누어 각각 O(n), O(1)의 시간복잡도를 말씀해주셨는데요.
dequeue가 일어나고, outstack에 데이터가 남아있는 상태에서 enqueue가 일어날 경우에는 outstack에 남아있는 데이터를 instack으로 다시 옮기는 작업 후에 push를 해줘야하기 때문에 똑같이 enqueue의 경우에도 2가지 경우가 있고, amortized O(1)로 볼 수 있지 않은지에 대한 의문이들어 질문드립니다.
Answer 2
1
안녕하세요 snowdrop6342님 강의 열심히 수강하고 계시면서 질문도 남겨주셔서 기분이 뭔가 좋네요 ㅎㅎ
비슷하지만 다른 두 개의 질문이 있습니다.
Q1.Stack 두 개를 이용하여 Queue를 구현해보세요.
Q2.Queue 두 개를 이용하여 Stack를 구현해보세요
Q1의 질문에서 두 개의 Stack 중 하나는 outstack으로 고정이고, 또 다른 stack은 instack으로 고정입니다. 그래서 남겨주신 의문점인 "outstack에 데이터가 남아있는 상태에서 enqueue가 일어날 경우에는 outstack에 남아있는 데이터를 instack으로 다시 옮기는 작업" 을 할필요가 없습니다. 남아있는 데이터를 instack으로 옮기면 안되고 outstack에 그대로 남아있어야 해서 그렇습니다.
제가 짐작하건데 헷갈릴 수 있었던 이유는, Q2의 질문에 대한 답에서는 두 개의 Queue가 InQueue 또는 OutQueue로 고정되어 있지 않고 매번 변경되어야해서 데이터들이 왔다갔다 하기 때문에, 이와 비슷하게 Q1에서도 데이터를 왔다갔다 계속 옮겨야 하지 않나 생각하신것 같아요.
질문에 대해서 제가 이해한 내용이 맞을까요? 한번 읽어보시고 다른 의견 있으시면 편하게 말씀해 주세요!! 감사합니다 :)
Open addressing을 사용할 때의 worst case
1
465
1
인터넷 계층과 네트워크 엑세스 계층
1
492
1
패킷이란
1
424
1
Linked list의 장점
1
652
1
노션 자료 이메일 잘못 입력했어요..
1
547
1
동기화 문제
1
503
2
프로세스 관련 질문
1
573
1
노션 전자 책 동영상 문제
1
476
1
안녕하세요 강사님!
1
338
1
노션 공유 요청
1
358
1
Linked List 시간 복잡도
3
750
1
thread의 PC register 질문
1
717
2
hash table의 seperate chaining 질문
0
385
2
인덱스 카디널리티 부분 질문이있습니다.
2
1184
2
프론트엔드 면접준비 질문
0
546
1
시간복잡도
1
269
1
쿠키 질문
0
310
1
쓰레드의 단점 중 궁금한 것이 있습니다.
0
260
1
URL을 주소창에 쳤을 때 화면에 나오기까지의 과정에 대해 추가적으로 궁금합니다.
1
434
1
궁금한게 있습니다
0
205
0
강의자료 HTTP 부분 request 단어가 repuest로 되어있습니다
1
222
1
강의가 이해가 잘되네요
1
250
1
syn 과 fin의 데이터 단위가 다른 이유
2
289
1
Circular Queue에 대해서 질문드려요
1
292
1