게시판 인덱스

 
 FAQFAQ   검색검색   멤버리스트멤버리스트   사용자 그룹사용자 그룹   사용자 등록하기사용자 등록하기 
 개인 정보개인 정보   비공개 메시지를 확인하려면 로그인하십시오비공개 메시지를 확인하려면 로그인하십시오   로그인로그인 

HW2 4번 질문드립니다.

 
글 쓰기   답변 달기     게시판 인덱스 -> 4190.310 Programming Languages (Spring 2021)
이전 주제 보기 :: 다음 주제 보기  
글쓴이 메시지
염준영



가입: 2021년 3월 14일
올린 글: 23

올리기올려짐: 2021년3월16일 15:24    주제: HW2 4번 질문드립니다. 인용과 함께 답변

과제 2 4번에 보면 두 개의 스택으로 큐를 구현하라고 되어 있는데, 그 밑 문단에는 L과 R을 리스트라고 언급하시는데, 이는 리스트를 스택처럼 사용(리스트의 헤드를 스택의 맨 위로 해석)하라는 뜻인가요?

그리고 큐에 넣고 빼는 작업이 거의 한 스텝에 이루어진다고 되어 있는데,
밑 설명에서 "리스트를 뒤집는어서 넣는" 작업은 O(n)의 시간이 걸리고,
찾아본 결과 스택을 가지고 Worst-case constant time의 큐를 구현하는 방법은
6개의 스택을 사용하거나, 3개의 스택과 lazy evaluation을 사용한 알고리즘(https://stackoverflow.com/questions/5538192/how-to-implement-a-queue-with-three-stacks)이 알려져 있다고 하는데, 4번 문제에서 말씀하신 "거의 한 스텝"은 amortized O(1) 을 뜻하는 건가요?
위로
사용자 정보 보기 비밀 메시지 보내기
shkim



가입: 2019년 7월 30일
올린 글: 86

올리기올려짐: 2021년3월16일 23:53    주제: 인용과 함께 답변

네, 이해하신게 맞습니다.
"리스트를 뒤집어서 넣는" 작업에 O(n) 시간이 걸리지만, 그 뒤 n번의 dequeue가 각각 O(1) 시간이 걸리므로 amortized O(1) 시간이 소모됩니다.
위로
사용자 정보 보기 비밀 메시지 보내기
이전 글 표시:   
글 쓰기   답변 달기     게시판 인덱스 -> 4190.310 Programming Languages (Spring 2021) 시간대: GMT + 9 시간(한국)
페이지 11

 
건너뛰기:  
새로운 주제를 올릴 수 없습니다
답글을 올릴 수 없습니다
주제를 수정할 수 없습니다
올린 글을 삭제할 수 없습니다
투표를 할 수 없습니다


Powered by phpBB 2.0.21-7 (Debian) © 2001, 2005 phpBB Group
Translated by kss & drssay