學習歷程 – Yui Huang 演算法學習筆記

C++ 語法

難度	主題	筆記	月份
1	cin / cout / getline	Link	Sep. 2019
1	<iomanip>	Link	Feb. 2020
1	if – else		Sep. 2019
1	for / while / continue / break		Sep. 2019
1	array		Sep. 2019
1	string		Sep. 2019
2	funciton & recursion		Sep. 2019
2	pointer & reference		Sep. 2019
2	struct		Sep. 2019

C++ 內建線性資料結構

難度	主題	筆記	範例	月份
1	Array		範例	Sep. 2019
2	C++ STL vector	Link		Sep. 2019
2	C++ STL bitset			Nov. 2019
2	C++ STL list
2	C++ STL stack	Link	範例	Sep. 2019
2	C++ STL queue	Link	範例	Sep. 2019
2	C++ STL deque			Jan. 2020

C++ STL algorithm

難度	主題	筆記	月份
2	sort	Link	Sep. 2019
2	reverse	Link	Sep. 2019
2	lower_bound & upper_bound	Link	Sep. 2019
2	is_permutation & next_permutation & prev_permutation	Link	Sep. 2019
2	find( ) vs. set.find( )	Link	Sep. 2019
2	memset() vs. for-loop	Link	Feb. 2020

C++ 內建非線性資料結構

難度	主題	筆記	範例	月份
2	C++ STL set / multiset	Link	範例	Sep. 2019
2	C++ STL map / unordered_map	Link	範例	Sep. 2019
2	C++ STL priority queue	Link	範例	Sep. 2019

基礎演算法

難度	主題	筆記	範例	月份
2	【枚舉 Complete Search】 => Iterative Complete Search	Link	範例	Aug. 2019
3	=> Recursive Complete Search Backtracking (八皇后 8-Queens)	Link	範例	Oct. 2019
2	【排序 Sorting】 => 泡沫排序法 Bubble sort => 插入排序法 Insertion sort => 選擇排序法 Selection sort	Link	範例	Aug. 2019
2	【搜尋 Search】 => Two Pointers => 二分搜 Binary search	Link	範例	Aug. 2019
3	=> 三分搜 Ternary search	Link	範例	Dec. 2019
3	【分治 Divide & Conquer】 => 合併排序法 Merge sort => 快速排序法 Quick sort => 河內塔 Tower of Hanoi	Link	範例	Aug. 2019
2	【貪心 Greedy】	Link	範例	Aug. 2019
3	【動態規劃 Dynamic Programming (DP)】 => Top-down DP => Bottom-up DP	Link	範例	Aug. 2019
3	=> Max 1D Range Sum		範例	Aug. 2019
4	=> Max 2D Range Sum		範例	Feb. 2019
3	=> 最長遞增子序列 LIS	Link	範例	Aug. 2019
3	=> 0-1背包問題 0-1 Knapsack	Link	範例	Aug. 2019
3	=> 零錢問題 Change coins	Link	範例	Aug. 2019
4	=> 區間DP		範例	Jan. 2020
6	=> 借還DP		範例	Jun. 2020
4	=> 環狀陣列之最大連續和		範例	Mar. 2020
	=> Traveling Salesman Problem (TSP)

進階資料結構

難度	主題	筆記	範例	月份
3	【圖 Graph】 => 鄰接矩陣 Adjacency matrix => 鄰接表 Adjacency list	Link	範例	Oct. 2019
4	【並查集 Union-Find Disjoint Sets, DSU】	Link	範例	Dec. 2019
5	【線段樹 Segment Tree】 => 區間問題 => 線段樹的結構 (二元樹) => build 建立線段樹 => query 線段樹的區間查詢 => update 單點修改線段樹	Link	範例	Dec. 2019
5	=> 懶標記 lazy tag => 區間修改線段樹		範例	Dec. 2019
5	=> 樹壓平 (樹的DFS序)		範例	Jan. 2020
5	=> 掃描線 (線段樹實作)		範例	Mar. 2020
5	【樹狀數組 Binary Indexed (Fenwick) Tree】	Link	範例	Jan. 2020
6	=> 二維樹狀數組 BIT		範例	Jan. 2020
5	【單調棧 Monotonic Stack】	Link	範例	Jan. 2020
5	【單調隊列 Monotonic Queue】	Link	範例	Jan. 2020
3	【雙向鏈結串列 Doubly Linked List】	Link		Mar. 2020
5	【Hash】	Link	範例	Jan. 2020

圖論 Graph

難度	主題	筆記	範例	月份
3	【圖的遍歷 Graph Traversal】 => 深度優先搜索 DFS	Link		Oct. 2019
3	=> 廣度優先搜索 BFS	Link		Oct. 2019
4	=> 連通塊 Finding Connected Components (Undirected Graph)
4	=> Flood Fill – Labeling/Coloring the Connected Components		範例	Jan. 2020
4	【拓撲排序 Topological sort】 (Directed Acyclic Graph)	Link	範例	Dec. 2019
6	【二分圖 Bipartite Graph】 => 二分圖染色 (BFS)		範例	Feb. 2020
6	=> 二分圖判定		範例	Feb. 2020
6	=> 二分圖的最大匹配	Link		Feb. 2020
	Graph Edges Property Check via DFS Spanning Tree
5	【圖的連通性】 => 關節點 / 割點 Finding Articulation Points and Bridges (Undirected Graph)		範例	Mar. 2020
5	=> 雙連通分量 (Biconnected Component)
5	=> 橋連通分量 (Bridge-connected Component)
5	=> 強連通分量 (Strongly Connected Component) ===> Tarjan’s Algorithm Finding Strongly Connected Components (Directed Graph)		範例	Mar. 2020
4	【最小生成樹 Minimum Spanning Tree (MST)】 => Kruskal algorithm	Link		Dec. 2019
4	=> Prim’s Algorithm
4	=> Maximum Spanning Tree
5	=> Minimax (and Maximin)		範例	Nov. 2019
5	=> 水母圖找環		範例	Feb. 2020
3	【單點源最短路 Single-Source Shortest Paths (SSSP)】 => SSSP on Unweighted Graph (BFS)		範例
4	=> SSSP on Weighted Graph (Dijkstra’s algorithm)	Link	範例	Nov. 2019
4	=> SSSP on Graph with Negative Weight Cycle (Bellman Ford’s algorithm)			Nov. 2019
4	【全點對最短路 All-Pairs Shortest Paths】 (Floyd Warshall’s algorithm)	Link	範例	Nov. 2019
6	【網路流 Network Flow】 => Ford Fulkerson’s Method
6	=> Edmonds Karp’s Algorithm
6	=> Minimum Cut
	【Special Graphs】
3	【樹狀結構 Tree】 => Tree Traversal pre-order, in-order, and post-order		範例	Oct. 2019
3	=> 二元樹 Binary tree => 二元搜尋樹 Binary Search Tree (BST)		範例	Nov. 2019
3	=> 樹上的DFS		範例	Nov. 2019
3	=> 樹直徑 Diameter
3	=> 樹圓心		範例	Nov. 2019
3	=> 樹重心 Centroid	Link		Nov. 2019
	=> Eulerian Graph
4	=> Euler Paths		範例	Jun. 2020
4	=> Euler Circuits		範例	Jul. 2020
	Max Cardinality Bipartite Matching (MCBM) and Its Max Flow Solution

數學 Mathematics

難度	主題	筆記	範例	月份
2	【簡單數學問題】		範例	Aug. 2019
2	=> 數學模擬 (暴力)		範例	Sep. 2019
3	=> 找出規律		範例	Feb. 2020
3	=> 數列		範例	Feb. 2020
4	=> 指數、對數
4	=> 多項式
4	=> 進位制		範例	Sep. 2019
2	【大數 BigInteger】		範例	Sep. 2019
	【組合數學 Combinatorics】
2	=> Fibonacci Numbers		範例	Aug. 2019
	=> Binomial Coefficients
5	=> 卡特蘭數 (Catalan Numbers)	Link		Feb. 2020
	【數論 Number Theory】
2	=> 質數 Prime Testing		範例	Aug. 2019
3	=> 質數篩法 Sieve of Eratosthenes	Link	範例	Nov. 2019
3	=> 最大質因數建表		範例	Nov. 2019
2	=> 最大公因數 GCD => 最小公倍數 LCM	Link	範例	Aug. 2019
2	=> 階乘 Factorial (!)			Aug. 2019
2	=> 質因數 Prime Factors		範例	Aug. 2019
4	=> 歐拉函數 Euler’s Phi (Totient) function	Link	範例	Nov. 2019
5	=> 擴展歐幾里德 (Extended Euclidean algorithm)		範例	Feb. 2020
2	=> 模運算 Modulo Arithmetic		範例	Aug. 2019
5	=> 模逆元	Link		Feb. 2020
4	=> 快速冪 (Exponentiating by squaring)	Link		Nov. 2019
6	【Probability Theory】
4	【Cycle-Finding】		範例	Dec. 2019
	【Game Theory】
5	=> Nim Game	Link		Jan. 2020

字串處理 String Processing

難度	主題	筆記	範例	月份
	【基本字串處理】
2	=> Cipher/Encode/Encrypt/Decode/Decrypt		範例	Sep. 2019
2	=> Frequency Counting		範例	Sep. 2019
2	=> Input Parsing			Sep. 2019
2	=> Output Formatting			Sep. 2019
2	=> String Comparison		範例	Sep. 2019
	【字串匹配String Matching】
5	=> Knuth-Morris-Pratt’s (KMP) Algorithm	Link		Feb. 2020
	【String Processing with DP】
3	=> 最長共同子序列 LCS	Link		Aug. 2019
4	=> String Alignment (Edit Distance)		範例	Feb. 2020
	=> Longest Palindrome
7	===> Manacher’s Algorithm		範例	Apr. 2020
	【Suffix Trie/Tree/Array】
5	=> 字典樹 Trie	Link		Feb. 2020
	=> Suffix Trie
	=> Suffix Tree
6	=> Suffix Array
	字串處理：Z-Algorithm		範例1、範例2	Sep. 2020

計算幾何 Computational Geometry

難度	主題	月份
	Basic Geometry Objects
6	=> Point
6	=> Line
6	=> Circle
6	=> Triangle
6	=> Quadrilaterals
	Algorithm on Polygon	Apr. 2021
6	=> Polygon Representation
6	=> Perimeter of a Polygon
6	=> Area of a Polygon
6	=> Checking if a Polygon is Convex
6	=> Checking if a Point is Inside a Polygon
6	=> Cutting Polygon with a Straight Line
6	=> Finding the Convex Hull of a Set of Points

進階主題

難度	主題	筆記	範例	月份
	Advanced Search Techniques
	=> Backtracking with Bitmask
	=> Backtracking with Heavy Pruning
	=> State-Space Search with BFS or Dijkstra’s
	=> Meet in the Middle (Bidirectional Search)
7	=> Informed Search: A* and IDA*
	Advanced DP Techniques
4	=> 數位DP (DP with Bitmask)	Link	範例	Feb. 2020
5	=> 插頭DP / 輪廓DP		範例1、範例2	Jan. 2021

其它主題

難度	主題	筆記	範例	月份
5	【2-SAT Problem】		範例1 範例2	Jul. 2020
	【Art Gallery Problem】
	【Bitonic Traveling Salesman Problem】
	【Bracket Matching】
	【Chinese Postman Problem】
	【Closest Pair Problem】
6	【Dinic’s Algorithm】
	【Formulas or Theorems】
6	【Gaussian Elimination Algorithm】
	【Graph Matching】
	【Great-Circle Distance】
	【Hopcroft Karp’s Algorithm】
	【Independent and Edge-Disjoint Paths】
	【Inversion Index】
	【Josephus Problem】
	【Knight Moves】
	【Kosaraju’s Algorithm】
4	【最近共同祖先 Lowest Common Ancestor (LCA) & 倍增法】	Link		Dec. 2019
	【Magic Square Construction (Odd Size)】
	【矩陣 Matrix】
5	=> 矩陣乘法 Matrix Multiplication	Link		Feb. 2020
	=> Matrix Chain Multiplication
5	=> 矩陣快速冪 Matrix Power	Link		Mar. 2020
	【Max Weighted Independent Set】
6	【Min Cost (Max) Flow】
	【Min Path Coveron DAG】
	【Pancake Sorting】
	【Pollard’s rho Integer Factoring Algorithm】
	【Postfix Calculator and Conversion】
	【Roman Numerals】
	【Selection Problem】
	【Shortest Path Faster Algorithm】
	【Sliding Window】
	【線性時間排序】
2	=> 計數排序 Counting Sort		範例	Feb. 2020
	=> 基數排序 Radix Sort
4	【稀疏表 Sparse Table 】		範例	Dec. 2019
2	【Tower of Hanoi】		範例	Oct. 2019
6	【cdq分治】		範例	May. 2020

Post Views (since April 2021) : 12,997