10000COW

B-트리란? B-트리(B-tree)는 데이터베이스와 파일 시스템에 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드에 여러 개의 데이터를 저장한다. 차수가 p인 B-트리의 특성 1)적어도 노드의 반은 채워야 한다. 즉, root와 leaf를 제외한 모든 노드의 pointer 수 = 서브트리 수 = 최소 ⌈p / 2⌉개, 최대 p 개 2) root는 pointer를 2개 이상 가져야 한다. 즉, root의 서브트리의 수 >= 2 3) 모든 leaf는 같은 level (즉, 균형 트리이다) 4) 노드의 key 개수 leaf가 아닌 노드: pointer 수 - 1 개 = 서브트리 수 - 1개 (아래 B-트리 기본 구조 그림을 보면, key의 개수는 (pointer 개수 - 1)일 수 밖..

BFS는 큐를 이용한 반복 구조로 구현한다. 먼저 큐를 이용한 BFS Pseudo code를 보면서 어떻게 구현해야할지 생각해보자. 1) 큐를 이용한 BFS Pseudo code BFS(G, start_v) let Q be a queue label start_v as discovered Q.enqueue(start_v) while Q is not empty do v := Q.dequeue() if v is the goal then return v for all edges from v to w in G.adjacentEdges(v) do if w is not labeled as discovered then label w as discovered w.parent := v Q.enqueue(w) 2) 큐를 이..

1) 재귀를 이용한 DFS 구현 Pseudo code G는 그래프, v는 정점(vertex)일 때, DFS(G,v) lable v as discovered for all directed edges from v to w that are in G.adjacentEdges(v) do if vertex w is not labeled as discovered then recursively call DFS(G,w) 재귀를 이용한 DFS 구현 Python code def recursive_dfs(v, discovered=[]): discovered.append(v) for w in graph[v]: if w not in discovered: discovered = recusrive_dfs(w, discovered) ..