deque() vs deque([]), 뭐가 맞는 방식이지?

deque()는 python의 collections 모듈에 포함된 double-ended queue로, 양쪽에서 데이터를 효율적으로 추가하거나 제거할 수 있는 자료구조다. 일반 리스트보다 양쪽에서 데이터 추가/삭제가 더 빠르기 때문에, 시간복잡도가 O(1)인 특징이 있고, 양쪽에서 모두 작동 가능한 메서드를 제공하기도 한다.(appendleft(), popleft())

from collections import deque

dq = deque([1,2,3])	# 초기 값 설정
dq.append(4) # 오른쪽에 추가
dq.appendleft(0) # 왼쪽에 추가
dq.pop()	# 오른쪽에서 제거
dq.popleft()	# 왼쪽에서 제거

print(dq)	# deque([1,2,3])

---

그런데 deque 을 초기화하는 과정에서 무심코 deque() 이라고 할 때도 있고, deque([]) 이렇게 명시를 해줄 때도 있는데, 둘의 차이는 뭘까? 결론부터 말하자면, 둘의 차이는 없지만 deque([]) 과 같은 초기화 스타일이 더 적합하다.

왜 deque([]) 과 같은 초기화가 필요할까?

1) deque 은 이터러블(iterable)을 인자로 받는다.

- deque 을 생성할 때, 초기값으로 이터러블(iterable) 객체를 전달해야 한다. 이터러블(iterable)한 객체는 '리스트, 튜플, 문자열' 등 반복 가능한 객체를 의미한다. 만약, 초기값 없이 빈 deque을 생성하고 싶다면, deque() 또는 deque([]) 를 사용할 수 있다.

• deque([]) : 명시적으로 빈 리스트를 전달해서 초기화
• deque() : 암묵적으로 빈 상태로 초기화

2) Pythonic한 스타일

python의 설계 철학 중 하나가 "명확한 것이 암묵적인 것보다 낫다"(Explicit is better than implicit)이다. deque([]) 는 코드의 의도를 명확히 드러내고 있다. 빈 리스트를 전달하면 "초기값이 없음을 의도적으로 표현"한다는 의미가 되기 때문이다.

 

3) 동작 차이는 없다

실제로, deque() 와 deque() 의 동작은 동일하고, 둘 다 빈 deque를 생성한다. 하지만, 명시적인 표현은 가독성을 높이고 협업 환경에서 더 이해하기 쉬운 코드를 작성할 수 있게 한다.

dq1 = deque()     # 암묵적
dq2 = deque([])   # 명시적

print(dq1)        # deque([])
print(dq2)        # deque([])

---

실제 deque([]) 초기화가 어떤 상황에서 유용하게 쓰이는지도 살펴보자.

 

1) 큐 또는 스택 초기화

: deque은 FIFO(First-In-First-Out) 큐와 LIFO(Last-In-First_Out) 스택의 성질을 다 갖고 있다. 따라서, 초기값 없이 데이터를 나중에 추가하려는 경우, deque([]) 로 빈 큐를 생성하는 것이 일반적이다. 

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])  # 초기화 시 명확히 표현

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            queue.extend(graph[node])  # 이웃 노드 추가
    return visited

 

2) BFS 알고리즘

: deque은 BFS(너비 우선 탐색)에서 큐 역할을 수행하며 매우 효율적이다.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])  # 시작 노드를 큐에 추가

    while queue:
        node = queue.popleft()  # 큐에서 노드 제거
        if node not in visited:
            visited.add(node)
            queue.extend(graph[node])  # 이웃 노드 추가

    return visited

# 그래프와 시작 노드
graph = {1: [2, 3], 2: [4], 3: [], 4: []}
print(bfs(graph, 1))  # {1, 2, 3, 4}

 

3) 슬라이딩 윈도우 알고리즘(Sliding Window)

: deque은 슬라이딩 윈도우 문제를 해결할 때 유용하게 쓰인다.

def max_sliding_window(nums, k):
    dq = deque([])  # 빈 deque 초기화
    result = []

    for i, num in enumerate(nums):
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(max_sliding_window(nums, 3))  # [3, 3, 5, 5, 6, 7]

코드 설명은 아래와 같다.

 

k = 3 이므로 윈도우의 크기는 3이다.

윈도우 구간	윈도우 요소	최댓값
[1,3,-1]	[1,3,-1]	3
[3,-1,-3]	[3,-1,-3]	3
[-1,-3,5]	[-1,-3,5]	5
[-3,5,3]	[-3,5,3]	5
[5,3,6]	[5,3,6]	6
[3,6,7]	[3,6,7]	7

 

1. 슬라이딩 윈도우 이동 : 배열의 인덱스 i 와 값 num 을 순회하며 윈도우를 업데이트한다.

2. 왼쪽 범위 초과 요소 제거

while dq and dq[0] < i - k + 1:
    dq.popleft()

윈도우 크기를 벗어나는 인덱스를 deque 에서 제거한다.

 

3. 새로 들어온 값보다 작은 값 제거

while dq and nums[dq[-1]] < num:
    dq.pop()

새로 들어온 값 num이 deque 내 값보다 크다면, 현재 값은 더 이상 최댓닶이 될 가능성이 없으므로 제거한다.

 

4. 현재 인덱스를 추가

dq.append(i)

 

5. 최댓값 기록

if i >= k - 1:
    result.append(nums[dq[0]])

윈도우 크기가 k 이상일 때, deque 의 첫 번째 인덱스에 해당하는 값을 결과에 추가

---