GameStudy489 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. Chapter 10. 트리(Tree) Def) 트리(Tree) 계층적인 구조를 나타내는 자료구조. 보통 Root가 위, Branch와 Leaf이 아래로 자라는 형태로 표현. Def) 노드(Node, Vertex) 트리의 데이터를 저장하는 원소 단위. 정점. Def) 엣지(Edge, Link) 노드와 노드를 연결하는 선. 간선 트리의 엣지는 부모-자식 계층 관계만을 나타냄. 즉, 엣지의 위에 있는 것이 부모, 아래가 자식. 노드의 개수가 N이면 항상 N - 1개의 엣지가 존재 즉, 두 개의 노드를 연결하는 엣지는 항상 유일함. Note) 트리 관련 용어 트리를 제대로 이해하기 위해선, 관련 용어 숙지가 필수. 루트(Root) 트리의 최상단 노드 부모 - 자식 관계(Parent - Child) 엣지로 연결되어 있는 두 노드의 상대적 관계 루트의.. 2021. 11. 19. 이전 1 ··· 93 94 95 96 97 98 99 ··· 123 다음
