알고리즘 종류
by St1tch재귀호출, 백트래킹 그리디 다이나믹 (Dynamic Programming) 기하 알고리즘 - 내부-외부 판별 - 단순 닫힌 경로 - Convex Hull (Graham Scan 또는 Jarvis March. 전자를 추천) - 선분의 교차 - 벡터 외적 (벡터곱) - Rotating Calipers (꼭 알 필요는 없지만, 알아두면 좋습니다) 문자열 & 오토마타 & 구조 - KMP (Knuth-Morris-Pratt) 스트링 매칭 - Boyer Moore 스트링 매칭 - 유한 오토마타 (Finite Automata) - Trie 구조 (이것은 꼭 알 필요는 없습니다) 수학 & 정수론 부분 - 유클리드 호제법 - 에라스토테네스의 체 - 페르마 소정리 - Totient Function (오일러 함수를 말합니다) - Stern-Brocot Tree (스턴-브로콧 트리) - Miler Rabin 소수 판정, Pollard Rho의 소인수분해 방법 (꼭 알 필요는 없습니다) - 포함배제의 원리 (뭐 이것보다 더 알아두면 더 좋죠.) 근사 알고리즘 - 국소탐색 (LS ; Local Search) - 시뮬레이티드 어닐링 (Simulated Annealing) - 유전자 알고리즘 (GA) (꼭 알 필요는 없습니다) NP 문제 - Minimum Vertex Cover, Edge Cover , Maximum Independent Set - 헤밀턴 회로 - TSP
아래 자료구조 부분이 가장 방대한데요...
< 그래프 & 자료구조 >
검색 (이분검색, 이진검색트리) (=> 여기서 이진검색트리의 최악의 경우 시간복잡도를 줄이기 위해서 AVL Tree가 구현되어졌는데, 레드블랙트리는 AVL의 일종입니다. 정올 할 때 꼭 배울 필요성은 없습니다..)
스택, 큐 Deque (Double Ended Queue) (알아두면 좋습니다) 링크드리스트 (Linked List) 힙 구조 - Binary Heap - Binomial Heap - Fibonacci Heap (이건 꼭 알 필요는 없습니다.) - (Binary) Indexed Tree (이건 알아둬야 합니다. 실제로 Binary Indexed Tree는 Binomial에 가깝지만..) - Interval Tree (이것 또한 Indexed Tree가 이녀석의 역할을 대신할정도로 만능이지만.) 정렬 (합병정렬, 퀵정렬, 힙정렬, 버블정렬, 선택정렬, 삽입정렬, 기수정렬) - K번째 숫자를 최악의 경우 O(n)에 찾는 문제 최소비용신장트리 - Prim - Kruskal - Matroid Theory (이것도 꼭 알 필요는 없습니다) 최단경로 - Dijkstra (다익스트라) - Floyd (플로이드) - Bellman Ford (벨만포드) 그래프 탐색 - BFS(너비우선탐색), DFS(깊이우선탐색) 위상정렬 (Topological Sort) 최대유량 알고리즘 (Maximum Flow Algorithm) - Ford-Fulkerson의 방법 - Minimum Cut (최소 절단 문제) - 푸시-재명명 방법 (이것도 꼭 알 필요는 없습니다) - 최대 이분매칭 (Bipartite Maximum Matching) - Hungarian Method (가중치가 들어간 매칭) - Gale-Shapely Matching (이건 최대유량과는 관계없이, 그리디 부분이지만, 매칭 알고리즘의 일종이므로 여기에 넣었습니다) - Hopcroft-Karp의 방법 (이건 이분매칭의 시간복잡도를 가장 줄이는 방법인데, 꼭 알 필요는 없습니다) - Mincost-Maxflow Algorithm - Stoer-Wagner Algorithm (간선연결도 문제에 쓰이는 최적 알고리즘인데, 꼭 알 필요는 없습니다) 트리 관련 - 최소 비용 채색 문제 (이건 다이나믹에 속하지만 , 트리 구조가 그래프에 속하니 여기에..) - 절점 찾기 - Bridge 찾기 (등등등등... 너무 많아서 생략) 강한 연결 성분 (Strongly Connected Components , 줄여서 SCC) - Kosaraju , Tarjan의 방법 2-CNF (2-SAT의 일종입니다) 서로소 집합 (Disjoint Set) - 순위 정하기 (휴리스틱의 일종) - 경로 압축 (휴리스틱의 일종 , Path Compression) |
블로그의 정보
튜기's blogg(st1tch)
St1tch