C67 Chapter 14. DFS Def) 그래프 순회(Graph Traversal) - 하나의 정점에서 시작하여 모든 정점들을 한 번씩 방문하는 작업 - 많은 문제들이 그래프 순회를 이용하여 해결될 수 있음. ex. 두 정점 사이의 연결 경로가 있는지 검사, 최단 거리 검사 등등 - 대표적인 그래프 순회 방법으로는 깊이 우선 탐색(Depth First Search), 너비 우선 탐색(Breadth First Search) Def) 깊이 우선 탐색(DFS, Depth First Search) - 현재 정점과 인접한 정점 중 하나를 선택하여 이동하는 과정을 반복. 더이상 이동할 정점이 없을 경우, 뒤쪽으로 백트래킹(Backtracking)하여 다시 이동할 경로를 탐색. - 시작 정점으로부터 거리가 멀어지는(깊이가 깊어지는) 방식으로 정점을.. 2021. 11. 28. Chapter 13. 그래프(Graph) Def) 그래프(Graph) - 개체 간의 연결 관계를 표현할 수 있는 비선형 자료구조 - ex. 도시들 간의 연결, 지하철 노선도, SNS 친구 관계도 등 Note) 그래프의 구성 요소 - 그래프 G = (V, E) - 정점 V(Vertex, Node) 그래프를 구성하는 기본 단위. 노드. 데이터를 저장하거나 상태를 표현 - 엣지 E(Edge, Link) 정점과 정점을 잇는 선. 간선. 방향을 가질 수도 있음. 가중치(Weight)를 가질 수도 있음. Note) 그래프 관련 용어 가중치(Weight) 엣지에 부여된 수치. 비용(Cost) 인접 정점(Adjacent Vertex) 엣지로 연결되어 있는 정점 차수(Degree) 정점에 연결된 다른 정점의 개수 경로(Path) - 특정 정점에서 다른 정점으로.. 2021. 11. 26. Chapter 12. 힙(Heap) Def) 힙(Heap) 완전 이진 트리의 한 분류로서, 힙 속성을 만족하는 자료구조. 이진 힙(Binary Heap) Note) 힙 속성(Heap Property) - 최대 힙 속성(Max Heap Property) 부모 노드의 키 값은 항상 자식 노드의 키 값보다 크거나 같다. - 최소 힙 속성(Min Heap Property) 부모 노드의 키 값은 항상 자식 노드의 키 값보다 작거나 같다. Note) 힙의 특징 - 루트 노드는 항상 최댓값 또는 최솟값을 갖음. - 부모 - 자식 사이의 크기 관계만 있고, 왼쪽 자식 - 오른쪽 자식 사이의 크기 관계는 없음. - 완전 이진 트리이기 때문에 트리의 높이 h = [log2N] - 힙의 응용 분야 힙 정렬, 우선순위 큐, 다익스트라 알고리즘 등 힙 이진 탐색.. 2021. 11. 25. Chapter 11. 이진 탐색 트리(Binary Search Tree) Def) 이진 탐색 트리(BST, Binary Search Tree) 자료의 효율적인 관리(삽입, 탐색, 삭제)를 위한 이진 트리 기반의 자료구조. 자료의 계층적인 구조를 표현하기 위해 트리를 사용하는 것이 아님. Note) 이진 탐색 트리의 특징 - 모든 노드 N에 대해, 왼쪽 서브 트리에 있는 모든 노드의 키값은 노드 N의 키값보다 작음. - 오른쪽 서브 트리에 있는 모든 노드의 키값은 노드 N의 키값보다 큼. - 자료의 탐색, 삽입, 삭제가 모두 O(logN)의 시간 복잡도로 동작. - 중위 순회시, 오름차순으로 정렬된 값을 얻을 수 있음. Note) 이진 탐색 트리 구현 코드(삽입, 탐색) #define _CRT_SECURE_NO_WARNINGS #include #include #include #.. 2021. 11. 21. 이전 1 ··· 7 8 9 10 11 12 13 ··· 17 다음
