CS/자료구조3 [자료구조] 3. Graph : MST, 최단거리, Union-Find 0. Graph 노드들과 그 노드들을 연결한 간선에 대한 정보를 저장하는 자료구조 1. Terminology 1) vertex(정점), edge(간선) 2) degree : 한 정점에 간선으로 연결된 정점 개수 2-1) in-degree : 방향 그래프에서 한 정점으로 들어오는 간선 개수 2-2) out-degree : 방향 그래프에서 한 정점에서 나가는 간선 개수 3) Simple Path : 경로 내 중복되는 정점이 없는 경로 1) Ordered/unOrdered : 간선의 방향 유무 2) Weighted : 간선에 가중치 유무 3) Connected/Disconnected : 그래프 내 한 정점에 대해서 나머지 정점으로의 경로 존재 유무 4) Cycle/Acycle : 시작점과 도착점이 동일한 Si.. 2020. 12. 3. [자료구조] 2. Tree : Binary Tree, Heap, BST 1. Terminology 1) Degree : # of child the node has 2) Size : total # of node in tree 3) Depth : # of edge that need to pass from root node(>=0) 4) Height : maximum value of depth 5) Level : set of node at same level 2. Binary Tree Tree의 각 Node가 최대 2개의 Children Node를 가지는 Tree 자료구조 * number of node in tree = n, height of tree = h 일때 → 2h + 1 ≤ n ≤ 2^(h+1)-1 1) Compelete Binary Tree : 완전이진트리 마지막 le.. 2020. 12. 1. [자료구조] 1. Array, Pointer, Stack, Queue, LinkedList 1. Array 연속적인 memory에 저장된 같은 type의 data집합 2. Pointer // 일반 포인터 type* var_name; cout data = (element); // == *(*ptr).data = (element); 3. Stack 한쪽 끝에서만 자료를 추가하고 삭제할 수 있는 FILO형태의 자료구조 4. Queue 한쪽 끝에서만 자료를 추가하고 삭제할 수 있는 FIFO형태의 자료구조 5. Linkedlist 기준에 따라 순서대로 배치할 때 새로운 element 삽입/삭제를 단순 Array보다 빠르게 할 수 있는 자료구조 typedef struct listNode *listPtr; typedef struct listNode{ int data; listPtr link; } listP.. 2020. 12. 1. 이전 1 다음
