목록DS (10)

YYYEJI

[DS] 최소 신장 트리(Minimum Spanning Tree)란?

신장 트리(Spanning Tree) 란? 한 Graph의 모든 vertex를 연결하는 cycle이 없는 sub graph입니다. - 스패닝 트리는 (n-1)개의 edge를 가진다. - 스패닝 트리는 DFS, BFS 알고리즘을 이용해 찾을 수 있다. (움직인 edge를 연결하면 된다.) - Cycle이 있어서는 안된다. 아래와 같은 그래프가 존재할 때 DFS, BFS spanning tree를 만들어보면 ↓↓↓ DFS ↓↓↓ https://yyyeji.tistory.com/379 [DS] 깊이 우선 탐색(DFS)이란? 하나의 vertax로부터 모든 vertex를 한 번씩 방문하는 그래프 탐색이 있습니다. ↓↓↓ 그래프란? ↓↓↓ https://yyyeji.tistory.com/378 [DS] 그래프(Gr..
Data structure 2023. 1. 24. 18:26
[DS] 넓이 우선 탐색(BFS)이란?

하나의 vertax로부터 모든 vertex를 한 번씩 방문하는 그래프 탐색이 있습니다. ↓↓↓ 그래프란? ↓↓↓ https://yyyeji.tistory.com/378 [DS] 그래프(Graphs)의 종류와 관련 용어 그래프(Graphs)란? 객체 사이의 연결 관계를 나타낼 수 있는 자료 구조입니다. 그래프(graph)는 vertax의 집합과 edge의 집합으로 이루어집니다. - vertax = {a, b, c, d, e} - edge = {(a, b), (a, e), (b, c), (c, d), (c, e yyyeji.tistory.com 아래에 BFS 방문 예제와 코드가 있습니다. 깊이 우선 탐색(Depth First Search)이란? 그래프 탐색에서 넓이 부분을 먼저 탐색하는 알고리즘이며, 큐(q..
Data structure 2023. 1. 5. 21:09
[DS] 깊이 우선 탐색(DFS)이란?

하나의 vertax로부터 모든 vertex를 한 번씩 방문하는 그래프 탐색이 있습니다. ↓↓↓ 그래프란? ↓↓↓ https://yyyeji.tistory.com/378 [DS] 그래프(Graphs)의 종류와 관련 용어 그래프(Graphs)란? 객체 사이의 연결 관계를 나타낼 수 있는 자료 구조입니다. 그래프(graph)는 vertax의 집합과 edge의 집합으로 이루어집니다. - vertax = {a, b, c, d, e} - edge = {(a, b), (a, e), (b, c), (c, d), (c, e yyyeji.tistory.com 아래에 DFS 방문 예제와 코드가 있습니다. 깊이 우선 탐색(Depth First Search)이란? 그래프 탐색에서 깊은 부분을 먼저 탐색하는 알고리즘이며, 재귀함..
Data structure 2023. 1. 5. 20:08
[DS] 그래프(Graphs)의 종류와 관련 용어

그래프(Graphs)란? 객체 사이의 연결 관계를 나타낼 수 있는 자료 구조입니다. 그래프(graph)는 vertex의 집합과 edge의 집합으로 이루어집니다. - vertex = {a, b, c, d, e} - edge = {(a, b), (a, e), (b, c), (c, d), (c, e), (d, e)} 그래프(graph) 관련 용어(Terminology) Adjacent - 두 vertex 간의 edge가 존재함 Path - 두 vertax 간에 edge로서 연결되는 vertex의 sequence Length of a path - path를 구성하는 edge 개수 Connected - 두 vertex 간에 path가 존재함 Connected components - 연결된 원소의 그룹 Cycle ..
Data structure 2023. 1. 5. 18:26
[DS] 이진탐색트리(Binary Search Tree)란?

이진탐색트리(Binary Search Tree)란? Left subtree에 속한 모든 node의 값(key)은 root의 값(key)보다 작고, Right subtree에 속한 모든 node의 값(key)보다 큰 이진 트리(binary tree)입니다. + Empty tree도 이진탐색트리입니다. + 모든 subtree도 이진탐색트리입니다. + 모든 노드(node)의 값(key)이 겹치면 안 됩니다. Binary Search Tree를 구현하기 위한 ADT 구현 class bst_node { public: string id; string name; double score; bst_node *left, *right; bst_node(); bst_node(string s1, string s2, double..
Data structure 2023. 1. 4. 23:43
[DS] 힙(Heap)이란?

힙(Heap)이란? 완전이진트리(complete binary tree)이면서 최대트리(max-tree)를 만족하는 이진트리(binary tree)입니다. 힙(heap)은 저장된 원소 중 가장 값(key)이 큰 원소를 제공하는 데이터 구조입니다. 완전이진트리(complete binary tree)란? https://yyyeji.tistory.com/370 [DS] 이진트리(Binary Tree)란? 이진트리(Binary Tree)란? 각 노드가 최대 두 개의 자식을 갖는 트리입니다. - 유한개(>=0)의 node로 이루어짐 - empty이거나 root와 두개의 disjoint binary tree로 구성됨 이진트리(binary tree)에는 순서(order)가 yyyeji.tistory.com n개의 노드..
Data structure 2023. 1. 3. 00:41
[DS] 트리순회(Tree Traversal)란?

트리순회(Binary tree Traversal)란? 모든 node에 대하여 중복이나 누락없이 일정 순서로 모든 node를 방문하는 방법을 나타냅니다. ① 전위순회(preorder traversal) - node → left → right 현재 node를 방문 후 left, right node를 방문 ② 중위순회(inorder traversal) - left → node → right left node 방문 후 현재 node, right node를 방문 ③ 후위순회(postorder traversal) - left → right → node left, right node 방문 후 현재 node를 방문 아래 트리로 예를 들어보겠습니다. ① 전위순회(preorder traversal) a - b - d - ..
Data structure 2022. 12. 29. 21:20
[DS] 이진트리(Binary Tree)란?

이진트리(Binary Tree)란? 각 노드가 최대 두 개의 자식을 갖는 트리입니다. - 유한개(>=0)의 node로 이루어짐 - empty이거나 root와 두개의 disjoint binary tree로 구성됨 이진트리(binary tree)에는 순서(order)가 있습니다. Disjoint binary tree - left subtree - right subtree 이진트리(Binary tree) 관련 용어(Terminology) 완전 이진 트리(Complete binary tree)이란 n개의 노드(node)가 level 순서로 모두 채워진 이진트리(binary tree)입니다. 노드(node)가 위에서 아래로 왼쪽부터 오른쪽으로 잘 채워져 있으면 됩니다. 정 이진트리(Full binary tree)..
Data structure 2022. 12. 29. 20:56
이전 Prev 1 2 Next 다음