튜기's bloggggg(st1tch)

알고리즘 종류

Algorithm2015.09.09 20:00


재귀호출, 백트래킹

그리디

다이나믹 (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)

[출처] 알고리즘 종류|작성자 튜기


저작자 표시
신고

Comment +0