Algorithm/Algorithm (이론)

재귀 하나의 함수에서 자기가 자신을 계속 호출하는 알고리즘으로 반드시 종료 조건 (Base condition) 을 갖는다.

Breadth First Search

When to use Find targetValue in sorted array Algorithm Recursive approach 1. StartIndex = 0 (lower bound), endIndex = arr.length (upper bound), midIndex = starIndex + endIndex / 2, 2. Recursion until (startIndex > endIndex (Not found)) . arr[midIndex] == targetValue ? => return midIndex .arr[midIndex] > targetValue ? => endIndex = mid – 1 (targetValue on left side) .arr[midIndex] < targetValue ?..

📝 개요 (1) 자식 노드 갯수가 2개 이하로 (2) 왼쪽 자식은 모두 나보다 값이 작고 (3) 오른쪽 자식은 모두 나보다 값이 큰 그리고 모든 자식 노드 또한 위 3가지 성질을 갖는 자료구조. When to use? (1) Local Search getNextNode (next Largest key except myself) Range Search ex) 1~100 中 5~15 (2) Implements Data structure Set, Binary Heap, Priority Queue 👨‍💻 Impelment (C++) 왼쪽, 오른쪽 자식뿐만 아니라 부모노드와 연결도 킵 BST.h BST.cpp main.cpp Key Point (Delete Node) 가장 까다로운 부분이기 때문에 그림과 함께 정..

When to use? 임의의 한 정점에서 모든 정점으로의 최단 경로 및 비용을 구할 때. 특정 출발 지점에서 도착지점까지의 최단 경로 및 비용을 구할 때 # shortest path # greedy Algorithm 1. Create shortestPath Set, distance array table || (visited array) 2. initialize all vertices with make start node weight '0', reamin node weight 'INF' 3. set || priorityQueue != empty (a) Pick minimum vertex (b) check all adjacent edge weight compare distance [adjacentVerte..

구현 방식 2가지 1. Priority Queue. // O(n log n) for(int i = 1; i O(n * log n) ∴ O (n * log n) BuildHeap Analysis When to use? k Largest(Smallest) elements in array Implementation (C++) // make Max Heap void PriorityQueue::shiftDown(int index) { int maxIndex = index; do { index = maxIndex; const int leftChildIndex = getLeftChildIndex(index); const int rightChildIndex = getRightChildIndex(index); if (l..