CS/DataStructure7

• 

  그래프 그래프 목차 1.그래프란 2.그래프 용어 3.그래프 구현 방법 4.그래프 종류 4.그래프 탐색 그래프란 정점과 간선으로 이루어진 자료구조. 트리는 그래프의 일종이다. 네트워크 모델이다. 객체와 이에 대한 관계를 나타낸다. 예) 지하철, 도로 등. 그래프의 순회방식 : BFS, DFS 그래프 용어 정점 : 노드로서 정점에는 데이터가 저장. 간선 : 링크라고 불리우며 노드간 관계를 나타냄. 인접 정점 : 간선에 의해 연결된 정점. 단순 경로 : 경로 중 반복적으로 탐색하는 정점이 없는 경로. 즉 같은 간선을 지나지 않는 경로. 차수 : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수 : 방향 그래프에서 사용되는 용어로서 한 노드에서 외부로 향하는 간선의 수를 의미. 진출 차수 : 방향 그래프에서.. CS/DataStructure 2021. 7. 30.

• 정렬 보호되어 있는 글 입니다. 2021. 7. 19.

• 

  Hash Hash Table ( key,value ) 로 데이터를 저장하는 자료구조 이다. 배열(버킷)을 사용하여 데이터를 저장하기 떄문에 빠른 검색 속도를 갖는다. ※배열은 물리적 위치와 논리적 위치가 동일하므로 빠르게 접근 가능하기 때문 avg_O (1). 하지만 문제는 인덱스로 저장되는 key값이 불규칙하다는 것이다. 특별한 알고리즘을 이용하여 저장할 데이터와 연관된 고유한 숫자(key)를 만들어 낸 뒤 이를 인덱스로 사용. 이 index를 활용해 값을 저장하거나 접근할 수 있고 실제 값이 저장되는 장소를 "버킷" 또는 "슬롯"이라고 한다. 특정 데이터가 저장되는 인덱스는 그 데이터 만의 고유한 위치이기 때문에, 삽입 연산 시 다른 데이터 사이에 끼어들거나 삭제 시에 다른 데이터로 채울 필요가 없으므로 연산.. CS/DataStructure 2021. 4. 12.

• 

  Heap 사전학습 PriorityQueue 큐를 활용한 자료구조. 데이터 들의 우선순위를 가지고 있다. 먼저 들어간 것이 먼저 나오는 것이 아니다. 우선순위를 지정할 수 있는 데이터의 기준을 정하여 우선순위가 높은 데이터가 먼저 나가는 자료구조. 힙을 사용하여 활용된 자료구조이다. HEAP 완전 이진 트리이다. ※마지막 레벨을 제외한 모든 서브트리의 레벨이 같고, 마지막 레벨은 무조건 왼쪽 부터 채워줘야 한다. 최대 힙과 최소 힙으로 이루어져 있다. 최대 힙 : 루트노드로 올라 갈 수록 저장된 값이 커지는 구조. 최소 힙 : 루트노드로 올라 갈 수록 저장된 값이 작은 구조. 최대 힙,최소 힙 둘다 노드에 우선순위가 가장 높은 것이 자리잡는다. 중복 된 값을 허용한다.(이진 탐색 트리에서는 중복이 허용되지 않는다... CS/DataStructure 2021. 3. 30.

• 

  Tree Tree 비선형 자료구조 이다. Hierachical 관계를 갖는다.(= 부모와 자식 관계를 갖는다) 트리는 DAG의 한 종류다( Directerd Acyclic Graphs 방향성 있는 비순환 그래프) 검색에 효율적인 구조를 갖는다. ※트리 관련 용어 Node : 트리 구성 각 요소. Edge : 트리를 구성 하기 위한 노드 간 연결을 하는 선. Root Node : 트리 구조에서 가장 위에 있는 노드. Terminal Node(=Leaf Node) : 하위에 따른 노드가 연결되지 않은 노드. Internal Node : Terminal 노드를 제외한 모든 노드로 루프 노드를 포함한다. +++ 노드의 크기 : 자신을 포함한 모든 자손의 노드 개수 노드의 깊이 : 루트에서 어떤 노드에 도달하기 위해 거쳐.. CS/DataStructure 2021. 3. 30.