Complete Binaray Tree every level, all nodes are filled ordering left to right except possibly last node When to use? -> Implements Prirority Queue! * Full Binrary Tree : every node has two children ADT of Prirority Queue implements using MAX Heap array -> parent index : i / 2 left child index : i * 2 right child index : i * 2 + 1 maxSize: Capacity size: The number of current elements which heap..
Algorithm/Algorithm (이론)
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)를 구하는 알고리즘 what's MST? 모든 노드(Vertex)를 최소 비용으로 최소 간선(Edge)을 사용해 연결한 트리 (no cycle) * MST의 Edge수는 Number Of Vertex - 1 이다. Where to use MST? Network Design Approximation algorithms (ex. traveling salesperson problem) When to use Kruskal Get MST of undirected graph by Greedy algorithm Algorithm (1) Sort all edges in ordering by weight (ascending) => 최소 비용 간선 오름차순 (2) Pi..
개요 모든 경우의 수를 탐색하는 Brute Force 알고리즘으로 조건이 존재할 때 사용한다. State-Space Tree 라고도 한다. 기본적으로 DFS 를 사용하며 조건에 부합하지 않는 branch에 대해 Pruning (가지치기)를 하여 불필요한 경우의 수를 따지지 않는다. Branch and Bound BFS 베이스로 (depth == level) 기준으로 자리를 구분한다. 관련 문제 www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/ Write a program to print all permutations of a given string - GeeksforGeeks A Computer Scie..
해싱 정의 키(key) 값에 직접 산술 연산을 적용하여 해시 테이블 주소를 통해 값(Value)에 접근하는 것 해시 테이블 (Hash Table) key 값의 연산에 의해 직접 접근이 가능한 자료구조 Dictionary == Map == Table 사전(Dictionary) 자료구조는 Key - Value를 갖는 자료구조로 오로지 키에 의해 값에 접근한다. (키가 정렬되었는지 여부는 구현시 결정 가능하다.) // 별로 중요하지 않다. ex) 사람 이름(key) - 전화번호(Value) 필수 연산은 다음과 같다. Insert Delete Search 이런 사전 자료구조 (Dictionary)를 효율적으로 구현하기 위해 해시 알고리즘을 적용한다. 해시 함수 키를 입력하여 해시 주소를 얻어낸다. 해시 주소는 ..
1. 용도 Graph에서 All pairs Shortest Path 구하기 == 그래프 내의 모든 노드쌍에 대한 최단거리 구하기. Input Directed-weighted Graph Output All pairs Shortest Path (ex. Adjacency Matrix) 2. IDEA 점화식으로 부터 이 알고리즘이 'Dynamic Programming' 류의 알고리즘임을 알 수 있다. 3. Pseudo Code 4. Time Complexity Pseudo Code에서 알 수 있듯이 최초의 Adjacency Matrix를 형성하는 2중 for Loop은 O(n^2) Shortest Path를 갱신하는 3중 for Loop 은 O(n^3) ∴ O(n^3) 참고 자료 https://ko.wikipe..
