덱의, 삽입/삭제가 유리하고 큐 처럼 쓸 수 있다는 장점 때문에

저처럼 본인만의 문제풀이 코드 템플릿? 에 배열을 덱으로 정의해 놓으신 분들이 혹여나 있으실 것 같아 이렇게 글을 남깁니다.

deque를 vector로 바꾸니까 시간초과 뜨지 않습니다.

저도 덱은 삽입/삭제 오버헤드가 없는 대신 메모리가 연속적이지 않을 수 있고, 벡터는 연속적인 대신에 매 삽입 삭제마다 복사가 일어난다는, 각각의 자료구조상의 특성으로 인한 차이라고 추측 할 뿐입니다.

저처럼 온갖 Pruning 방법 찾느라 3시간 허비하지 마시라고 글 남겨드립니다...

zenith82114   2년 전

std::vector는 매 삽입/삭제마다 복사를 일으키지 않습니다. size가 capacity의 어떤 특정 비율을 넘나들 때에만 메모리 재할당 및 전체 복사를 하여 랜덤한 push_back/pop_back에 대하여 기댓값 O(1) 시간이 걸립니다. vector의 작동 원리, 또는 dynamic array, 또는 geometric scaling이라고 검색을 조금 해보시면 설명들이 잘 나올 것입니다.

답변 감사합니다. 또 하나 알아갑니다.

댓글을 작성하려면 로그인해야 합니다.