파이썬 자료구조 (2)

해시 테이블(Hash Table)

 

개념

해시 테이블은 데이터를 **키(Key)와 값(Value)**의 쌍으로 저장하는 자료구조입니다. 해시함수(Hash Function)를 통해 키를 특정 인덱스로 변환하여 해당 위치에 값을 저장합니다.

 

특징

• 평균 시간 복잡도 : O(1) (탐색, 삽입, 삭제)
• 키 충돌(Collision) 시에는 체이닝(Chaining) 또는 개방 주소법(Open Addressiong)으로 해결

장점

• 매우 빠른 검색 속도
• 다양한 키 타입 사용 가능

단점

• 해시 충돌 시 성능 저하 기능
• 메모리 사용량이 많을 수 있음

# Python Dictionary 사용
hash_table = {}
hash_table['apple'] = 10
hash_table['banana'] = 5
print(hash_table['apple'])  # 10

 

해시 충돌 처리 (체이닝 방식)

class HashTable:
    def __init__(self):
        self.size = 10
        self.table = [[] for _ in range(self.size)]

    def put(self, key, value):
        index = hash(key) % self.size
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)
                return
        self.table[index].append((key, value))

    def get(self, key):
        index = hash(key) % self.size
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

---

트리(Tree)

 

 

개념

트리는 하나의 루트 노드를 기준으로 계층적 구조를 표현하는 비선형 자료구조입니다. 노드는 자식 노드를 가질 수 있으며, 순환이 존재하지 않습니다.

 

용어정리

• 루트(Root) : 최상위 노드
• 리프(Leaf) : 자식 노드가 없는 노드
• 부모/자식 노드 : 상하 관계
• 서브트리(Subtree) : 특정 노드를 루트로 하는 하위 트리

사용 사례

• 디렉토리 구조
• 이진 탐색 트리 (검색 최적화)
• 파싱 트리(컴파일러, 수식 계산 등)

이진 탐색 트리 (Binary Search Tree)

왼쪽 자식 노드는 루트보다 작고, 오른쪽 자식 노드는 루트보다 큰 값

 

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, key):
        self.root = self._insert(self.root, key)

    def _insert(self, node, key):
        if node is None:
            return Node(key)
        if key < node.key:
            node.left = self._insert(node.left, key)
        else:
            node.right = self._insert(node.right, key)
        return node

---

힙(Heap)

 

개념

힙은 완전 이진 트리를 기반으로 한 우선순위 큐 자료구조입니다. 항상 루트 노드가 가장 크거나 가장 작습니다.

종류

• 최대 힙(Max Heap) : 부모 ≥ 자식 (루트가 최대)
• 최소 힙(Min Heap) : 부모 ≤ 자식 (루트가 최소)

사용 사례

• 우선순위 기반 스케줄러
• 힙 정렬 알고리즘
• 실시간 최댓값/최솟값 추출

import heapq
heap = []
heapq.heappush(heap, 4)
heapq.heappush(heap, 2)
heapq.heappush(heap, 7)
print(heapq.heappop(heap))  # 2 (최소값)

 

최대 힙 구현 (heapq는 최소 힙 기반)

import heapq
max_heap = []
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -1)
print(-heapq.heappop(max_heap))  # 10

 

---

그래프(Graph)

 

개념

그래프 **정점(Vertex)과 간선(Edge)**으로 이루어진 자료구조입니다. 순환 가능하며, 정점 간 복잡한 관계를 표현하는 데 적합합니다.

 

종류

• 방향 그래프 vs 무방향 그래프
• 가중치 그래프 vs 비가중치 그래프

사용 사례

• 소셜 네트워크, 도로 지도
• 추천 시스템, 웹 크롤링

표현 방식

1. 인접 리스트
2. 인접 행렬

# 인접 리스트
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

 

BFS/DFS 탐색 예시

from collections import deque

def bfs(graph, start):
    visited = []
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])
    return visited

 

# 그래프 구현 (인접 리스트 방식)
class Graph:
    def __init__(self):
        self.graph = {}
    
    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []
    
    def add_edge(self, vertex1, vertex2):
        if vertex1 in self.graph and vertex2 in self.graph:
            self.graph[vertex1].append(vertex2)
            self.graph[vertex2].append(vertex1)  # 무방향 그래프
    
    def display(self):
        for vertex in self.graph:
            print(f"{vertex}: {self.graph[vertex]}")

# 가중치 그래프
class WeightedGraph:
    def __init__(self):
        self.graph = {}
    
    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []
    
    def add_edge(self, vertex1, vertex2, weight):
        if vertex1 in self.graph and vertex2 in self.graph:
            self.graph[vertex1].append((vertex2, weight))
            self.graph[vertex2].append((vertex1, weight))

# 예제
g = Graph()
vertices = ['A', 'B', 'C', 'D']
for v in vertices:
    g.add_vertex(v)

g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'D')

print("그래프 구조:")
g.display()

 

자료구조                                         주요 목적                                               활용 사례

해시 테이블	빠른 탐색	캐시, 딕셔너리
트리	계층적 표현	디렉토리, 탐색 트리
힙	우선순위 관리	작업 큐, 힙 정렬
그래프	관계 표현	지도, SNS, 경로 탐색