🚩deque에 대하여
2022-07-03
우선 문제를 풀다보면 우리는 흔하게 리스트를 접하게 되는데 해당 상황에서 보다보면 특정인덱스를 비워서 없애서 옆으로 shift해줘야 하는 상황이 자주 발생한다.그리고 그 중 큐 같은 문제에서는 '앞에서부터~' 라는 말이 나오는 느낌이 존재한다.
사실 큐나 스택을 구현하는데 있어서 파이썬은 리스트 생성해서 사용을 해도 사용은 가능하다
🔑deque와 일반 리스트를 사용할 때의 차이점
애초에 리스트는 원래 무작위 접근이 가능한 자료형으로서 자체적으로
pop()같은 것을 진행할시 shift를 해주는 연산이 필요하여 O(n)의 복잡성을 갖게 되어 데이터가 커지면 효율이 떨어진다
deque를 사용할 시 성능의 시간복잡도 O(1)이라 데이터 크기가 커져도 훨씬 좋음
하지만 그에 따라서 인덱싱이나 슬라이싱을 자체적으로 제공하지는 않음
따라서 나중에는 list()로 다시 형 변환을 하는 것도 나쁘지않음
🙋♂️사용방법
from collections import deque
tmp=deque([])
tmp.append(넣을 원소)
#오른쪽에 원소 삽입
tmp.popleft()
#왼쪽에서 제거-흔히 큐에서 많이 쓰는 방법
tmp.pop()
#오른쪽에서 제거-흔히 스택에서 많이 쓰는 방법
그럼 큐를 사용하는 문제에서 전체적인 대체로 틀은
while queue:
#즉 큐 안에 원소가 있는지 없는지에 대하여 체크 후 while루프 진행
큐연산에 대한 것 진행이와 같다고 볼 수 있을 것 같다
물론 queue에 대하여
for q in queue:
연산진행이런식으로 가능은 하지만 만약에 for문 안에서 queue에 대한 원소에 대한 변경이 일어나는 연산인 popleft()나 append()가 일어난다면 실시간으로 for문을 돌고 있는 queue에 대해서 업데이트 되어 계속 돌아가는 것이 아니라
연산 전 것으로 돌아가게 되는 문제점이 생긴다.
또한 for문 내부에서 큐에 대한 수정이 들어가게 되면 파이썬 자체적으로도
queue에 대한 오류가 발생한다
따라서 정 써야할 것 같은 상황이 발생할시에는
for q in list(queue):
#이와 같이 리스트 형변환후 수정해서 사용
#-단 이래도 변경된 사항에 대한 반영은 역시 안된다는점
for q in copy.deepcopy(queue):
#이런 방법도 존재하지만 최대한 queue를 선회하는 for문 내부에서 큐에 대한 수정은 따라서 피하게 코드를 짜는게 더 좋을 것 같다
대신 while문을 돌면서 queue에 대한 연산을 진행하는걸 더 추천!
🚩문제를 풀어보면서 느낀점
1.미리 전체 리스트를 0으로 초기화 해두고 수정해주는 방법
tmp=[0 for x in range(사이즈)]2.for문 queue 선회를 사용을 하며 내부에서 과연 queue에 대한 수정연산이 없다면
for x in queue:
#굳이 queue에 대해서 리스트 씌우지 말자
#그래야 효율성이 deque버젼으로 돌아가 더 좋아짐3.스택 문제에서의 기본 느껴야 하는 것은 구조상 무엇인가 앞에서부터 쭉 담아두되 후반부쪽에만 수정해주면 될 것 같을 때 사용해주면 좋은 상황
