Algorithms & ICPC 썸네일형 리스트형 Greedy Greedy - Like DP or Divide&Conquer, Greedy is a programming paradigm rather than a specific algorithm. Minimum Spanning Tree - Let's assume we have a connected, undirected graph G=(V,E) with weight function w : E -> R. - The MST of the graph is a tree that connects all vertices with minimum weight. - An algorithm that finds the MST of a graph could be used when building Spanning Tree Protocol(ST.. 더보기 Dynamic Programming Dynamic Programming - Like Divide-and-Conquer, Dynamic Programming is a design technique of algorithms. Longest Common Subsequence(LCS) - LCS is a famous example of a problem that could be solved using DP. - Given two sequence x[1, ... , m] and y[1, ... , n], the goal is to find the longest subsequence common to both. - A naive approach is to check every subsequence of x to se if it is also a su.. 더보기 Order Statistics - In order to find the ith smallest of n elements, one naive approach is to sort the n elements using merge sort or heap sort and pick the ith element, which would take O(NlgN) time in the worst case. Randomized Divide-and-Conquer Algorithm - Instead we could use a randomized divide-and-conquer algorithm. - In this algorithm, we do not sort the sub arrays which are consisted of elements smaller .. 더보기 Trees Binary Search Tree - To build a BST with a given array input, the best time complexity would take O(NlogN) for N elements, and worst case would be O(N^2). - The worst case is when a the array is in ascending order or descending order. - This is because for each element, since the BST is skewed, it would take N comparisons to find the position for the corresponding element. - The expected time to.. 더보기 Linear Sorting Comparison Sort - All the sorting algorithms we have seen so far are comparison sorts, which only use comparisons to determine the relative order of elements. - Such examples are Insertion Sort, Merge Sort, Quick Sort, and Heap Sort. - The best worst-case running time that we've seen for comparison sorting is O(NlogN). - A decision tree can model the execution of any comparison sort. - The tree .. 더보기 이전 1 다음
