[Daily Post] 230626

[Daily Post]는 매일매일 탐구한 내용을 간략하게 기록하는 포스트입니다.
따라서 정리되지 않은 내용과 추측을 포함하고 있을 수 있습니다.
더 체계적인 형식을 갖춘 글은 해당 카테고리의 포스트를 확인해주세요 :)

My Study

Graph: 관계를 위한 자료구조
- Node와 Edge로 구성
- 들어오는 간선은 indegree, 나가는 간선은 outdegree
Tree: 특수한 구조를 가진 그래프
- 마찬가지로 Node와 Edge로 구성
- 상위, 하위 관계를 나눌 수 있음
- Parent & Child
- Ancestor & Descendant
- Root & Leaf
Binary Tree
- 부모노드가 X면 왼쪽 자식은 2X, 오른쪽 자식은 2X+1
- 공통부모를 찾을 때 1/2씩 나누면서 찾게 되기 때문에 빠르다
- 복잡해보여도 어차피 Root Node가 1이기 때문에 공통 부모는 꼭 찾게 된다
- Heap, BST가 여기서 비롯된다
Heap: 우선순위가 가장 높은 값을 Root 노드에 위치시킨다
- 다른 이름은 Priority Queue이다.
- Pop하면 root node가 나오고, leaf node 중 하나를 Top을 가져옴
- 만드는 속도, 정렬하는 속도 모두 O(NlogN)안에 해결 가능
BST: Binary Search Tree
- 추가하는 Node가 자신보다 작으면 왼쪽에, 크면 오른쪽에 위치시키는 tree
DFS: 깊이 우선 탐색 (Depth First Search)
- 스택을 사용하여 기능 구현
BFS: 너비 우선 탐색 (Breadth First Search)
- 큐를 사용하여 기능 구현

Array: 연속적, 순차적, 미리 할당된 크기만큼 배정
Dynamic Array: resize (더블링 등)
- 데이터를 append 할 때는 O(1)만큼 걸린다
- resize하면서 데이터 옮기는 것은 O(N)이지만, 결론적으로는 amortized(1)이다. resize 횟수 자체가 element 갯수에 비해 적기 때문.
Linked List