코딩테스트 자료구조 파이썬 완전 정복 – 빈출 10선과 실전 코드

# 리스트 핵심 패턴 – 코딩테스트 실전
arr = [3, 1, 4, 1, 5, 9, 2, 6]

# 정렬 (Timsort, O(n log n))
arr.sort()                        # 오름차순 정렬 (in-place)
arr.sort(reverse=True)            # 내림차순 정렬
sorted_arr = sorted(arr, key=lambda x: -x)  # key 활용

# 슬라이싱 – O(k), k = 슬라이스 길이
sub = arr[2:5]

# 이진 탐색 – bisect 활용 (정렬된 배열에서 O(log n))
import bisect
pos = bisect.bisect_left(arr, 4)  # 4가 삽입될 위치 반환

# 2차원 배열 초기화 – 주의: [[0]*n]*m 은 얕은 복사!
matrix = [[0] * 4 for _ in range(3)]  # 3×4 행렬 안전 초기화

# 스택 – 괄호 유효성 검사 (카카오 빈출 유형)
def is_valid(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in mapping:                   # 닫는 괄호
            top = stack.pop() if stack else '#'
            if mapping[char] != top:
                return False
        else:                                 # 여는 괄호
            stack.append(char)

    return not stack                          # 스택이 비어있어야 유효

print(is_valid("({[]})"))   # True
print(is_valid("({[})"))    # False

from collections import deque

# BFS – 최단 경로 탐색 (가장 빈출 큐 활용)
def bfs(graph: dict, start: int) -> list:
    visited = set([start])
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()        # O(1) – 리스트 pop(0) 대신!
        order.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order

graph = {1: [2, 3], 2: [4], 3: [4, 5], 4: [], 5: []}
print(bfs(graph, 1))   # [1, 2, 3, 4, 5]

from collections import deque

# 슬라이딩 윈도우 최대값 – 단조 덱(Monotonic Deque) 패턴
def sliding_window_max(nums: list, k: int) -> list:
    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

print(sliding_window_max([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]

from collections import defaultdict, Counter

# --- 패턴 1: defaultdict – KeyError 없이 안전하게 ---
graph = defaultdict(list)     # 그래프 인접 리스트
graph[1].append(2)            # 키 없어도 자동 초기화

freq = defaultdict(int)       # 빈도수 카운터
for char in "abracadabra":
    freq[char] += 1

# --- 패턴 2: Counter – 빈도수 특화 ---
counter = Counter("abracadabra")
print(counter.most_common(2)) # [('a', 5), ('b', 2)]

# 두 Counter 연산
c1 = Counter("aab")
c2 = Counter("abb")
print(c1 + c2)   # Counter({'a': 3, 'b': 3})
print(c1 & c2)   # Counter({'a': 1, 'b': 1}) – 교집합(최솟값)

# --- 패턴 3: 애너그램 판별 ---
def is_anagram(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)

print(is_anagram("anagram", "nagaram"))  # True

# 집합 핵심 연산
a = {1, 2, 3, 4, 5}
b = {3, 4, 5, 6, 7}

print(a | b)   # 합집합: {1, 2, 3, 4, 5, 6, 7}
print(a & b)   # 교집합: {3, 4, 5}
print(a - b)   # 차집합: {1, 2}
print(a ^ b)   # 대칭차: {1, 2, 6, 7}

# 방문 체크 – BFS/DFS에서 set이 list보다 O(1) vs O(n)
visited = set()
visited.add(node)
if node not in visited:   # O(1) 탐색
    pass

# 중복 제거 후 정렬
nums = [3, 1, 4, 1, 5, 9, 2, 6, 5]
unique_sorted = sorted(set(nums))  # [1, 2, 3, 4, 5, 6, 9]

import heapq

# 최소 힙 기본
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)
print(heapq.heappop(heap))   # 1 (최솟값 반환)

# 최대 힙 – 음수 변환 트릭
max_heap = []
for num in [3, 1, 5, 2]:
    heapq.heappush(max_heap, -num)
print(-heapq.heappop(max_heap))  # 5 (최댓값 반환)

# K번째 최솟값 – O(n log k) 패턴
def kth_smallest(nums: list, k: int) -> int:
    heapq.heapify(nums)          # 리스트를 힙으로 O(n)
    for _ in range(k - 1):
        heapq.heappop(nums)
    return heapq.heappop(nums)

# 다익스트라 핵심 패턴 – (거리, 노드) 튜플로 관리
def dijkstra(graph: dict, start: int) -> dict:
    dist = defaultdict(lambda: float('inf'))
    dist[start] = 0
    pq = [(0, start)]           # (거리, 노드)

    while pq:
        d, node = heapq.heappop(pq)
        if d > dist[node]:
            continue            # 이미 더 짧은 경로 존재
        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
    return dist

# 트라이 – 딕셔너리 기반 구현
class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            # 해당 문자 키가 없으면 새 노드 생성
            node = node.setdefault(char, {})
        node['#'] = True          # 단어 종료 마커

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node:
                return False
            node = node[char]
        return '#' in node        # 종료 마커 확인

    def starts_with(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True               # 접두사만 존재해도 True

# 사용 예시
trie = Trie()
for word in ["apple", "app", "application"]:
    trie.insert(word)

print(trie.search("app"))          # True
print(trie.search("ap"))           # False
print(trie.starts_with("appl"))    # True

from collections import deque

# 인접 리스트 표현 – 공간 효율적
graph = defaultdict(list)
edges = [(1,2),(1,3),(2,4),(3,4),(3,5)]
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)   # 무방향 그래프

# DFS – 재귀 구현
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node, end=' ')
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

# DFS – 스택 반복 구현 (재귀 깊이 제한 우회)
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    result = []
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            result.append(node)
            # 방문 순서 유지를 위해 역순 삽입
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    return result

# BFS – 최단 거리 계산
def bfs_distance(graph, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in dist:
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)
    return dist

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))  # 각 노드가 자기 자신의 부모
        self.rank = [0] * n           # 트리 높이 관리

    def find(self, x: int) -> int:
        # 경로 압축 – find 호출 시 부모를 루트로 직접 연결
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False             # 이미 같은 집합 (사이클 감지)
        # 랭크 기반 합치기 – 높이가 낮은 트리를 높은 쪽에 붙임
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

# 크루스칼 알고리즘 – MST (최소 신장 트리) 핵심 패턴
def kruskal(n: int, edges: list) -> int:
    uf = UnionFind(n)
    edges.sort(key=lambda x: x[2])  # 가중치 기준 정렬
    total = 0
    for u, v, weight in edges:
        if uf.union(u, v):           # 사이클 없을 때만 추가
            total += weight
    return total

[입문]
리스트 → 딕셔너리 → 집합
    ↓
[중급]
스택 → 큐(deque) → 힙(heapq)
    ↓
[고급]
그래프(BFS/DFS) → 유니온 파인드 → 트라이
    ↓
[심화]
세그먼트 트리 → 펜윅 트리 → 스패닝 트리

import sys
sys.setrecursionlimit(10**6)

import sys
input = sys.stdin.readline

# 느림
result = []
for i in range(n):
    result.append(i * 2)

# 빠름
result = [i * 2 for i in range(n)]

matrix = [[1,2,3],[4,5,6],[7,8,9]]

# 전치(Transpose)
transposed = list(map(list, zip(*matrix)))

# 90도 시계 방향 회전
rotated = list(map(list, zip(*matrix[::-1])))