고급 자료구조 (이터레이터, 제너레이터, 컴프리헨션, 스택·큐, 트리, 그래프)

앞서 파이썬의 메모리 관리 메커니즘과 객체 지향 프로그래밍(OOP) 설계 기법을 살펴보았습니다. 이번 글에서는 대용량 데이터를 효율적으로 다루고 복잡한 관계를 모델링하는 파이썬의 고급 자료구조와 알고리즘 패턴(이터레이터, 제너레이터, 컴프리헨션, 스택·큐, 연결 리스트, 해시 테이블, 트리, 그래프)의 모든 것을 완벽하게 파헤쳐 보겠습니다.

1. 이터레이터 (Iterator)와 이터러블 (Iterable)

파이썬의 이터레이터(Iterator)는 데이터를 순차적으로 접근할 수 있는 표준화된 객체입니다. 모든 요소를 메모리에 한 번에 로드하지 않고 필요할 때마다 가져올 수 있습니다.

  • 이터러블 (Iterable): __iter__ 매직 메서드를 구현하고 있어 for 루프에 사용할 수 있는 객체입니다. (예: 리스트, 튜플, 문자열 등)

  • 이터레이터 (Iterator): __iter__와 __next__ 메서드를 모두 구현하여 실제로 반복을 수행하고 다음 값을 제공하는 객체입니다. 더 이상 반환할 값이 없으면 StopIteration 예외를 발생시킵니다.

# 리스트는 이터러블 객체
numbers = [1, 2, 3]
iterator = iter(numbers)

print(next(iterator))  # 출력: 1
print(next(iterator))  # 출력: 2

2. 제너레이터 (Generator)와 yield 키워드

제너레이터는 이터레이터를 가장 간단하고 메모리 효율적으로 만들 수 있는 도구입니다. 모든 값을 미리 만들지 않고 필요할 때마다 하나씩 생성하는 지연 평가(Lazy Evaluation) 방식을 사용합니다.

  • yield 키워드: 값을 반환한 후 함수의 상태(실행 위치, 지역 변수)를 일시 중지합니다. 다음에 next()가 호출되면 멈췄던 지점부터 다시 실행을 재개합니다.

  • 장점: 대규모 데이터셋 처리 시 메모리 사용량을 수백 배 이상 절약할 수 있습니다.

def count_up_to(max_num):
    n = 1
    while n <= max_num:
        yield n
        n += 1

gen = count_up_to(3)
print(next(gen))  # 출력: 1

3. 컴프리헨션 (Comprehension) 구문

컴프리헨션은 리스트, 딕셔너리, 셋(Set) 같은 이터러블 객체를 한 줄로 간결하고 직관적으로 생성할 수 있는 구문입니다. 일반 반복문보다 가독성이 높고 성능이 우수합니다.

  • 리스트 컴프리헨션: [표현식 for 항목 in 이터러블 if 조건문]

  • 딕셔너리 컴프리헨션: {키: 값 for 항목 in 이터러블 if 조건문}

  • 셋 컴프리헨션: {표현식 for 항목 in 이터러블 if 조건문}

# 1부터 10 사이의 짝수 제곱 리스트 생성
even_squares = [i ** 2 for i in range(1, 11) if i % 2 == 0]
print(even_squares)  # 출력: [4, 16, 36, 64, 100]

4. 선형 자료구조: 스택(Stack)과 큐(Queue)

  • 스택 (Stack): 후입선출(LIFO, Last In First Out) 원칙을 따르는 구조로, 파이썬에서는 리스트의 .append()와 .pop() 또는 collections.deque를 이용해 구현합니다.

  • 큐 (Queue): 선입선출(FIFO, First In First Out) 원칙을 따르며, 양쪽 끝에서 O(1) 연산을 지원하는 collections.deque를 사용하는 것이 가장 효율적입니다.

5. 연결 리스트 (Linked Lists)

데이터를 메모리상에 연속적으로 저장하지 않고, 노드(Node) 형태로 연결한 선형 자료구조입니다.

  • 구조: 데이터와 다음 노드를 가리키는 참조(next)로 구성됩니다.

  • 특징: 메모리 중간 삽입과 삭제가 O(1)로 매우 효율적이지만, 특정 인덱스 탐색은 O(n) 시간이 소요됩니다. 단일, 이중, 환형 연결 리스트로 나뉩니다.

6. 해시 테이블 (Hash Table)과 파이썬 딕셔너리

키(Key)를 값(Value)에 연결하여 저장하는 구조로, 해시 함수를 통해 인덱스를 계산하므로 평균 O(1)의 매우 빠른 검색·삽입·삭제 성능을 자랑합니다. 파이썬의 dict가 바로 이 해시 테이블로 구현되어 있습니다.

  • 키 요구사항: 딕셔너리의 키는 반드시 불변(Immutable) 객체여야 하는 해시 가능성(Hashability)을 만족해야 합니다.

7. 비선형 자료구조: 트리 (Trees)와 탐색 알고리즘

트리는 노드와 엣지로 연결된 계층적 데이터 구조입니다.

7.1 이진 트리 순회 (Traversal)

  • 전위 순회 (Pre-order): Root → Left → Right

  • 중위 순회 (In-order): Left → Root → Right (이진 탐색 트리에서 오름차순 정렬 결과 제공)

  • 후위 순회 (Post-order): Left → Right → Root (트리 삭제 및 자취 계산에 유용)

7.2 이진 탐색 트리 (BST)와 AVL 트리

  • 이진 탐색 트리 (BST): 왼쪽 자식 < 부모 < 오른쪽 자식 규칙을 만족하여 빠른 탐색을 돕지만, 편향될 경우 최악의 시간 복잡도 O(n)을 가집니다.

  • AVL 트리: 최초의 자가 균형 이진 탐색 트리(Self-Balancing BST)로, 모든 노드의 균형 인수(BF)가 -1, 0, 1을 유지하도록 회전(Rotation) 연산을 통해 높이를 자동 조절하여 항상 O(log n) 성능을 보장합니다.

8. 그래프 (Graphs)의 개념과 구현

그래프는 정점(Vertex)과 이들을 연결하는 간선(Edge)들의 집합으로 이루어진 비선형 자료구조입니다. 소셜 네트워크, 최단 경로(내비게이션) 등 복잡한 관계를 모델링하는 데 핵심적으로 사용됩니다.

  • 인접 행렬 (Adjacency Matrix): 2차원 리스트를 사용하여 연결 여부를 표현하며, 간선 조회는 빠르나 메모리 낭비가 발생할 수 있습니다.

  • 인접 리스트 (Adjacency List): 딕셔너리나 리스트의 리스트로 각 노드에 연결된 이웃 노드만 저장하여 메모리가 매우 효율적입니다.

답글 남기기