Deque를 활용한 파이썬 최적화: 리스트를 대체하는 이유

deque(double-ended queue)는 Python의 collections 모듈에서 제공하는 자료구조로, 양쪽 끝에서 효율적으로 요소를 추가하고 제거할 수 있는 기능을 제공한다.

일반 리스트와 다른 데이터 구조와 비교할 때, deque의 장점을 아래와 같이 정리할 수 있다.

1. 효율적인 삽입과 삭제

• deque: 양쪽 끝에서의 요소 추가(append 및 appendleft)와 제거(pop 및 popleft)가 **O(1)**의 시간 복잡도를 가진다.
• 리스트: 리스트의 처음에서 요소를 제거하거나 추가하는 작업은 평균적으로 **O(N)**의 시간 복잡도를 가진다. 즉, 리스트의 크기가 커질수록 비효율적이다.

2. 메모리 효율성

• deque: deque는 메모리를 동적으로 관리하며, 필요한 경우 내부 구조를 재조정하여 추가적인 메모리 오버헤드를 줄인다.
• 리스트: 리스트는 고정 크기의 메모리 블록을 사용하여 메모리 할당이 비효율적일 수 있으며, 크기가 커질 경우 요소를 재배치해야 한다.

3. 스택과 큐의 통합

• deque: deque는 스택(Last In First Out, LIFO)과 큐(First In First Out, FIFO) 모두에 적합한 자료구조다. 양쪽 끝에서 모두 접근할 수 있기 때문에 유연한 자료구조다.
• 리스트: 리스트는 스택처럼 사용할 수 있지만, 큐처럼 사용하려면 추가적인 처리 없이 사용할 수 없다.

4. 반전 및 회전 기능

• deque: rotate(n) 메소드를 사용하여 deque의 요소를 쉽게 회전할 수 있으며, reverse() 메소드를 통해 요소를 반전시킬 수 있다.
• 리스트: 리스트에서도 회전 및 반전 기능을 사용할 수 있지만, deque보다 효율적이지 않다. 예를 들어, 리스트를 회전하려면 슬라이싱 등을 사용해야 하며, 이 과정에서 추가적인 메모리가 소모된다.

실제 백준 2164번 문제를 풀며 시간초과가 걸린 코드

# 정수 N 입력받기
N = int(input())

# 1부터 N까지의 숫자를 가진 리스트 생성
list1 = list(range(1, N + 1))

# 리스트에 하나의 요소만 남을 때까지 반복
while len(list1) != 1:
    del list1[0]              # 리스트의 첫 번째 요소 제거
    list1.append(list1[0])   # 첫 번째 요소를 리스트의 끝에 추가
    del list1[0]              # 이제 추가한 요소를 다시 제거

# 남은 요소를 출력
print(list1[0])

 

deque를 사용하여 수정한 코드 (시간초과 문제 해결)

from collections import deque

# 정수 N 입력받기
N = int(input())
# 1부터 N까지의 숫자를 가진 리스트 생성
list1 = list(range(1, N + 1))

# 리스트를 deque로 변환
deque1 = deque(list1)

# deque에 하나의 요소만 남을 때까지 반복
while len(deque1) != 1:
    deque1.popleft()         # 왼쪽 끝에서 요소 제거
    deque1.rotate(-1)       # 모든 요소를 왼쪽으로 한 칸 회전

# 남은 요소를 출력하고 deque에서 제거
print(deque1.popleft())

 

결론

deque는 양방향에서 효율적으로 요소를 추가하고 제거할 수 있는 장점을 가지며, 리스트보다 다양한 상황에서 더 유용하게 사용될 수 있다. 성능과 메모리 효율성이 중요한 작업에 적합하며, 스택과 큐의 기능을 모두 포함하는 유연한 자료구조다.