알고리즘 관련 학습 사항 정리

두서없이 공부하다 보니 이대로 안 될 거 같아서 적어놓으면서 정리하기로 함.

갱신의 가능성은 ... 글쎄...

• 기본기 (자료구조)
• 링크드리스트, 더블링크드리스트 (std::list)
  다양한 링크드리스트 구현 방법에 대해 공부해야 둘 것.
• dictionary (std::map)
• Queue (일반적으로 std::priority_queue 사용)
• Tree 
• Disjoint Set, Union-Find 개념
  
• Heap
• Indexed Tree
  (Binary / Red-black과 같은..? 일반적으로 std::map 같은 방식으로 내장 되어 있으니 구현할 필요는 없을 것)
• Prim / Kruskal 최소비용신장트리
• 세그먼트 트리 (Heap의 확장판... 필요성과 구현 예 - 문1/해설/해설2 )
• Sorting
• quicksort, Merge sort (분할정복의 기본 이해)
• Radix sort (O(n) 소팅의 이해 및 응용)
• Graph
• DFS, BFS (recursively or using for; )
  예시: Minimum Vertex Cover, Edge cover, ...
• 응용
• Dynamic Programming; DP
  계산했던 값을 재사용하여 계산 시간을 줄인다는 의의가 있음을 깨달아야 함.
  (대체로 부분정복이 가능한 문제들에 대해 적용)
• Graph
• TSP
  저장되는 값: 현재 위치/방문한 지점에 따른 최적의 moving distance
  최적의 경로를 역추적할 수 있음, 방법도 숙지할 것.
• Dijkstra, Bellman-Ford
• Floyd-Warshall
  다익스트라/플로이드 둘다 경로 역추적 가능.
  다익스트라는 음수간선 사용 불가능.
• 문자열 매칭
• LCS 알고리즘
• Edit Distance
• n개중 p개의 최소 성공 확률? 문제
• 백트래킹: 색칠 문제, N Queen 문제
  일종의 그리디? 유형으로 시간복잡도가 크기 때문에 이 점을 유념해서 사용해야 됨...
  필요시 DP나 여타 다른 알고리즘이랑 보조하여 사용
• 기하 / 그래프 문제
• Convex hull (Graham's scan)
  주로 사용되는 값: 각도. 초기값: 맨 밑 점을 기준으로, 2개의 점
• 선형계획법 (여기 들어가야 하나?)
• 선분 교차 여부 확인
• 단절점(선) 문제 (Bridge) 2 (DFS 이용)
• 최대유량 알고리즘
• Ford-Fulkerson 
  (Minimum Cut 은 사실상 동치인 문제가 된다)
  역추적 또한 가능.
  유량을 1로 지정하면 Bipartite matching 문제를 해결하는 용도로 사용 가능.
• 강한/이중 연결 성분 (SCC / BCC)
• Kosaraju / Tarjan 
• Tarjan (Biconnected; BCC ver., wikipedia explanation)
• 2-SAT 문제 (유명한 난제; 그래프문제로 변형 가능)
• 최대 이분매칭
• Hungarian Method [ppt] [2]
  - 쉬운 버전 [2] (O^4 버전)
  - 비용이 없는 경우(소-우리 배분 문제), 유량 1인 최대유량 문제로 치환 가능.
  - O^3까지 최적화 가능 (slack 변수 사용 필요).
• Hopcraft-Karp 알고리즘
  포드펄커슨 써도 될듯?
• 기본적인 수학적 성질 / 정수론
• 페르마의 소정리
  (a가 소수 p로 나누어 떨어지지 않을때, a^(p-1) mod p = 1)

참조할 만한 문제들: Baekjoon Online Judge

이것 말고 다른 비슷한 것