-
질문 & 답변
카테고리
-
세부 분야
취업 · 이직
-
해결 여부
해결됨
시간복잡도 질문
22.03.21 17:35 작성 조회수 154
3
안녕하세요.
Stack 2개를 활용하여 Queue를 만드는 시간복잡도 부분에서 질문이 있습니다.
강의에서는 dequeue의 경우에만 outstack이 비어있는 경우와 데이터가 있는 경우를 나누어 각각 O(n), O(1)의 시간복잡도를 말씀해주셨는데요.
dequeue가 일어나고, outstack에 데이터가 남아있는 상태에서 enqueue가 일어날 경우에는 outstack에 남아있는 데이터를 instack으로 다시 옮기는 작업 후에 push를 해줘야하기 때문에 똑같이 enqueue의 경우에도 2가지 경우가 있고, amortized O(1)로 볼 수 있지 않은지에 대한 의문이들어 질문드립니다.
답변을 작성해보세요.
1
0
개발남노씨
지식공유자2022.03.21
안녕하세요 snowdrop6342님 강의 열심히 수강하고 계시면서 질문도 남겨주셔서 기분이 뭔가 좋네요 ㅎㅎ
비슷하지만 다른 두 개의 질문이 있습니다.
Q1.Stack 두 개를 이용하여 Queue를 구현해보세요.
Q2.Queue 두 개를 이용하여 Stack를 구현해보세요
Q1의 질문에서 두 개의 Stack 중 하나는 outstack으로 고정이고, 또 다른 stack은 instack으로 고정입니다. 그래서 남겨주신 의문점인 "outstack에 데이터가 남아있는 상태에서 enqueue가 일어날 경우에는 outstack에 남아있는 데이터를 instack으로 다시 옮기는 작업" 을 할필요가 없습니다. 남아있는 데이터를 instack으로 옮기면 안되고 outstack에 그대로 남아있어야 해서 그렇습니다.
제가 짐작하건데 헷갈릴 수 있었던 이유는, Q2의 질문에 대한 답에서는 두 개의 Queue가 InQueue 또는 OutQueue로 고정되어 있지 않고 매번 변경되어야해서 데이터들이 왔다갔다 하기 때문에, 이와 비슷하게 Q1에서도 데이터를 왔다갔다 계속 옮겨야 하지 않나 생각하신것 같아요.
질문에 대해서 제가 이해한 내용이 맞을까요? 한번 읽어보시고 다른 의견 있으시면 편하게 말씀해 주세요!! 감사합니다 :)
답변 2