algorithm

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 ?..

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..

When to use get MST of undirected & weighted Graph Idea maintain two sets of vertices (1: MST, 2: not visited) find cut vertex minimum weight in each loop until all vertices be included in MST 📝 cut vertex: connect vertex which connects two disjoint subsets Algorithm (1) Create key-value table (vertex - weight) , empty MST Set (2) initialize first value of key as '0' to visit first, remain key a..

🔒 문제 💭 생각의 흐름 MST (Minimum Spanning Tree) + Undirected Graph => 2가지 방법! Kruskcal Prim✔️ mstSet: 방문된 MST 원소의 집합 not visited Set: 아직 방문하지 않은 노드 번호 - 비용 집합 find minimum cut vertex : mstSet과 not visited Set을 최소 비용으로 연결하는 노드 찾기 mstSet -> 어차피 weight의 총합을 구하는 것이므로 방문 순서를 저장할 필요가 없겠다 -> unorderd_set not visited Set -> 배열로 생성시 따로 visited Boolean 배열이 필요하므로 map 자료구조 사용 ⭐ find minimum cut vertex -> not vist..