배열·리스트·스택·큐 코드
노트의 개념을 Python 3로 옮긴 코드다. 표준 라이브러리만 쓰고, 파일 끝의 assert 예제가 그대로 실행된다. 복사해 python3 파일이름.py로 돌려 보자.
배열과 동적 배열
"""배열과 동적 배열: 용량을 두 배씩 늘리는 동적 배열과, 가운데 넣기·빼기의 옮기기 비용.
시간: 읽기·쓰기 O(1), 끝에 넣기 분할 상환 O(1), i번 자리에 넣기·빼기 O(n - i)
공간: O(n) — 용량은 크기의 두 배를 넘지 않는다
"""
def element_address(start: int, index: int, element_bytes: int) -> int:
"""배열 i번 칸의 주소 = 시작 + i × 칸 크기. 앞 칸을 보지 않는다."""
return start + index * element_bytes
class DynamicArray:
"""크기(size)와 용량(capacity)을 따로 들고, 가득 차면 두 배로 늘리는 배열."""
def __init__(self, capacity: int = 1) -> None:
self.capacity = capacity
self.slots: list = [None] * capacity
self.size = 0
self.moves = 0
def _check(self, index: int, upper: int) -> None:
if not 0 <= index < upper:
raise IndexError(index)
def _grow(self) -> None:
bigger = [None] * (self.capacity * 2)
bigger[: self.size] = self.slots[: self.size]
self.slots = bigger
self.capacity *= 2
def append(self, value) -> None:
"""끝에 넣는다. 가득 찼으면 먼저 용량을 두 배로 늘린다."""
self.insert(self.size, value)
def insert(self, index: int, value) -> None:
"""index 자리에 넣는다. 그 뒤의 값을 뒤에서부터 한 칸씩 민다."""
self._check(index, self.size + 1)
if self.size == self.capacity:
self._grow()
for position in range(self.size, index, -1):
self.slots[position] = self.slots[position - 1]
self.moves += 1
self.slots[index] = value
self.size += 1
def pop(self, index: int):
"""index 자리의 값을 빼서 돌려준다. 뒤의 값을 한 칸씩 당긴다."""
self._check(index, self.size)
value = self.slots[index]
for position in range(index, self.size - 1):
self.slots[position] = self.slots[position + 1]
self.moves += 1
self.size -= 1
self.slots[self.size] = None
return value
def __getitem__(self, index: int):
self._check(index, self.size)
return self.slots[index]
def to_list(self) -> list:
"""든 값을 파이썬 리스트로 돌려준다."""
return self.slots[: self.size]
if __name__ == "__main__":
assert element_address(2000, 7, 4) == 2028
assert element_address(1000, 5, 8) == 1040
array = DynamicArray(8)
for value in [3, 8, 1, 9, 4]:
array.append(value)
array.moves = 0
array.insert(1, 6)
assert array.to_list() == [3, 6, 8, 1, 9, 4]
assert array.moves == 4
array.moves = 0
assert array.pop(0) == 3
assert array.to_list() == [6, 8, 1, 9, 4]
assert array.moves == 5
growing = DynamicArray(1)
for value in range(1, 10):
growing.append(value)
assert growing.capacity == 16
assert growing[8] == 9
assert growing.moves == 0
for bad in (lambda: growing[9], lambda: growing.pop(9), lambda: growing.insert(11, 0)):
try:
bad()
raise AssertionError("범위 밖은 IndexError여야 한다")
except IndexError:
pass
print("ok")연결 리스트
"""연결 리스트: 단일 연결 리스트의 넣기·지우기·뒤집기와, 이중 연결 리스트의 O(1) 떼어 내기.
시간: i번째 읽기 O(n), 쥔 노드 뒤에 넣기 O(1), 값으로 지우기 O(n), 뒤집기 O(n)
공간: 노드마다 포인터 하나(이중이면 둘)가 더 든다. 뒤집기는 추가 공간 O(1)
"""
from __future__ import annotations
from dataclasses import dataclass
@dataclass
class Node:
"""단일 연결 리스트의 노드: 값과 다음 노드."""
value: int
next: Node | None = None
class SinglyLinkedList:
"""head만 들고 있는 단일 연결 리스트."""
def __init__(self, values: list[int]) -> None:
self.head: Node | None = None
for value in reversed(values):
self.head = Node(value, self.head)
def to_list(self) -> list[int]:
"""head부터 따라가며 값을 모은다."""
values = []
node = self.head
while node:
values.append(node.value)
node = node.next
return values
def hops_to(self, index: int) -> int:
"""index번 노드까지 next를 따라간 횟수. 없으면 IndexError."""
node = self.head
for _ in range(index):
if node is None:
break
node = node.next
if node is None:
raise IndexError(index)
return index
def find(self, value: int) -> Node:
"""값이 value인 첫 노드. 없으면 ValueError."""
node = self.head
while node and node.value != value:
node = node.next
if node is None:
raise ValueError(value)
return node
def insert_after(self, node: Node, value: int) -> int:
"""node 뒤에 새 노드를 넣고, 바꾼 포인터 수(2)를 돌려준다."""
created = Node(value, node.next)
node.next = created
return 2
def delete(self, value: int) -> int:
"""값이 value인 노드를 떼어 내고, 바꾼 포인터 수(1)를 돌려준다."""
if self.head is None:
raise ValueError(value)
if self.head.value == value:
# 첫 노드는 앞 노드가 없으니 head를 옮긴다
self.head = self.head.next
return 1
previous = self.head
while previous.next and previous.next.value != value:
previous = previous.next
if previous.next is None:
raise ValueError(value)
previous.next = previous.next.next
return 1
def reverse(self) -> int:
"""제자리에서 뒤집고, next를 바꾼 횟수를 돌려준다."""
previous = None
current = self.head
changes = 0
while current:
next_node = current.next
current.next = previous
changes += 1
previous = current
current = next_node
self.head = previous
return changes
@dataclass
class DoublyNode:
"""이중 연결 리스트의 노드: 값, 앞 노드, 뒤 노드."""
value: int
prev: DoublyNode | None = None
next: DoublyNode | None = None
def build_doubly(values: list[int]) -> list[DoublyNode]:
"""값들을 이중으로 이은 노드 목록."""
nodes = [DoublyNode(value) for value in values]
for left, right in zip(nodes, nodes[1:]):
left.next = right
right.prev = left
return nodes
def unlink(node: DoublyNode) -> int:
"""쥐고 있는 node를 O(1)에 떼어 내고, 바꾼 포인터 수를 돌려준다."""
changes = 0
if node.prev:
node.prev.next = node.next
changes += 1
if node.next:
node.next.prev = node.prev
changes += 1
node.prev = node.next = None
return changes
def forward(head: DoublyNode | None) -> list[int]:
"""head부터 next로 읽은 값."""
values = []
while head:
values.append(head.value)
head = head.next
return values
if __name__ == "__main__":
numbers = SinglyLinkedList([4, 8, 15, 16, 23])
assert numbers.hops_to(3) == 3
try:
numbers.hops_to(5)
raise AssertionError("없는 위치는 IndexError여야 한다")
except IndexError:
pass
linked = SinglyLinkedList([2, 4, 6])
assert linked.insert_after(linked.find(4), 5) == 2
assert linked.to_list() == [2, 4, 5, 6]
assert linked.delete(2) == 1
assert linked.to_list() == [4, 5, 6]
assert linked.delete(6) == 1
assert linked.to_list() == [4, 5]
reversing = SinglyLinkedList([1, 2, 3, 4])
assert reversing.reverse() == 4
assert reversing.to_list() == [4, 3, 2, 1]
empty = SinglyLinkedList([])
assert empty.reverse() == 0
assert empty.to_list() == []
three, five, seven, nine = build_doubly([3, 5, 7, 9])
assert unlink(seven) == 2
assert forward(three) == [3, 5, 9]
assert nine.prev is five
print("ok")스택
"""스택: 괄호 짝 맞추기와 후위 표기식 계산. 파이썬 리스트의 끝을 스택으로 쓴다.
시간: push·pop·peek O(1), 괄호 검사와 후위 계산은 글자·토큰 수에 대해 O(n)
공간: O(n) — 스택 깊이만큼
"""
PAIRS = {")": "(", "]": "[", "}": "{"}
def check_brackets(text: str) -> tuple[str, int]:
"""괄호를 검사해 (결과, 위치)를 돌려준다.
결과는 'balanced', 'mismatch'(짝이 틀린 닫는 괄호의 위치), 'unclosed'(남은 여는 괄호 수)다.
"""
stack: list[str] = []
for index, char in enumerate(text):
if char in "([{":
stack.append(char)
elif char in PAIRS:
if not stack or stack[-1] != PAIRS[char]:
return "mismatch", index
stack.pop()
if stack:
return "unclosed", len(stack)
return "balanced", len(text)
def evaluate_postfix(tokens: list[str]) -> int:
"""후위 표기식을 계산한다. 먼저 꺼낸 값이 오른쪽 피연산자다."""
operations = {
"+": lambda left, right: left + right,
"-": lambda left, right: left - right,
"*": lambda left, right: left * right,
}
stack: list[int] = []
for token in tokens:
if token not in operations:
stack.append(int(token))
continue
if len(stack) < 2:
raise ValueError(f"피연산자가 모자라다: {token}")
right = stack.pop()
left = stack.pop()
stack.append(operations[token](left, right))
if len(stack) != 1:
raise ValueError("식이 하나의 값으로 끝나지 않는다")
return stack[0]
if __name__ == "__main__":
stack: list[int] = []
popped = []
for operation in ["push 1", "push 2", "push 3", "pop", "push 4", "pop", "pop"]:
if operation == "pop":
popped.append(stack.pop())
else:
stack.append(int(operation.split()[1]))
assert popped == [3, 4, 2]
assert stack == [1]
assert check_brackets("([]{()})") == ("balanced", 8)
assert check_brackets("{[(])}") == ("mismatch", 3)
assert check_brackets("(()[{}]") == ("unclosed", 1)
assert check_brackets(")") == ("mismatch", 0)
assert check_brackets("") == ("balanced", 0)
assert evaluate_postfix("5 1 2 + 4 * + 3 -".split()) == 14
assert evaluate_postfix(["7"]) == 7
for bad in (["+"], ["1", "2"]):
try:
evaluate_postfix(bad)
raise AssertionError("틀린 식은 ValueError여야 한다")
except ValueError:
pass
print("ok")큐와 덱
"""큐와 덱: 리스트 pop(0) 큐의 옮기기 비용과, 덱으로 푸는 미끄러지는 창의 최댓값.
시간: deque의 양 끝 넣기·빼기 O(1), list.pop(0)은 O(n), 창 최댓값은 전체 O(n)
공간: 창 최댓값의 덱은 O(k)
"""
from collections import deque
def pop_front_moves(count: int) -> int:
"""리스트 앞에서 count번 꺼낼 때 한 칸씩 당기는 값의 총수 = n(n - 1) / 2."""
items = list(range(count))
moves = 0
while items:
moves += len(items) - 1
items.pop(0)
return moves
def sliding_window_max(values: list[int], width: int) -> list[int]:
"""길이 width의 창마다 최댓값. 덱에는 인덱스를 값이 큰 것부터 남긴다."""
if width <= 0:
raise ValueError("창 길이는 1 이상이다")
window: deque[int] = deque()
result = []
for index, value in enumerate(values):
if window and window[0] <= index - width:
window.popleft()
# 새 값보다 작거나 같은 값은 다시는 최댓값이 될 수 없다
while window and values[window[-1]] <= value:
window.pop()
window.append(index)
if index >= width - 1:
result.append(values[window[0]])
return result
if __name__ == "__main__":
queue: deque[str] = deque()
served = []
for operation in ["A", "B", "C", None, "D", None]:
if operation is None:
served.append(queue.popleft())
else:
queue.append(operation)
assert served == ["A", "B"]
assert list(queue) == ["C", "D"]
assert pop_front_moves(5) == 10
assert pop_front_moves(10_000) == 49_995_000
assert pop_front_moves(0) == 0
assert sliding_window_max([1, 3, -1, -3, 5, 3, 6, 7], 3) == [3, 3, 5, 5, 6, 7]
assert sliding_window_max([4, 2], 1) == [4, 2]
assert sliding_window_max([1, 2], 3) == []
data = [5, 1, 4, 2, 8, 3, 9, 0, 7]
expected = [max(data[start : start + 4]) for start in range(len(data) - 3)]
assert sliding_window_max(data, 4) == expected
print("ok")원형 버퍼
"""원형 버퍼: 고정 크기 배열의 끝과 처음을 이어 쓰는 큐. 가득 차면 거부하거나 가장 오래된 값을 덮어쓴다.
시간: 넣기·꺼내기 O(1) — 값을 옮기지 않는다
공간: O(capacity) — 처음에 한 번 잡고 더 늘리지 않는다
"""
class RingBuffer:
"""head(가장 오래된 칸), tail(다음에 쓸 칸), size(든 개수)로 움직이는 원형 버퍼."""
def __init__(self, capacity: int, overwrite: bool = False) -> None:
if capacity <= 0:
raise ValueError("크기는 1 이상이다")
self.slots: list = [None] * capacity
self.capacity = capacity
self.overwrite = overwrite
self.head = 0
self.tail = 0
self.size = 0
def push(self, value) -> bool:
"""값을 넣는다. 가득 차서 거부했으면 False."""
if self.size == self.capacity:
if not self.overwrite:
return False
# 가장 오래된 값이 밀려나므로 head도 함께 민다
self.head = (self.head + 1) % self.capacity
self.size -= 1
self.slots[self.tail] = value
self.tail = (self.tail + 1) % self.capacity
self.size += 1
return True
def pop(self):
"""가장 오래된 값을 꺼낸다. 비었으면 IndexError."""
if self.size == 0:
raise IndexError("빈 버퍼")
value = self.slots[self.head]
self.slots[self.head] = None
self.head = (self.head + 1) % self.capacity
self.size -= 1
return value
def contents(self) -> list:
"""오래된 순서로 든 값."""
return [self.slots[(self.head + offset) % self.capacity] for offset in range(self.size)]
if __name__ == "__main__":
# head 6, 개수 4인 크기 8 버퍼의 칸 위치
assert [(6 + offset) % 8 for offset in range(4)] == [6, 7, 0, 1]
assert (6 + 4) % 8 == 2
assert (7 + 1) & 7 == (7 + 1) % 8
ring = RingBuffer(4)
popped = []
rejected = []
for value in [1, 2, 3, None, 4, 5, 6, None, 7]:
if value is None:
popped.append(ring.pop())
elif not ring.push(value):
rejected.append(value)
assert popped == [1, 2]
assert rejected == [6]
assert ring.contents() == [3, 4, 5, 7]
assert (ring.head, ring.tail) == (2, 2)
log = RingBuffer(4, overwrite=True)
for value in range(1, 7):
assert log.push(value)
assert log.contents() == [3, 4, 5, 6]
assert log.head == 2
try:
RingBuffer(2).pop()
raise AssertionError("빈 버퍼에서 꺼내면 IndexError여야 한다")
except IndexError:
pass
print("ok")