핵심 인사이트 (3줄 요약)

  1. 본질: 덱(Deque, Double-Ended Queue)은 양쪽 끝에서 삽입·삭제가 모두 가능한 자료구조다. 큐(FIFO)와 스택(LIFO)의 기능을 모두 포함하는 슈퍼셋이다.
  2. 가치: 슬라이딩 윈도우 최댓값/최솟값 문제에서 덱을 사용하면 O(n) 시간에 해결 가능하다(단순 배열은 O(n²)). 이중 연결 리스트 또는 순환 배열로 구현하며 모든 연산이 O(1) 분할 상환이다.
  3. 판단 포인트: 덱의 핵심 알고리즘 응용은 "단조 덱(Monotonic Deque)"이다. 슬라이딩 윈도우에서 최대/최솟값 조회 시 덱의 양끝 관리로 O(n) 달성. LeetCode 239번 Sliding Window Maximum이 대표 문제다.

Ⅰ. 개요 및 필요성

┌──────────────────────────────────────────────────────────┐
│               덱 자료구조 동작                            │
├──────────────────────────────────────────────────────────┤
│                                                           │
│  앞(Front) 삽입/삭제  ←→  뒤(Rear) 삽입/삭제             │
│                                                           │
│  [← A | B | C | D →]                                     │
│   앞(Front)          뒤(Rear)                             │
│                                                           │
│  push_front(X): [X | A | B | C | D]                      │
│  push_back(Y):  [X | A | B | C | D | Y]                  │
│  pop_front():   반환 X, [A | B | C | D | Y]              │
│  pop_back():    반환 Y, [A | B | C | D]                   │
│                                                           │
│  모든 연산: O(1) (이중 연결 리스트 또는 순환 배열)         │
└──────────────────────────────────────────────────────────┘
  • 📢 섹션 요약 비유: 덱은 양쪽에 문이 있는 버스다. 앞문·뒷문 어디서든 승객(데이터)이 탑승·하차할 수 있어 상황에 따라 큐처럼 앞뒤로 사용하거나 스택처럼 한쪽만 사용할 수 있다.

Ⅱ. 아키텍처 및 핵심 원리

단조 덱 (Monotonic Deque)

슬라이딩 윈도우 최댓값 (k=3):
  배열: [1, 3, -1, -3, 5, 3, 6, 7]
  
  창 [1,3,-1]: 덱=[3,-1], 최대=3
  창 [3,-1,-3]: 덱=[3,-1,-3], 최대=3
  창 [-1,-3,5]: 덱=[5], 최대=5
  창 [-3,5,3]: 덱=[5,3], 최대=5
  창 [5,3,6]: 덱=[6], 최대=6
  창 [3,6,7]: 덱=[7], 최대=7

원리: 덱 뒤에서 현재 값보다 작은 것은 제거 (단조 감소)
      창 밖으로 나간 인덱스는 앞에서 제거

구현 방식

구현장점단점
이중 연결 리스트O(1) 삽입·삭제포인터 오버헤드
순환 배열캐시 친화적크기 제한
Python collections.deque표준 라이브러리C 구현, 빠름
  • 📢 섹션 요약 비유: 단조 덱은 자동으로 더 작은 값을 버리는 스마트 줄이다. 줄에 들어올 때 나보다 작은 사람은 자동으로 줄에서 빠지는 규칙 덕분에 줄에는 항상 내림차순으로만 사람이 있다.

Ⅲ. 비교 및 연결

비교스택큐덱
삽입한쪽 끝한쪽 끝양쪽 끝
삭제같은 끝반대 끝양쪽 끝
패턴LIFOFIFO둘 다
  • 📢 섹션 요약 비유: 스택·큐·덱은 도로 구조다. 스택은 막힌 골목(한쪽만 출입), 큐는 일방통행 도로(한쪽 입구·반대쪽 출구), 덱은 양방향 도로(양쪽 모두 출입 가능)다.

Ⅳ. 실무 적용 및 기술사 판단

알고리즘 응용

from collections import deque

# 슬라이딩 윈도우 최댓값
def maxSlidingWindow(nums, k):
    dq = 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
  • 📢 섹션 요약 비유: 슬라이딩 윈도우 덱은 이동하는 창문이다. 창문(윈도우)이 오른쪽으로 이동하면서 창문 밖으로 나간 것은 버리고, 새로 들어온 것 중 최대가 아닌 것도 버려서 항상 현재 창문의 최댓값을 O(1)에 알 수 있다.

Ⅴ. 기대효과 및 결론

기대효과내용
슬라이딩 윈도우O(n²) → O(n) 최적화
양방향 처리큐+스택 기능 통합
BFS 변형우선순위 BFS, 0-1 BFS

덱은 BFS 변형 알고리즘(0-1 BFS, 양방향 BFS)에서도 핵심 역할을 한다. 0-1 BFS에서 가중치가 0인 엣지는 덱 앞쪽에, 1인 엣지는 뒤쪽에 추가하여 다익스트라 없이 O(V+E) 최단 경로를 구현한다.

  • 📢 섹션 요약 비유: 0-1 BFS + 덱은 급행·완행이 혼합된 지하철이다. 급행(가중치 0)은 맨 앞에 서고, 완행(가중치 1)은 맨 뒤에 서서 항상 가장 빠른 경로가 앞에 있도록 관리한다.

📌 관련 개념 맵

개념연결 포인트
단조 덱슬라이딩 윈도우 최적화 핵심
BFS덱 기반 그래프 탐색
0-1 BFS가중치 덱 기반 최단 경로
슬라이딩 윈도우덱의 핵심 알고리즘 응용 패턴
우선순위 큐덱의 확장 개념

📈 관련 키워드 및 발전 흐름도

[스택·큐 — 단방향 자료구조]
    │
    ▼
[덱 (Deque) — 양방향 삽입·삭제]
    │
    ▼
[단조 덱 — 슬라이딩 윈도우 최적화]
    │
    ▼
[0-1 BFS — 이진 가중치 최단 경로]
    │
    ▼
[세그먼트 트리·스파스 테이블 — 구간 최솟값 고급 구조]

👶 어린이를 위한 3줄 비유 설명

  1. 덱은 양쪽 모두 출입 가능한 버스예요! 앞문·뒷문 어디서든 타고 내릴 수 있어요.
  2. 단조 덱을 쓰면 이동하는 창문 안의 최댓값을 매번 다시 계산하지 않아도 돼요 — O(n²)을 O(n)으로 줄이는 마법!
  3. Python의 collections.deque는 이 덱을 빠르게 구현해둔 도구로 코딩 테스트에서 자주 쓰인답니다!