ghdcksgml1/cpp_Algorithm_implementation

📓 C++ 알고리즘 구현체 📓

알고리즘 정리 🙂

혹시나 틀린부분이 있다면 언제든 지적해주세요!! (난이도 순서 X, 내가 공부한 순서 O)

순서	알고리즘		시간 복잡도
01	선택 정렬	Select Sort	O(N2)
02	버블 정렬	Bubble Sort	O(N2)
03	삽입 정렬	Insertion sort	O(N2)
04	퀵 정렬	Quick Sort	평균: O(N*logN), 최대: O(N2)
05	병합 정렬	Merge Sort	O(N*logN)
06	STL::Sort 사용	sortMethod	O(N*logN)
07	힙 정렬	Heap Sort	O(N*logN)
08	계수 정렬	Counting Sort	O(N)
09	스택 구현	stack
10	큐 구현	Queue
11	BFS(너비 우선 탐색)	Breath First Search	O(V2)
12	DFS(깊이 우선 탐색)	Depth First Search	O(V2)
13	유니온 파인드	Union Find	O(logE)
14	최소 스패닝 트리	Kruskal Algorithm	O(E*logE)
15	바이너리 트리	Binary Tree
16	다이나믹 프로그래밍	Dynamic Programming	O(N)
17	에라토스테네스의 체	Prime Number	O(N*logN*logN)
18	다익스트라 알고리즘	Dijkstra Algorithm	O(E*V*logV)
19	괄호문제	Parentheses
20	분할 정복	Quad Tree	O(N*logN)
21	백트래킹	BackTracking	O(2N)
22	다익스트라 알고리즘2	Dijkstra Algorithm2	O(E*logV)
23	유클리드 호제법	Ecuild
24	이분 매칭	Bipartite Matching	O(VE)
25	KMP 알고리즘	KMP Algorithm	O(N)
26	위상 정렬	Topology Sort	O(V+E)
27	세그먼트 트리	Segment Tree	O(N*logN)
28	플로이드 와샬	Floyd Warshall	O(V3)
29	느리게 갱신되는 세그먼트 트리	Segment Tree Lazy Propagation	O(N*logN)
30	외판원 순회	TSP	O(2N)
31	배낭 알고리즘	KnapSack	O(N*V)
32	최장 공통 문자열	LCS (Longest Common Substring)
33	최장 공통 부분 문자열	LCS (Longest Common Subsequence)
34	가장 긴 증가하는 부분 수열	LIS (Longest Increasing Subsequence)	O(N*logN)
35	최장 공통 조상	LCA (Longest Common Ancestor)	O(M*logN)
36	해시	Hash	O(1)
37	트라이	Trie	생성 시간복잡도: O(M*L) 탐색 시간복잡도: O(L) (L: 제일 긴 문자열의 길이, M: 총 문자열 수)
38	머지소트 트리	MergeSort Tree	O(N*logN)
39	모스 알고리즘 + 오프라인 쿼리	mo's Algorithm + Offline Query	O((N+Q)√N * T(N)) (T(N): 모스 알고리즘에서 숫자를 늘리거나 줄일때의 연산량)
40	오일러회로 알고리즘	Hierholzer's Algorithm	O(E) (V: 정점의 수, E: 간선의 수)
41	오일러경로 테크닉	Euler tour technic	O(N) : 각 노드의 인덱스를 붙여 DFS탐색을 통해 어디서 들어가고 빠져나오는지를 기록