V : vertex (정점) E : edge (간선) Edge Type directed edge : 유향 간선 undirected edge : 무향 간선 directed graph : 유향 간선으로 이루어진 그래프 undirected graph : 무향 간선으로 이루어진 그래 Termiology Incident : 간선과 정점이 붙어있는 경우 사 (정점과 간선의 관계) Adjacent : 인접한 정점들 (정점과 정점의 관계) Degree : 연결된 간선의 수 Parrel Edge : a - > b / b -> a와 같은 간선 Self - loop Edge : 시작과 끝이 같은 정점을 가리키는 간선 Property 1. deg(v)의 합은 2m이다. -> 중복으로 두 번 세기 때문. ex) a - b가 있..
Study/Data_Structure
key를 가지고 탐색을 진행, 동일한 key를 가지는 원소가 있을 수 있음. => 중복 가능 List - Based Dict log file / audit trail : unsorted sequence insert : O(1) find && erase : O(n) log file -> insert는 빠르지만, 나머지 탐색, 삭제는 느림 Search Table search table == lookup table, table = 배열 / sorted array 정렬된 배열 -> 이진 탐색 떠올리기 이진 탐색 -> sorted array떠올리기 find : O(log(n)), 이진 탐색을 이용 insert : O(n), 원소 재배치 remove : O(n), 원소 재배치 search table은 size가 작..
Binary Search Tree 아래 그림과 같이 한 쪽으로 편향될 수 있다. 그렇기에 insert, delete, find 함수의 시간 복잡도는 최악의 경우 O(n), 가장 효율적으로는 O(log(n))이 된다. 즉, 높이 h에 따른다는 것을 알 수 있다. Insert root부터 해당 value 값보다 작으면 left, 크면 right로 내려가 NULL이 아닐때 까지 탐색 Delete 1. child 중 NULL이 있는 경우 -> external이 아닌 노드를 그대로 이어 붙이면 해결된다. 아래 그림은 child에 NULL이 있는 경우인 빨간색 노드를 삭제하는 경우이다. 2. 하지만 만약 child 모두 internal 이라면, 얘기가 달라진다. 아래 그림은 internal node인 빨간색을 삭제..
key, value 두 가지 entry로 구성 key값이 작을수록 우선순위가 높다 -> min_priority_queue key값이 클 수록 우선순위가 높다 -> max_priority_queue PQ sorting unsorted list - selection sort sorted list - insertion sort heap sort Unsorted List - Selection Sort 원소를 주어지는 순서대로 삽입 -> O(1) 삽입된 원소를 하나하나 비교해가며 찾아서 반환 -> O(n) 그러므로 n개의 원소 삽입 -> O(n) 최솟값 / 최댓값을 찾아 반환 -> O(n^2) => worst-case 가 곧 average-case Sorted List - Insertion Sort -> 사이즈가..
이진트리란 자식 노드의 수가 0 ~ 2개인 트리를 말한다. 이를 재귀적으로 표현할 수 있는데, 단일 노드이거나 해당 노드의 자식 노드가 모두 이진 트리라면 해당 노드를 이진트리라고 부른다. 완전이진트리란 이진트리를 채워나갈 때 마지막 노드가 왼쪽부터 차례대로 채워진 트리의 형태이다. 위 그림에서 볼 수 있듯이, internal 노드의 수는 3, external 노드의 수는 3, 높이 h는 2이다. external 노드가 왼쪽부터 차례대로 채워졌으므로 위의 트리는 완전이진트리가 된다. 만약 왼쪽부터 채우다가 오른쪽 끝까지, 즉 external 노드의 수가 2^h개라면 이를 포화이진트리라고 부른다. internal 노드의 수는 3, external 노드의 수는 4, 높이 h는 2이다. external 노드가..
