자료구조 심화

1. 트리(Tree)

👉 정의

• 계층적(hierarchical) 자료구조
• 루트(root)에서 시작해 자식(child)으로 이어짐
• 대표적으로 이진 트리(Binary Tree)

🔹 이진 탐색 트리 (BST)

• 왼쪽 서브트리: 루트보다 작은 값
• 오른쪽 서브트리: 루트보다 큰 값
• 평균 탐색 시간: O(log N)
• 최악(편향트리): O(N)

코드

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 not node:
            return Node(key)
        if key < node.key:
            node.left = self._insert(node.left, key)
        else:
            node.right = self._insert(node.right, key)
        return node

    def search(self, key):
        return self._search(self.root, key)

    def _search(self, node, key):
        if not node or node.key == key:
            return node
        if key < node.key:
            return self._search(node.left, key)
        return self._search(node.right, key)

 

---

2. 힙(Heap)

👉 정의

• 완전 이진트리 기반의 자료구조
• 부모 노드가 자식보다 크거나(Max Heap) 작음(Min Heap)

👉 시간 복잡도

• 삽입/삭제: O(log N)
• 최댓값/최솟값 접근: O(1)

코드

import heapq

# 최소 힙
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 2)
heapq.heappush(min_heap, 8)
print(heapq.heappop(min_heap))  # 2

# 최대 힙 (음수로 변환해서 구현)
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -2)
heapq.heappush(max_heap, -8)
print(-heapq.heappop(max_heap))  # 8

---

3. 그래프(Graph)

👉 정의

• 정점(Vertex) + 간선(Edge)
• 방향 그래프, 무방향 그래프, 가중치 그래프

👉 표현 방법

• 인접 리스트 (Adjacency List): O(V+E) → 공간 효율적
• 인접 행렬 (Adjacency Matrix): O(V²) → 빠른 간선 확인

코드

# 인접 리스트 표현
graph = {
    1: [2, 3],
    2: [4],
    3: [4],
    4: [5],
    5: []
}

# BFS 탐색
from collections import deque

def bfs(start):
    visited = set()
    q = deque([start])
    while q:
        node = q.popleft()
        if node not in visited:
            print(node, end=" ")
            visited.add(node)
            q.extend(graph[node])

bfs(1)  # 1 2 3 4 5

---

자료구조·알고리즘 틀 내 진도:

• 자료구조 개요 (10%)
• 알고리즘 개요 (10%)
• 자료구조 심화 (트리/힙/그래프 구현) (20%)

➡️ 현재까지 자료구조·알고리즘 40% 완료

 

전체 CS 틀 내 진도:

• 자료구조·알고리즘(30%) 중 40% 달성
  ➡️ 전체 CS 대비 12% 완료