덱은 앞과 뒤에서 원소를 넣고 꺼내는 양방향 큐다. 원형 배열 구현, 언어별 계약, 제한 용량과 회전, 단조 덱의 윈도 최댓값과 0-1 BFS를 실제 예제와 기준 구현 대조로 설명한다.
개요: 양 끝을 모두 사용하는 큐
덱(deque)은 double-ended queue의 줄임말로, 앞과 뒤에서 원소를 넣고 꺼낼 수 있는 양방향 큐다. 보통 앞 삽입·뒤 삽입·앞 제거·뒤 제거의 네 연산을 제공한다. 한쪽에서 넣고 반대쪽에서 빼면 FIFO 큐,같은 쪽에서 넣고 빼면 LIFO 스택으로 사용할 수 있다.
양 끝에 접근할 수 있다는 성질은 최근 항목 관리뿐 아니라 슬라이딩 윈도에서 쓸모없는 후보를 양쪽에서 제거하거나 비용이 0인 탐색을 앞으로 보내는 알고리즘에도 쓰인다. 단순히 큐와 스택을 합친 이름을 외우기보다 각 끝에 어떤 의미를 부여하는지가 중요하다.
이 문서는 네 연산의 계약과 원형 배열 구현, 언어별 차이, 제한 용량의 버림 정책, 단조 덱과 0-1 BFS를 설명한다. 실행 예제는 Python 3.9.6에서 확인했고 직접 만든 RingDeque와 표준 deque를 대조한다.
deque와 dequeue는 다른 말이다. deque는 자료구조 이름이고 dequeue는 큐에서 꺼내는 연산을 가리킨다. 또한 양 끝 연산이 빠르다고 임의 인덱스 접근이나 중간 삽입이 모든 언어에서 같은 비용이라는 뜻은 아니다.
네 연산을 같은 입력에서 비교하기
앞과 뒤를 먼저 정하면 API를 이해하기 쉽다. Python collections.deque에서는 append가 오른쪽 삽입,appendleft가 왼쪽 삽입,pop이 오른쪽 제거,popleft가 왼쪽 제거다. 왼쪽을 front,오른쪽을 back으로 부르는 표기를 사용할 수 있다.
아래 [B,C]에서 왼쪽에 A,오른쪽에 D를 넣으면 [A,B,C,D]가 된다. popleft는 A,pop은 D를 꺼내고 [B,C]가 남는다. 같은 저장소를 쓰더라도 어떤 끝에서 꺼내는지에 따라 순서가 달라진다.
빈 상태에서 제거하면 Python deque는 IndexError를 발생시킨다. 다른 언어에는 Optional이나 특별한 반환값을 쓰는 API도 있다. 정상 데이터로 None이나 null을 저장할 수 있는지와 빈 상태 표시가 무엇인지를 함께 확인해야 한다.
예제 코드
from collections import deque
items = deque(['B', 'C'])
items.appendleft('A')
items.append('D')
print(list(items))
print(items.popleft(), items.pop())
print(list(items))실행 결과
['A', 'B', 'C', 'D']
A D
['B', 'C']같은 덱으로 FIFO와 LIFO 구현하기
FIFO 큐는 먼저 들어온 항목이 먼저 나가야 하므로 오른쪽에 넣고 왼쪽에서 꺼낼 수 있다. LIFO 스택은 오른쪽에 넣고 오른쪽에서 꺼내면 된다. 덱이 두 규칙을 모두 지원한다는 뜻이지 한 번의 제거가 동시에 두 규칙을 만족한다는 뜻은 아니다.
아래 동일한 A,B,C를 담은 두 덱에서 FIFO는 A,B,C,LIFO는 C,B,A를 출력한다. 업무 코드에서 메서드를 하나 잘못 선택하면 프로그램이 정상 실행되면서 순서만 달라질 수 있다. 타입과 인터페이스로 의도를 드러내면 실수를 줄일 수 있다.
큐만 필요한 모듈에는 append와 popleft만 노출하는 작은 래퍼를 둘 수 있다. 모든 끝 연산을 공개하면 다른 코드가 앞에 새 작업을 넣어 기존 대기 순서를 깨뜨릴 수 있다. 유연한 자료구조와 제한된 업무 계약을 구분한다.
우선순위 큐는 별개의 선택 규칙이다. 덱의 앞·뒤에 넣는 것만으로 임의의 우선순위 전체를 자동 정렬할 수는 없다. 뒤에서 다룰 0-1 BFS는 비용의 범위가 제한되어 있기 때문에 두 끝을 활용할 수 있는 특수한 경우다.
예제 코드
from collections import deque
fifo = deque('ABC')
lifo = deque('ABC')
print([fifo.popleft() for _ in range(3)])
print([lifo.pop() for _ in range(3)])실행 결과
['A', 'B', 'C']
['C', 'B', 'A']내부 구현은 하나로 정해져 있지 않다
덱은 연산 계약이며 저장 방식은 여러 가지다. 원형 배열,연결된 블록,이중 연결 노드와 같은 구성이 가능하다. 어떤 표현을 사용하는지에 따라 인덱스 접근,메모리 지역성,확장과 반복자 무효화의 성질이 달라진다.
원형 배열은 논리 순서가 배열 끝을 넘어 앞부분으로 이어질 수 있다. 블록 기반 구조는 여러 원소를 담은 블록을 연결하여 노드 하나당 원소 하나인 연결 리스트와 다른 공간·접근 특성을 가질 수 있다. 구현 세부를 단어 deque 하나로 추측하지 않는다.
언어별 공식 계약도 다르다. Python deque의 가운데 인덱스 접근을 C++ deque의 임의 접근 계약과 동일하게 설명하면 안 된다. Java ArrayDeque는 List의 인덱스 접근 API가 아니며 Rust VecDeque는 원형 버퍼의 연속 구간을 다루는 기능을 제공한다.
성능을 비교할 때는 필요한 연산을 나누어 본다. 양 끝 추가·삭제가 대부분인지,중간 검색이 많은지,슬라이스처럼 연속 메모리를 요구하는 외부 API와 연결해야 하는지에 따라 적합한 구현이 달라진다. 자료구조의 이름보다 사용 방식이 중요하다.
원형 배열의 head와 논리 인덱스
용량 C의 원형 배열에서 head는 맨 앞 원소의 물리 위치이고 size는 유효 원소 수다. 논리 위치 i는 (head+i)%C에 저장한다. 원소들이 배열의 끝과 앞에 나뉘어 있어도 이 식으로 같은 논리 순서를 유지할 수 있다.
뒤 삽입은 (head+size)%C에 쓰고 길이를 늘린다. 앞 삽입은 head를 한 칸 뒤로 이동한 위치에 값을 쓴다. 앞 제거는 현재 head를 비우고 한 칸 전진하며,뒤 제거는 (head+size-1)%C를 비운다.
아래 C=5,head=3,size=3의 유효 위치는 3,4,0이다. 앞에 넣을 위치는 2,뒤에 넣을 위치는 1이다. 길이가 용량보다 작다는 조건이 있어야 두 위치가 빈칸으로 사용 가능하다. 꽉 찼을 때는 먼저 확장하거나 실패 정책을 적용한다.
Python에서 음수 값의 % 양수 결과는 원형 인덱스 계산에 맞게 음이 아닌 나머지가 된다. 다른 언어로 옮길 때는 음수 나머지 규칙을 확인하고 (head-1+C)%C처럼 조정할 수 있다. 수학식이 같아 보여도 언어 연산의 의미가 다를 수 있다.
예제 코드
capacity, head, size = 5, 3, 3
print([(head + i) % capacity for i in range(size)])
print((head - 1) % capacity, (head + size) % capacity)실행 결과
[3, 4, 0]
2 1확장 가능한 최소 구현
아래 RingDeque는 용량 1에서 시작해 가득 차면 두 배로 늘린다. 확장 시 기존 원소를 논리 순서로 새 배열의 앞부분에 옮기고 head=0으로 맞춘다. 앞 삽입·뒤 삽입 모두 같은 용량 확보 함수를 사용한다.
제거된 슬롯은 None으로 비워 참조를 놓는다. None도 정상 원소로 저장할 수 있으므로 유효 여부는 슬롯 값이 아니라 size로 판단한다. 빈 제거는 IndexError이고 자동 축소는 구현하지 않았다. 한 번 확보한 용량은 원소를 꺼내도 유지한다.
to_list는 전체 유효 원소를 복사하므로 O(n)이다. 네 끝 연산의 테스트 결과를 읽기 쉽게 출력하려고 제공한 도구이며 매 연산의 내부 과정에서 호출하지 않는다. 내부 필드 접근과 타입 검증을 단순화한 교육용 구현이고 스레드 안전성은 없다.
각 추가는 보통 상수 개의 작업이지만 확장 때 O(n) 복사가 발생한다. 두 배 정책을 사용한 연속 추가의 재할당 비용은 분할 상환 O(1)로 분석할 수 있다. 개별 호출의 최대 지연이 상수라는 뜻은 아니다.
예제 코드
class RingDeque:
def __init__(self):
self._data = [None]
self._head = 0
self._size = 0
def __len__(self):
return self._size
def _grow_if_full(self):
if self._size < len(self._data):
return
new_data = [None] * (2 * len(self._data))
for i in range(self._size):
new_data[i] = self._data[(self._head + i) % len(self._data)]
self._data = new_data
self._head = 0
def append(self, value):
self._grow_if_full()
index = (self._head + self._size) % len(self._data)
self._data[index] = value
self._size += 1
def appendleft(self, value):
self._grow_if_full()
self._head = (self._head - 1) % len(self._data)
self._data[self._head] = value
self._size += 1
def pop(self):
if not self._size:
raise IndexError('deque empty')
index = (self._head + self._size - 1) % len(self._data)
value = self._data[index]
self._data[index] = None
self._size -= 1
return value
def popleft(self):
if not self._size:
raise IndexError('deque empty')
value = self._data[self._head]
self._data[self._head] = None
self._head = (self._head + 1) % len(self._data)
self._size -= 1
return value
def to_list(self):
return [self._data[(self._head + i) % len(self._data)]
for i in range(self._size)]
d = RingDeque()
d.append('B')
d.appendleft('A')
d.append('C')
print(d.to_list(), len(d._data))
print(d.popleft(), d.pop(), d.to_list())실행 결과
['A', 'B', 'C'] 4
A C ['B']확장할 때 물리 배열을 그대로 복사하면 안 된다
head가 0이 아닌 상태에서 원형 버퍼를 확장하면 논리 순서를 복원해 복사해야 한다. 물리 인덱스 0부터 복사한 뒤 head만 0으로 바꾸면 원소 순서가 달라질 수 있다. 특히 앞 삽입과 앞 제거를 섞은 뒤 확장하는 경우에 드러난다.
아래는 B,C,D에 앞의 A를 더해 [A,B,C,D]를 만든 뒤 앞에서 A를 제거하고 뒤에 E를 넣는다. 논리 순서는 B,C,D,E다. 그 다음 앞에 X를 넣으며 확장해도 [X,B,C,D,E]가 되어야 한다.
이 사례는 길이만 확인하면 잡을 수 없는 오류다. 길이는 5로 맞아도 원소가 회전되어 있거나 하나가 덮이면 결과가 틀리므로 전체 순서를 기준 모델과 비교한다. 빈 상태에서만 확장 테스트를 하면 head가 이동한 경우의 버그를 놓칠 수 있다.
실제 구현에서는 새 버퍼 확보에 실패했을 때 기존 상태를 보존하는 순서도 중요하다. 새 저장소를 준비하고 복사한 뒤 교체하는 방식과 원소 이동의 예외 계약을 검토한다. Python 참조 복사 예제를 다른 언어의 임의 값 이동에 그대로 일반화하지 않는다.
예제 코드
d = RingDeque()
for value in ['B', 'C', 'D']:
d.append(value)
d.appendleft('A')
print(d.popleft())
d.append('E')
print(d.to_list())
d.appendleft('X')
print(d.to_list(), len(d._data))실행 결과
A
['B', 'C', 'D', 'E']
['X', 'B', 'C', 'D', 'E'] 8복잡도 표기의 전제를 확인하기
원형 배열 구현의 양끝 추가는 확장이 없으면 O(1),두 배 성장 정책에서 분할 상환 O(1)이다. 양끝 제거는 자동 축소를 하지 않는 이 예제에서는 O(1) 구조 작업이다. 전체 논리 순회와 to_list 복사는 O(n)이다.
중간 위치에 삽입하려면 어느 쪽 원소를 옮길지 선택할 수 있다. 원형 배열 덱은 가까운 끝 방향으로 이동하여 대략 min(i,n-i)개의 원소 이동으로 처리할 수 있지만 여전히 가운데에서는 선형이다. 양끝이 빠르다는 사실과 중간도 빠르다는 주장은 다르다.
Python deque의 임의 인덱스 접근은 양끝 근처에서 빠르고 가운데로 갈수록 선형 비용이 들 수 있다. 인덱스 0부터 n-1까지 하나씩 접근하는 반복 대신 직접 순회하는 방식이 더 적합할 수 있다. C++ deque는 다른 임의 접근 계약을 가지므로 같은 표를 모든 언어에 적용하지 않는다.
메모리도 현재 길이 외에 여유 용량과 블록 관리 정보가 포함될 수 있다. 빈 덱이 되었을 때 실제로 얼마를 반환하는지는 구현 정책이다. 성능 분석을 쓸 때 언어·자료형·연산과 평균/분할 상환/최악 중 어떤 비용인지 함께 적는다.
extendleft는 입력 순서를 뒤집을 수 있다
Python deque의 extendleft는 입력을 순회하며 각 항목을 왼쪽에 추가한다. A를 먼저 넣고 B를 그 앞에 넣으면 최종 앞부분은 B,A가 된다. 한 번에 리스트를 왼쪽에 붙여 입력 순서를 그대로 보존하는 의미와 다르다.
아래 X 앞에 A,B,C를 extendleft하면 C,B,A,X다. 입력 순서를 유지하려면 역순 입력을 넘겨 A,B,C,X를 만들 수 있다. 입력이 목록처럼 뒤집을 수 있는 시퀀스인지,한 번만 읽을 수 있는 이터레이터인지에 따라 방법과 추가 저장 비용이 달라진다.
메서드 이름만으로 대량 연산의 순서를 추측하기보다 작은 서로 다른 항목으로 직접 확인하는 것이 좋다. 값이 모두 같으면 뒤집힘을 발견하기 어렵고,빈 입력만 테스트하면 의미가 드러나지 않는다.
이 동작은 슬라이딩 윈도나 탐색에서 여러 후보를 앞에 넣는 코드에도 영향을 줄 수 있다. 우선순위가 같은 항목의 처리 순서가 중요한 경우에는 앞 삽입의 반복 방향을 명시적으로 정한다.
예제 코드
from collections import deque
first = deque(['X'])
first.extendleft(['A', 'B', 'C'])
second = deque(['X'])
second.extendleft(reversed(['A', 'B', 'C']))
print(list(first))
print(list(second))실행 결과
['C', 'B', 'A', 'X']
['A', 'B', 'C', 'X']회전은 순서를 바꾸는 연산이다
덱의 회전은 한쪽 끝의 원소를 반대쪽으로 이동시킨 효과를 낸다. Python rotate(1)은 오른쪽 끝 하나를 왼쪽으로 옮기고 rotate(-1)은 그 반대다. 회전 수가 전체 길이보다 크면 주기적인 성질을 이용해 의미를 이해할 수 있다.
아래 A,B,C,D를 오른쪽으로 한 칸 회전하면 D,A,B,C이고 이어서 왼쪽으로 두 칸 회전하면 B,C,D,A다. 회전은 원소의 상대적인 원형 순서를 유지하지만 선형 목록의 시작점은 바꾼다.
원형 배열에서는 head를 바꾸기만 하면 될 것처럼 보이지만 유효 원소가 버퍼 전체를 채우지 않으면 단순 head 변경으로 빈 슬롯을 포함하게 될 수 있다. 실제 구현의 회전 방식과 비용은 자료 표현에 달려 있다. API가 제공한다는 이유로 임의 크기 회전이 항상 O(1)이라고 주장하지 않는다.
요세푸스 문제나 순환 작업 순서에 회전을 활용할 수 있지만 회전 횟수와 반복 횟수가 크면 전체 비용을 따로 분석해야 한다. 필요한 답이 마지막 생존자 하나인지 전체 제거 순서인지에 따라 더 적합한 방법이 있을 수 있다.
예제 코드
from collections import deque
items = deque('ABCD')
items.rotate(1)
print(list(items))
items.rotate(-2)
print(list(items))실행 결과
['D', 'A', 'B', 'C']
['B', 'C', 'D', 'A']제한 용량 덱의 자동 버림 정책
Python deque(maxlen=k)는 양끝 추가 시 용량을 넘으면 반대쪽 원소를 버리는 동작을 제공한다. 최근 k개 기록만 유지하는 용도에는 편리하지만 모든 작업을 반드시 처리해야 하는 큐와는 다른 계약이다. 가득 찼을 때 대기하거나 오류를 반환하는 도구가 아니다.
아래 용량 3의 A,B,C에 D를 오른쪽에 추가하면 A가 사라지고 B,C,D가 된다. 이어서 X를 왼쪽에 추가하면 반대쪽 D가 사라져 X,B,C가 된다. 버려진 항목이 필요했다면 이 선택은 데이터 손실을 일으킨다.
자동 버림은 로그 꼬리,최근 관측값이나 화면 이력처럼 오래된 항목을 버려도 되는 요구에 맞출 수 있다. 결제·영속 작업·전달 보장처럼 손실을 허용하지 않는 흐름에는 별도의 용량 제한과 역압 정책이 필요하다.
같은 bounded deque에서도 모든 메서드의 초과 처리 의미가 같다고 가정하지 않는다. Python의 insert는 제한 용량을 초과시키면 IndexError를 낼 수 있으므로 append의 버림 동작과 구분한다. 사용하는 연산의 공식 계약을 확인한다.
예제 코드
from collections import deque
items = deque('ABC', maxlen=3)
items.append('D')
print(list(items))
items.appendleft('X')
print(list(items))
try:
items.insert(1, 'Y')
except IndexError:
print('insert rejected')실행 결과
['B', 'C', 'D']
['X', 'B', 'C']
insert rejected회문 검사에서 양끝 제거하기
회문은 앞에서 읽은 순서와 뒤에서 읽은 순서가 같은 문자열이다. 양끝의 값을 비교해 같으면 제거하고 가운데로 진행하면 덱의 두 끝을 자연스럽게 사용할 수 있다. 남은 길이가 0 또는 1이면 비교가 끝난다.
아래 함수는 입력의 각 Python 문자를 그대로 비교한다. level은 True,codex는 False,빈 문자열은 True다. 대소문자 무시나 공백 제거,유니코드 정규화를 하지 않으므로 사람이 보는 모든 회문 개념을 처리하는 완성된 텍스트 정규화기는 아니다.
문자열을 덱으로 복사하므로 O(n) 보조 공간을 사용한다. 원본 문자열에서 좌우 인덱스만 이동하면 같은 비교를 더 적은 추가 공간으로 수행할 수 있다. 덱을 사용할 수 있다는 사실과 그 문제가 덱을 꼭 필요로 한다는 사실은 다르다.
입력 자체가 양끝으로 변경되는 자료이거나 다른 덱 연산과 결합되는 경우에는 이 방식이 적합할 수 있다. 자료구조 선택은 예제를 만들기 위한 선택이 아니라 실제 입력의 형태와 연산 요구에 맞춰 판단한다.
예제 코드
from collections import deque
def palindrome(text):
items = deque(text)
while len(items) > 1:
if items.popleft() != items.pop():
return False
return True
for text in ['level', 'codex', '']:
print(repr(text), palindrome(text))실행 결과
'level' True
'codex' False
'' True슬라이딩 윈도 최댓값의 문제 정의
길이 n 배열에서 연속된 width개 원소의 최댓값을 각 위치마다 구한다고 하자. [1,3,-1,-3,5,3,6,7]에서 폭 3의 결과는 [3,3,5,5,6,7]이다. 매 구간을 처음부터 훑으면 O(n·width)의 비교가 필요할 수 있다.
윈도가 한 칸 움직이면 맨 왼쪽 원소 하나가 빠지고 오른쪽 원소 하나가 들어온다. 기존 최댓값이 빠졌을 때 다음 후보를 효율적으로 알아야 하므로 단순한 최댓값 변수 하나만으로는 부족하다. 모든 원소를 매번 다시 조사하지 않을 후보 관리가 필요하다.
단조 덱은 아직 유효하고 앞으로 최댓값이 될 가능성이 있는 인덱스만 보관한다. 앞에서는 윈도 밖으로 나간 인덱스를 제거하고,뒤에서는 새 값보다 작거나 같은 낡은 후보를 제거한다. 두 끝이 서로 다른 이유로 쓰인다.
이 문서의 함수는 1≤width≤n을 전제로 하고 범위를 벗어나면 ValueError를 낸다. 빈 입력에 폭 0을 허용하는 다른 API를 만들 수도 있지만 같은 계약이 아니므로 명시적으로 구분한다.
단조 덱 구현: 만료와 지배 후보 제거
아래 window_maximum은 먼저 인덱스가 index-width 이하인 앞 후보를 제거한다. 현재 윈도의 시작은 index-width+1이므로 그 이전은 더 이상 답에 사용할 수 없다. 다음으로 새 값 이하인 뒤 후보를 제거한 뒤 새 인덱스를 넣는다.
뒤 후보를 제거해도 되는 이유는 새 원소가 그 후보보다 크거나 같고 더 늦게 만료되기 때문이다. 앞으로 두 원소가 함께 포함되는 윈도에서는 새 원소가 최댓값으로 적어도 좋으며,옛 원소가 만료된 뒤에도 새 원소는 남을 수 있다. 더 오래 살아 있는 지배 후보를 보존하는 것이다.
덱 앞은 현재 유효 후보 중 값이 가장 크다. 윈도 하나가 완성되는 index≥width-1부터 그 값을 결과에 추가한다. 값이 아닌 인덱스를 저장하므로 만료 여부를 판단할 수 있고 같은 값의 여러 위치도 구분할 수 있다.
이 함수는 최댓값만 반환하므로 같은 값 중 어느 위치를 남기는지는 출력 값에 영향을 주지 않는다. 최댓값의 가장 오래된 위치까지 필요하다면 동률 제거 규칙을 바꾸어야 한다. 요구사항에 따라 <=와 <의 의미가 달라진다.
예제 코드
def window_maximum(values, width):
from collections import deque
if not 1 <= width <= len(values):
raise ValueError('invalid window width')
candidates = deque()
result = []
for index, value in enumerate(values):
while candidates and candidates[0] <= index - width:
candidates.popleft()
while candidates and values[candidates[-1]] <= value:
candidates.pop()
candidates.append(index)
if index >= width - 1:
result.append(values[candidates[0]])
return result
print(window_maximum([1, 3, -1, -3, 5, 3, 6, 7], 3))
print(window_maximum([2, 2, 2], 2))실행 결과
[3, 3, 5, 5, 6, 7]
[2, 2]단조 덱의 정확성과 선형 시간
덱 안의 인덱스는 시간 순서로 증가하고 대응하는 값은 이 구현에서 엄격히 감소한다. 앞에서 오래된 인덱스를 지우면 남은 후보는 모두 현재 윈도 안에 있다. 뒤에서 지운 후보는 더 늦고 크거나 같은 후보가 대신하므로 최댓값을 잃지 않는다.
각 인덱스는 한 번 들어가고 앞이나 뒤 중 한쪽으로 최대 한 번 나온다. 안쪽 while이 어떤 단계에서 여러 번 실행되어도 전체 제거 횟수는 n을 넘지 않는다. 따라서 전체 시간은 O(n)이다. 중첩 반복문의 모양만 세어 O(n²)이라고 판단하지 않는 사례다.
덱의 후보는 현재 윈도 안의 인덱스이므로 보조 공간은 O(width)다. 반환 결과 목록은 n-width+1개이므로 출력 공간을 포함하면 O(n)이다. 두 수치를 구별하면 메모리 요구를 더 정확히 설명할 수 있다.
입력이 스트림이면 결과를 하나씩 내보내고 필요한 후보의 값과 위치만 유지하는 형태로 바꿀 수 있다. 다만 현재 함수는 원본 values를 인덱스로 읽으므로 그 자체가 스트림 구현은 아니다. 인터페이스를 바꿀 때 자료 수명과 출력 소비 방식도 함께 검토한다.
동률·만료 경계에서 생기는 오류
윈도 시작 위치와 같은 인덱스는 아직 유효하다. index-width를 넘지 않는 후보를 제거해야 하며 index-width+1까지 제거하면 맨 왼쪽의 정상 원소를 너무 일찍 버린다. width=1과 width=n은 이런 경계 실수를 찾기 좋은 입력이다.
중복 값 처리도 인덱스를 함께 저장해야 안전하다. 값만 보고 앞에서 같은 값을 제거하면 새 위치의 같은 값까지 지웠는지 구분하기 어렵다. 만료는 값의 크기가 아니라 삽입된 위치에 따라 결정된다.
아래 폭 1의 결과는 원본과 같고,전체 폭의 결과는 최댓값 하나다. [5,1,5]의 폭 2에서는 같은 최댓값 5가 서로 다른 위치에서 기여한다. 오래된 5가 만료되어도 새 5가 남아야 한다.
문서의 설명과 코드 비교 연산을 함께 검토한다. “크거나 같은 후보를 제거”라고 설명하면서 <만 사용해도 값 결과가 맞을 수 있지만 동률 정책과 공간 상태의 설명은 달라진다. 결과뿐 아니라 약속한 불변식이 일치해야 한다.
예제 코드
values = [5, 1, 5]
print(window_maximum(values, 1))
print(window_maximum(values, 3))
print(window_maximum(values, 2))
for width in [0, 4]:
try:
window_maximum(values, width)
except ValueError:
print('invalid', width)실행 결과
[5, 1, 5]
[5]
[5, 5]
invalid 0
invalid 40-1 BFS: 두 종류의 비용을 양 끝에 배치하기
간선 가중치가 0 또는 1인 그래프에서는 일반 FIFO BFS의 최초 발견 규칙만으로 최소 비용을 구할 수 없다. 비용 1의 경로를 먼저 발견한 뒤 비용 0의 우회 경로로 개선할 수 있기 때문이다. 거리 갱신이 필요하다.
현재 거리 d의 정점에서 비용 0 간선을 지나면 새 거리는 d이고 비용 1이면 d+1이다. 0 비용으로 개선한 후보는 덱 앞에,1 비용 후보는 뒤에 넣어 가까운 거리 계층을 먼저 처리할 수 있다. 일반적인 임의 가중치 전체를 정렬하는 우선순위 큐 대신 제한된 비용 구조를 이용하는 방법이다.
아래 zero_one_distances는 정점과 그 항목을 넣을 때의 거리를 함께 저장한다. 나중에 더 좋은 경로가 발견되어 오래된 항목이 남아 있으면 저장된 거리와 현재 최솟값이 다른 항목을 건너뛴다. 방문 여부 하나로 이후 개선을 막지 않는다.
입력 그래프는 해시 가능한 정점에서 (이웃,가중치) 목록으로 가는 매핑이며 모든 가중치가 0 또는 1이어야 한다. 함수는 도달하여 검사한 간선의 범위 위반을 ValueError로 알린다. 도달하지 못한 부분까지 외부 입력 전체를 검증하려면 별도 검사가 필요하다.
예제 코드
def zero_one_distances(graph, start):
from collections import deque
distances = {start: 0}
pending = deque([(0, start)])
while pending:
saved_distance, vertex = pending.popleft()
if saved_distance != distances[vertex]:
continue
for neighbor, weight in graph.get(vertex, []):
if weight not in (0, 1):
raise ValueError('weight must be zero or one')
candidate = saved_distance + weight
if candidate < distances.get(neighbor, float('inf')):
distances[neighbor] = candidate
item = (candidate, neighbor)
if weight == 0:
pending.appendleft(item)
else:
pending.append(item)
return distances
graph = {'A': [('B', 1), ('C', 0)], 'C': [('B', 0)], 'B': [('D', 1)], 'D': []}
print(sorted(zero_one_distances(graph, 'A').items()))실행 결과
[('A', 0), ('B', 0), ('C', 0), ('D', 1)]최초 발견을 확정하지 않는 이유
예제에서 A→B의 비용은 1이지만 A→C→B의 비용은 0이다. B를 처음 큐에 넣은 순간 visited로 확정하고 이후 갱신을 막으면 B의 답이 1로 잘못 고정된다. 가중치가 모두 같은 일반 BFS와 다른 상태 갱신 규칙이 필요한 이유다.
0-1 BFS에서는 더 작은 candidate가 나올 때만 거리를 갱신한다. 비용 0의 순환이 있어도 동일한 거리로는 계속 다시 넣지 않으므로 불필요한 반복을 막는다. <=로 갱신 조건을 바꾸면 같은 비용의 순환에서 끝없이 넣는 오류를 만들 수 있다.
덱의 거리 계층 순서를 유지하면 유효한 최소 거리 항목을 먼저 처리할 수 있고 각 정점의 이웃을 최종 거리에서 처리하는 분석이 가능하다. 인접 목록에서 시간 O(V+E)로 분석하며,중복된 오래된 대기 항목을 저장하는 이 구현에서는 큐 공간을 무조건 정점 수만으로 제한한다고 단정하지 않는다. 거리 사전과 대기 항목을 함께 센다.
가중치가 2,음수 또는 임의 실수로 바뀌면 같은 두 끝 규칙의 근거가 성립하지 않는다. 일반적인 최단 경로 알고리즘을 선택하거나 다른 제한 조건을 활용해야 한다. 이름에 BFS가 있다는 이유로 모든 그래프에 적용하지 않는다.
기존 항목이 남는 것과 중복 처리는 다르다
거리 개선 전에 넣어 둔 항목은 덱 중간에 남아 있을 수 있다. 임의 위치에서 찾아 제거하려고 하면 탐색 비용과 구현 복잡성이 늘어난다. 저장된 거리를 함께 둔 항목은 꺼낼 때 유효성을 확인하고 오래된 것을 건너뛰는 방식으로 처리할 수 있다.
이 기법은 우선순위 큐를 사용하는 최단 경로에서도 등장하지만 자료구조의 순서 보장은 다르다. 오래된 항목을 무시하는 조건이 정확한지,거리 값이 변경된 후 어떤 항목이 유효한지 명확히 해야 한다.
아래 0 비용 순환을 포함한 그래프에서 시작점 0과 정점 1의 거리는 0,정점 2는 1이다. 순환을 만나도 더 작은 값으로만 갱신하므로 종료한다. 지원하지 않는 비용 2를 실제로 방문하면 ValueError가 발생한다.
테스트에서는 순환이 없는 예제뿐 아니라 0 비용 순환,단절된 정점,같은 정점으로 가는 여러 경로를 포함한다. 작은 모든 그래프를 다른 기준 해법과 비교하면 발견 시점과 갱신 조건의 오류를 찾는 데 도움이 된다.
예제 코드
graph = {0: [(1, 0)], 1: [(0, 0), (2, 1)], 2: []}
print(sorted(zero_one_distances(graph, 0).items()))
try:
zero_one_distances({0: [(1, 2)]}, 0)
except ValueError:
print('unsupported weight')실행 결과
[(0, 0), (1, 0), (2, 1)]
unsupported weight인덱스 접근·슬라이스·연속 저장의 차이
Python deque는 양끝 연산에 맞춰져 있으며 목록과 같은 모든 슬라이스 연산을 제공하는 것은 아니다. 가운데 원소를 반복해서 인덱스로 접근하는 작업에는 list 같은 다른 구조가 더 적합할 수 있다. API 사용 편의와 접근 복잡도를 함께 살핀다.
Rust VecDeque는 원형 버퍼의 유효 자료가 두 연속 구간으로 나뉘어 있을 수 있고 이를 다루는 as_slices와 연속 구간으로 정리하는 make_contiguous 같은 기능을 제공한다. 논리적으로 연속된 순서와 물리적으로 한 구간에 놓인 메모리는 같은 말이 아니다.
C++ deque는 임의 접근 반복자를 지원하지만 vector처럼 전체 원소가 하나의 연속 배열이라는 가정을 할 수 없다. 원시 포인터로 전체 범위를 넘기는 외부 API와 연결할 때는 그 요구와 컨테이너의 보장을 확인한다.
연속 버퍼로 복사하면 연결은 쉬워질 수 있지만 O(n) 시간과 추가 공간이 생긴다. 덱 선택 이후 이런 변환을 매번 수행한다면 전체 비용이 양끝 연산의 이점을 상쇄할 수 있다. 파이프라인 전체에서 자료가 어떻게 이동하는지 살펴야 한다.
반복 중 변경과 참조 무효화
덱을 순회하는 동안 끝에 추가하거나 제거하면 반복자의 의미가 달라질 수 있다. 언어와 컨테이너에 따라 예외가 나거나 반복자가 무효화되므로,한 언어의 동작을 다른 언어에도 그대로 적용하지 않는다.
C++에서는 덱 양끝 삽입이 원소 참조와 반복자에 미치는 영향이 서로 다르다. 공식 계약상 양끝 삽입은 반복자를 무효화하지만 기존 원소 참조는 유지한다. 중간 삽입은 다른 규칙을 가지므로 정확한 연산 단위로 확인한다.
Java ArrayDeque의 반복자는 구조 변경을 감지하는 fail-fast 동작을 제공하지만 이를 동시 접근의 정확성을 보장하는 장치로 사용해서는 안 된다. 같은 스레드의 논리 오류를 찾는 데 도움이 될 수 있어도 모든 경쟁 상태를 보장된 방식으로 검출하는 것은 아니다.
안전한 방식으로는 원본을 변경하지 않고 순회하거나,명시적으로 popleft하며 큐를 소진하는 while 반복을 사용할 수 있다. 스냅샷을 복사해 순회하면 변경 영향은 줄지만 추가 공간과 최신성 차이가 생긴다. 필요한 의미를 먼저 정한다.
스레드 안전한 끝 연산과 복합 절차
일부 라이브러리는 개별 끝 연산에 대한 동시 접근 보장을 제공하지만 “비어 있지 않으면 꺼낸다” 같은 여러 단계가 자동으로 원자적이 되는 것은 아니다. 확인 후 다른 소비자가 마지막 원소를 가져갈 수 있다.
공유 작업 전달이 목적이면 잠금·대기·종료를 포함한 큐 API가 더 적합할 수 있다. 덱은 자료 저장의 연산을 제공하고 생산자·소비자 조율은 별개의 기능이다. 직접 만든 RingDeque에는 어떠한 스레드 동기화도 없다.
작업 훔치기 스케줄러에서 소유자는 한쪽 끝,다른 작업자는 반대쪽 끝을 사용하는 아이디어가 등장할 수 있지만 범용 덱의 네 메서드를 여러 스레드에서 호출하는 것만으로 올바른 lock-free 스케줄러가 되지 않는다. 메모리 모델과 경쟁 상태 처리에 전문적인 설계가 필요하다.
동시성을 문서화할 때 지원하는 실행 모델,잠금 범위와 실패 계약을 적는다. 테스트에서 단일 스레드 연산열을 검사한 결과를 동시성 검증이라고 표현하지 않는다. 이 문서의 대조 검사는 자료구조 순서와 경계 처리에 한정된다.
메모리·용량·원소 수명
덱의 길이는 현재 보관한 원소 수이며 실제 할당량은 여유 슬롯,블록 관리 정보와 원소 객체를 포함할 수 있다. 값이 큰 객체의 참조라면 덱 자체가 작아도 그 객체가 살아 있게 만드는 보유 공간이 클 수 있다.
원소를 제거할 때 내부 참조를 비우는 것은 그 객체를 더 이상 필요 없이 붙잡지 않기 위해서다. 다른 곳에서 참조하면 객체는 계속 존재한다. 원소가 사라졌다고 프로세스 메모리가 즉시 같은 양만큼 줄어든다고 기대하지 않는다.
제한 maxlen은 덱이 보유하는 원소 수를 제한하지만 각 원소의 크기를 제한하지 않는다. 작은 항목 수 안에도 거대한 버퍼나 객체 그래프가 들어갈 수 있다. 바이트 예산이 필요하면 항목 크기와 공유 관계를 별도로 관리한다.
학습용 RingDeque는 자동 축소를 하지 않으므로 한 번 커진 용량을 재사용한다. 반복 작업에서는 재할당을 줄일 수 있지만 한 번의 큰 작업 후 장기간 작은 상태로 남으면 보유 공간이 커질 수 있다. 수명과 재사용 패턴에 맞춰 축소 정책을 선택한다.
기준 deque와 5,000단계 상태 비교
아래 검사는 RingDeque와 Python collections.deque에 같은 연산을 적용한다. 고정 시드로 앞·뒤 추가와 앞·뒤 제거를 5,000번 섞고 매번 전체 순서와 길이를 비교한다. 값에는 None과 중복 정수가 포함된다.
빈 상태의 제거는 IndexError를 내야 하며 이후에도 상태가 그대로여야 한다. 각 단계에서 head 범위와 size≤capacity도 확인한다. head가 여러 번 순환하고 확장 전후를 지나는 연산열이라 단순한 연속 append 테스트보다 많은 경계를 지나간다.
이 검사는 같은 Python 환경에서 재현 가능한 단일 스레드 검사다. 메모리 부족이나 스레드 경쟁을 검증하지 않으며,원형 인덱스와 네 끝 연산의 의미를 확인하는 용도다. 앞의 RingDeque 정의 뒤에 실행한다.
예제 코드
from collections import deque
from random import Random
rng = Random(31)
actual, expected = RingDeque(), deque()
for step in range(5000):
operation = rng.randrange(4)
if operation < 2:
value = rng.choice([None, -1, 0, 5])
if operation == 0:
actual.append(value); expected.append(value)
else:
actual.appendleft(value); expected.appendleft(value)
elif expected:
if operation == 2:
assert actual.pop() == expected.pop()
else:
assert actual.popleft() == expected.popleft()
else:
try:
actual.pop() if operation == 2 else actual.popleft()
except IndexError:
pass
else:
raise AssertionError('empty removal succeeded')
assert actual.to_list() == list(expected)
assert len(actual) == len(expected)
assert 0 <= actual._head < len(actual._data)
assert len(actual) <= len(actual._data)
print(5000)실행 결과
5000슬라이딩 최댓값 완전 열거 검사
다음 검사는 값 0,1,2로 만들 수 있는 길이 1부터 6까지의 모든 배열과 각 유효한 윈도 폭을 검사한다. 기준 결과는 각 구간을 직접 잘라 max로 계산한다. 효율은 낮지만 작은 입력의 정답을 구하는 독립적인 방법이다.
총 6,015개 배열·폭 조합을 비교한다. 같은 값만 있는 경우,오름차순·내림차순과 중복 패턴,폭 1과 전체 폭이 포함된다. 후보 지배 조건과 만료 경계의 오류를 찾는 데 유용하다.
단조 덱의 O(n) 증명은 각 인덱스의 삽입·제거 횟수로 별도 설명했다. 이 테스트는 작은 입력에서 구현과 계약이 일치하는지를 확인하는 것이다. 입력이 일반 숫자라는 전제를 벗어나는 NaN이나 일관되지 않은 비교 객체는 별도 계약이 필요하다.
예제 코드
from itertools import product
checks = 0
for length in range(1, 7):
for values in product(range(3), repeat=length):
for width in range(1, length + 1):
expected = [max(values[start:start + width])
for start in range(length - width + 1)]
assert window_maximum(values, width) == expected
checks += 1
print(checks)실행 결과
60150-1 BFS를 반복 완화와 대조하기
정점 3개에서 자기 간선을 제외한 방향 간선은 6개다. 각 간선을 없음·비용0·비용1 중 하나로 정하면 3^6=729개 그래프를 만들 수 있다. 모든 시작점에서 0-1 BFS를 실행해 반복 완화 방식의 거리 결과와 비교한다.
기준 해법은 가능한 모든 간선을 여러 차례 완화하여 더 짧은 거리로 갱신한다. 덱의 처리 순서에 의존하지 않는 다른 방식이므로 최초 발견을 잘못 확정하거나 0 비용 순환을 처리하지 못하는 오류를 찾는 데 도움이 된다.
총 2,187개 시작점별 거리 결과를 검사한다. 단절과 순환,같은 비용의 여러 경로가 포함된다. 범위가 작은 완전 열거이며 임의 가중치 지원을 의미하지 않는다. 앞의 zero_one_distances 정의 뒤에 실행한다.
예제 코드
from itertools import product
edges = [(a, b) for a in range(3) for b in range(3) if a != b]
checks = 0
for choices in product([-1, 0, 1], repeat=len(edges)):
graph = {a: [] for a in range(3)}
weighted = []
for (a, b), weight in zip(edges, choices):
if weight >= 0:
graph[a].append((b, weight))
weighted.append((a, b, weight))
for start in range(3):
distance = [99] * 3
distance[start] = 0
for _ in range(2):
for a, b, weight in weighted:
if distance[a] < 99:
distance[b] = min(distance[b], distance[a] + weight)
expected = {a: distance[a] for a in range(3) if distance[a] < 99}
assert zero_one_distances(graph, start) == expected
checks += 1
print(checks)실행 결과
2187덱을 선택할 때 확인할 사항
양 끝이 각각 어떤 의미를 갖는지 먼저 정한다. FIFO의 입력·출력인지,LIFO의 맨 위인지,단조 후보의 만료·지배 제거인지에 따라 같은 연산도 역할이 달라진다. 양끝을 모두 사용할 이유가 없다면 더 제한적인 인터페이스가 명확할 수 있다.
다음으로 가운데 접근,연속 버퍼 변환,반복자 수명과 동시 접근 요구를 확인한다. 언어마다 deque의 보장이 다르므로 다른 언어의 성능 설명을 그대로 가져오지 않는다. 제한 용량일 때 버림·실패·대기 중 어느 동작인지도 검토한다.
알고리즘에서는 원소 자체보다 인덱스·거리·만료 시점 같은 부가 상태가 필요할 수 있다. 무엇을 왜 제거해도 되는지 불변식으로 설명하고 작은 독립 기준 해법과 대조한다. 단순히 while과 pop을 조합했다고 올바른 단조 덱이나 최단 경로가 되는 것은 아니다.
덱의 장점은 두 끝을 효율적으로 조작하는 유연성이다. 그 유연성을 정확한 순서 규칙,경계 처리와 상태 의미에 연결했을 때 큐·스택을 넘어 윈도 분석과 제한 가중치 탐색 같은 문제에서도 활용할 수 있다.