이전 글에서와 같이 파이썬에서 list를 쓸 때 아래 그림과 같은 push, pop연산은 (append()와 pop()을 통해 주로 사용)
stack 구조상 시간복잡도가 O(1)로 무리없이 금방 할 수 있지만, 저 깊은 곳에 (그림 상으로 bottom가까이)
데이터를 삽입하거나 삭제하려고 한다면 성능이 낮아지는게 list의 특징이다.
따라서 큐 연산이 필요하게 되면 collections.depue()를 이용하여 연산을 하는게 성능에 이득이다.
파이썬 collections.deque()는 양쪽에서 데이터를 pop(),popleft()를 통해 삭제할 수 있고
삽입 역시 append(), appendleft()를 통해 할 수 있는데 자료 구조상 양 쪽으로 큐가 뚫린 형태라서
큐보다 더 효율적으로 양쪽으로 삽입, 삭제를 할 수 있으므로 시간복잡도를 줄이는데 매우 좋은 자료구조이다.
일반 list에서 pop()이나 append()가 아닌, pop(0)나 append(0)를 하게 되면 시간복잡도가 O(n)이 되는데
이런 연산이 필요한 경우에 deque()를 통해 한층 한층 다 제끼고 index가 0인 요소에 연산할 필요 없이 양쪽이 뻥 뚫려있는 deque를 이용하면 한번만에 도달한 후 연산할 수 있어서 이득인 것. 따라서 0번 요소가 아녀도 바텀 가까이에
삽입, 삭제를 하려는 연산이라면 deque()를 사용하는 것이 좋다.
또한 deque에는 rotate()라는 알짜배기(?) 매써드가 있는데 다음 그림과 함께 직관적으로 이해해보자.
collections.depue([1,2,3,4,5])를 list_nums라는 것에 할당 해주면
일반리스트 [1,2,3,4,5]와 같이 인덱스가 부여된다.
여기서 러시안 룰렛에 총알을 넣고 돌리는 것처럼 5번을 시작요소로 하여
그 다음 요소가 나오게 하고 싶다면?
deque의 rotate()를 통해 쉽게 구현할 수 있다.
deque()로 정의된 객체에 .rotate(1)을 하면 시계 방향으로 룰렛을 한칸만 돌린것처럼 배열이 바뀌게 된다.
배열이 시계방향으로 돌아간 것으로 혹은 시작요소를 가리키는 포인터가 반시계방향으로
한칸 이동한 것으로도이해할 수 있다
rotate()에는 양수뿐만 아니라 마이너스 정수값도 넣을 수 있다.
-1을 넣으면 [1,2,3,4,5] 배열을 시계 반대 방향으로 한 칸씩 이동한 것
혹은 시작 포인터를 시계 방향으로 한 칸 움직여 가리킨 것과 같게 된다.
'Python_파이썬설명서' 카테고리의 다른 글
| 파이썬에서 자료구조 이해가 코딩 테스트 및 알고리즘 성능 (시간복잡도)에 미치는 영향 (0) | 2021.08.16 |
|---|
