수업 목표

본 수업은 파이썬의 핵심 동적 자료구조를 알고리즘 문제 풀이에 맞게 선택하고 적절히 조합하는 능력을 함양하는 것을 목표로 합니다. - 집합(set), 딕셔너리(dict)의 해시 테이블 기반 $O(1)$ 연산 원리를 이해하고 실전에 투입합니다. - 이진 힙(heapq)을 활용한 우선순위 큐(Priority Queue)의 $O(\log N)$ 삽입/삭제를 익히고, 이벤트 기반 정렬 스케줄링에 응용합니다. - 덱(deque), 스택의 $O(1)$ 양방향 연산 원리를 이해하고 슬라이딩 윈도우 문제에 적용합니다. - 트라이(Trie) 자료구조의 prefix 탐색 원리를 이해하고, 전화번호부 일관성 검증 문제에 적용합니다. - 행렬 회전이라는 인덱스 변환 논리를 파악하고, 대용량 $T$를 $T mod 4$로 단순화하는 주기성 활용 기법을 습득합니다. - 2진 허프만 트리 및 가변 진법($R$진) 허프만 트리를 구축하여 최적 가중치 코드 길이를 구하는 압축 알고리즘을 구현합니다.

학습 동기부여

알고리즘 설계에서 '어떤 알고리즘을 쓸까'만큼 중요한 것은 '어떤 자료구조에 데이터를 담을까'입니다. 수천 개의 데이터를 리스트에서 탐색하면 $O(N)$이지만, 집합에서 탐색하면 $O(1)$입니다. 이 단순한 선택 하나로 프로그램의 실행 속도가 수천 배 차이 날 수 있습니다. 특히 파이썬에는 set, dict, heapq, deque, defaultdict 등 강력한 내장 자료구조들이 사용하기 좋게 준비되어 있으며, 이들의 성능 특성을 손발처럼 익숙하게 다루는 것이 경쟁 프로그래밍과 실무 모두를 관통하는 핵심 역량입니다.

도입 스토리

도서관을 운영하는 방식으로 비유해 봅시다. 아무렇게나 쌓여있는 책 더미(리스트)에서 특정 책을 찾으려면 한 권씩 다 살펴봐야 하지만, 분류 번호(해시값)에 따라 정해진 선반(해시 테이블)에 꽂아둔 책은 단 한 번의 이동으로 찾을 수 있습니다. 누군가 예약한 책을 알림 순서대로 처리해주는 것은 우선순위 큐(Priority Queue)가 담당하고, 가장 최근에 반납된 책부터 빠르게 앞으로 꺼내고 뒤로도 보내는 작업은 덱(Deque)이 최적입니다. 또한 문자들의 빈도에 맞춰 가변 비트를 배정해 압축하는 허프만 코드는 우선순위 큐의 병합 시뮬레이션으로 완벽히 설계됩니다. 본 수업에서는 이러한 내장 및 사용자 정의 자료구조들이 빛나는 문제 상황을 직접 탐구해 봅니다.

1. 집합(Set)과 딕셔너리(Dict) — 해시 기반 $O(1)$ 연산

파이썬의 set과 dict는 모두 내부적으로 해시 테이블(Hash Table)을 사용합니다. 원소의 존재 여부 확인, 삽입, 삭제가 평균 $O(1)$ 시간에 수행됩니다. 이는 같은 연산이 $O(\log N)$인 정렬된 자료구조나 $O(N)$인 리스트보다 훨씬 빠릅니다.

# 8023번: 중복 숫자 제거 — 파이썬 set 자료구조로 1줄 해결
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
print(len(set(a)))  # set이 중복을 자동 제거 → O(N) 시간

2. 우선순위 큐(Priority Queue) — heapq

파이썬의 heapq 모듈은 최소 힙(Min-Heap)을 구현합니다. 가장 작은 값이 항상 최상단에 위치하여 $O(\log N)$ 시간에 삽입 및 추출이 가능합니다. 최대 힙이 필요한 경우 값을 부호 반전(-val)하여 구현합니다.

import heapq

# 최소 힙 사용 예시
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 8)
print(heapq.heappop(h))  # 1 출력 (최솟값 추출)

# 8015번: 식당 손님 — 이벤트 기반 스케줄링
events = []
for a, b in guests:
    heapq.heappush(events, (a, 1))   # 도착: +1
    heapq.heappush(events, (b, -1))  # 퇴장: -1  (같은 시간이면 퇴장이 먼저)

current = 0
max_guests = 0
for time, delta in sorted(events, key=lambda x: (x[0], x[1])):
    current += delta
    max_guests = max(max_guests, current)

3. 덱(Deque)과 스택 — 양방향 $O(1)$ 연산

파이썬의 collections.deque는 리스트와 달리, 앞쪽(appendleft, popleft) 및 뒤쪽(append, pop) 삽입/삭제가 모두 $O(1)$에 동작합니다. 슬라이딩 윈도우의 범위 밖으로 나간 인덱스를 앞에서 제거하는 데 최적입니다.

from collections import deque

# 슬라이딩 윈도우 최소값 (Deque 활용)
dq = deque()  # 인덱스를 저장 (값은 a[i]로 접근)
for i in range(n):
    while dq and dq[0] < i - k + 1:  # 범위 밖 인덱스 제거
        dq.popleft()
    while dq and a[dq[-1]] >= a[i]:  # 단조 증가 유지
        dq.pop()
    dq.append(i)
    if i >= k - 1:
        print(a[dq[0]])  # 현재 윈도우의 최솟값

4. 트라이(Trie) — 접두사 탐색의 핵심 자료구조

트라이는 문자열의 공통 접두사를 공유하여 저장하는 트리 자료구조입니다. $N$개의 문자열에서 특정 문자열의 접두사 존재 여부를 $O(L)$ 시간(L = 문자열 길이)에 확인할 수 있습니다. 파이썬에서는 딕셔너리를 중첩해 간단하게 구현합니다.

# 8024번: 전화번호 목록 — 정렬 기반 O(N log N) 최적 풀이
def is_consistent(phones):
    phones.sort()
    for i in range(len(phones) - 1):
        if phones[i + 1].startswith(phones[i]):
            return False
    return True

# 참고: Trie 기반 풀이 (교육 목적)
def make_trie():
    return {}

def insert(trie, phone):
    node = trie
    for ch in phone:
        node = node.setdefault(ch, {})
    node['$'] = True  # 끝 표시

def check_prefix(trie, phone):
    node = trie
    for ch in phone:
        if '$' in node:   # 이미 완성된 번호가 이 경로에 있음
            return False  # → 현재 번호가 그 번호의 접두사
        if ch not in node:
            return True
        node = node[ch]
    return '$' not in node

5. 행렬 회전과 주기성 활용

$N \times N$ 행렬을 시계 방향으로 90도 회전하면, 원래 $(r, c)$ 위치의 원소가 $(c, N-1-r)$ 위치로 이동합니다. 회전을 4번 수행하면 원래 상태로 돌아오는 주기성이 있으므로, $T$번 회전은 $T \bmod 4$번 회전으로 간소화됩니다.

# 8025번: 행렬 회전 — O(N^2 * (T mod 4)) 시간
def rotate_cw(matrix):
    # 시계 방향 90도 회전: (r,c) → (c, N-1-r)
    return [list(row) for row in zip(*matrix[::-1])]

n, t = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]

t_effective = t % 4
for _ in range(t_effective):
    matrix = rotate_cw(matrix)

for row in matrix:
    print(*row)

6. 허프만 코딩과 우선순위 큐

허프만 코딩은 데이터 압축에 널리 사용되는 그리디 알고리즘입니다. 문자열 속 문자의 등장 빈도수를 계산한 후, 빈도가 가장 낮은 두 노드를 우선순위 큐(heapq)에서 꺼내어 합치고 다시 넣는 과정을 반복하여 이진 트리를 구성합니다. 총 비트 수는 모든 병합 연산에서 합쳐진 빈도수의 누적 합으로 구해집니다.

# 8026번: 허프만 트리 구축 — 빈도수 기반 이진 트리 병합
import heapq

def solve_huffman(line):
    n = len(line)
    freq = {}
    for char in line:
        freq[char] = freq.get(char, 0) + 1
        
    ascii_bits = n * 8
    # 문자의 종류가 1가지인 경우 예외 처리
    if len(freq) == 1:
        return ascii_bits, n
        
    heap = []
    counter = 0  # heapq 비교 충돌 방지용 고유 번호
    for char, f in freq.items():
        heapq.heappush(heap, (f, counter, char))
        counter += 1
        
    total_cost = 0
    while len(heap) > 1:
        f1, _, node1 = heapq.heappop(heap)
        f2, _, node2 = heapq.heappop(heap)
        sum_f = f1 + f2
        total_cost += sum_f
        heapq.heappush(heap, (sum_f, counter, [node1, node2]))
        counter += 1
        
    return ascii_bits, total_cost

4. 가변 진법 허프만 코딩 최적화

$R$진법 허프만 코딩은 한 번에 $R$개의 노드를 하나의 부모 노드로 합칩니다. 이 과정에서 마지막 단계에 합칠 노드가 $R$개에 부합하지 않는 불균형이 생길 수 있으므로, 초기 큐 구성 단계에서 0짜리 더미 노드를 추가해야 합니다. - 추가해야 할 더미 노드의 개수 $d$: (R - 1) - ((N - 1) % (R - 1)) (단, (N - 1) % (R - 1) != 0 인 경우) 더미 노드를 보강한 뒤 최소값 $R$개를 꺼내어 병합해 나갑니다.

# 8027번: 가변 진법 허프만 — 더미 노드 보강 및 R진 트리 병합
def get_min_wpl(n, r, freq):
    # R진법 매칭을 위한 더미 노드 개수 계산
    rem = (n - 1) % (r - 1)
    if rem != 0:
        dummy_count = (r - 1) - rem
        freq.extend([0] * dummy_count)
        
    heap = []
    for f in freq:
        heapq.heappush(heap, f)
        
    total_wpl = 0
    while len(heap) > 1:
        curr_sum = 0
        for _ in range(r):
            if heap:
                curr_sum += heapq.heappop(heap)
        total_wpl += curr_sum
        heapq.heappush(heap, curr_sum)
        
    return total_wpl

자주 하는 실수 & 오류 예방

- Trie 메모리 관리: Trie는 자식 노드를 담기 위해 다수의 딕셔너리나 고정 배열을 생성하므로 문자열 개수가 $100,000$개를 넘어가면 메모리 제한을 초과하기 쉽습니다. 파이썬에서는 `__slots__` 지시자를 통해 메모리를 최적화하거나, 단순 해싱 기법을 고려해야 합니다. - heapq 튜플 비교 충돌: heapq에 (우선순위, 객체) 형태로 튜플을 삽입할 때, 우선순위 값이 같으면 두 번째 인자인 객체끼리 비교 연산을 수행합니다. 이때 객체에 비교 연산자(__lt__)가 오버로딩되어 있지 않다면 TypeError가 발생합니다. 이를 방지하기 위해 (우선순위, 카운터, 객체) 형태로 고유한 카운터 정수를 중간에 삽입하여 객체 간 비교가 일어나지 않도록 강제해야 합니다. - Deque의 시간 복잡도 이해: 리스트의 `pop(0)` 또는 `insert(0, x)`는 원소 이동 비용으로 인해 $O(N)$이지만, collections.deque의 `popleft()` 및 `appendleft()`는 무조건 $O(1)$입니다. 큐/덱 시뮬레이션에서는 반드시 deque를 사용하십시오.

핵심 정리

자료구조	파이썬 구현체	주요 연산 시간 복잡도	핵심 용도
해시 집합	set	$O(1)$	중복 제거, 원소 존재 여부 고속 판정
해시 맵	dict / defaultdict	$O(1)$	키-값 쌍 보관, 등장 빈도 카운팅, 방문 위치 기록
우선순위 큐	heapq (최소 힙)	$O(\log N)$	최솟값/최댓값 상시 추출, 허프만 트리 병합 시뮬레이션
양방향 큐	collections.deque	$O(1)$	FIFO 큐 연산, 슬라이딩 윈도우 최대/최소값 관리
트라이 (Trie)	클래스 직접 구현	$O(L)$ (L: 문자열 길이)	문자열의 공통 접두사(Prefix) 고속 검색 및 접두사 겹침 판정

실습 문제

번호	문제 제목	출처	난이도	핵심 알고리즘 / 자료구조
8023	중복 숫자 제거	CSES	쉬움	해시 집합(set) 활용
8024	전화번호 목록	SPOJ	보통	Trie 활용 접두사 일관성 검사
8025	행렬 회전	SPOJ	보통	행렬 인덱스 시뮬레이션 및 주기성
8026	허프만 트리 구축	POJ	보통	우선순위 큐(heapq) 이진 트리 병합
8027	가변 진법 허프만	SPOJ	어려움	R진 허프만 트리 및 더미 노드 설계