내가 배운 알고리즘/이론 정리

배운 알고리즘을 정리 해 놓을려고 한다.
백준 핸들은 다음과 같으며, 원래 질문을 디스코드로 많이 받지만, 이제 군대가서 못받는다.
디스코드 : 황현석#9999
사용자 명 : hy3on_se0k

 
hhs2003 정보 (acmicpc.net)
 
왠만하면, 알고리즘은 그때그때 구현하는 것이 좋다고 생각한다. 템플릿 만들어 놓고 하는 것은 연습할 때는 좋지 않다고 생각한다.
 
그리고 코딩하면서 타자 많이 치다보면, 실수도 점점 줄어들고, 타자도 점점 빨라진다. 물론 좀 어려운 알고리즘 한정이다. 너무 왤논은 귀찮으면 템플릿 만들어서 쓰자.
 
넓은 의미로써의 알고리즘은, 그냥 모든 문제 해결 과정의 서술이다 즉, 과정으로 서술 할 수 있는 모든 코드다.
 
하지만, 여기서는 좁은 의미로 특정 문제에 대하여, 그 문제를 유의미한 다항 시간내에 해결 할 수 있도록 과정이 서술 되어 있는 알고리즘을 다룬다.
 
알고리즘을 공부 할 때 느낀것 이지만, 고등학생때, 내가 의미없다고 생각하며 죽어라 배웠던 수학적 귀납법, 연역법과, 모든 수열과 함수개형, 기하학적 수학적 관찰을 여기서 매일 같이 써왔다는 것이다.
 

그래프 Graph

그래프 이론은, 기본적인 DFS / BFS 를 기반으로 시작한다.

1. 이분 그래프
   1. NetWorkFlow, 네트워크 플로우 / 최대유량 문제
      1. Edmonds-Karp Algorithm, 애드몬드-카프 알고리즘
      2. Ford-Fulkerson Algorithm, 포드-풀커슨 알고리즘
      3. Dinic Algorithm, 디닉 알고리즘
   2. Bipartite Matching, 이분 매칭 알고리즘
   3. Minimum Vertex Cover 최소 버텍스 커버 / Kőnig's Theorem 쾨닉의 정리
   4. MCMF 최소 비용 최대 유량 문제
2. 그래프
   1. Dijkstra, 다익스트라 알고리즘 / 최단거리
   2. Union Find, 유니온 파인드
      1. Union by Path Compression, O(N) / 경로압축을 통한 구현
      2. Union by Rank Compression, (height on log N) O(N log N) 
   3. Floyd Warshall Algorithm, 플로이드-워셜 알고리즘 / 최단거리
   4. 위상 정렬
   5. Strongly Connected Components (SCC), 강한 연결 이론
      1. 2 - SAT
3. 트리
   1. SparseTable, 희소배열
   2. Heavy-Light-Decomposition, HLD (세그먼트 트리 응용 필요)
   3. Link-Cut-tree, 링크컷 트리
   4. Divide on Centroid Decomposition and Conquer 센트로이드 분할
   5. Lowest Common Ancestor (LCA) 최소 공통 조상
   6. Kruskal Algorithm, 크루스칼 알고리즘
   7. 오일러 경로 투어 테크닉
   8. 트리에서의 파라매트릭 서치

자료구조 Data Structure

1. HashSet / HashMap
2. LinkedList, Queue, Deque, Stack
3. 값 / 좌표 압축
4. Segment Tree
   1. Lichao Tree, 리차오 트리
   2. Persistent Segment Tree, 퍼시스턴트 세그먼트 트리
   3. Lazy Propagation Segment Tree 느리게 갱신되는 세그먼트 트리
   4. Segment Tree beats! 세그먼트 트리 비츠
   5. Kinetic Tournament 키네틱 세그먼트 트리
5. 펜윅 트리
6. Trie, 트라이 자료구조
7. Splay Tree, 스플레이 트리
8. Link - Cut - Tree, 링크 컷 트리
9. Priority Queue, 우선순위 큐
10. Policy based data structures, PBDS

다이나믹 프로그래밍, Dynamic Programming

1. 일반적인 다이나믹 프로그래밍 O(N), O(NM)
2. knapSack(냅색), 배낭 문제
3. Dynamic Programming on Bit fields, 비트필드 위에서의 다이나믹 프로그래밍
4. Convex Hull Trick (CHT), 컨벡스헐 트릭, 볼록껍질을 이용한 최적화
5. Dynamic Programming Optimization with Divide and conquer, 분할정복을 이용한 최적화
6. Dyanamic Programming on Tree, 트리에서의 다이나믹 프로그래밍
7. Aliens Trick, 매개변수를 통한 제한으로 하는 다이나믹 프로그래밍

문자열, Strings

1. Knuth–Morris–Pratt (KMP) 알고리즘
2. Z 알고리즘
3. 아호 코라식
4. Manacher 알고리즘

수학, Mathematics

1. gcd 알고리즘 O(logN) with LCA
2. 분할 정복을 이용한 거듭 제곱 O(log N)
3. 밀러-라빈 소수 판별
4. Pollard`s rho Algorithm, 폴라드 로 알고리즘
5. Fast Fourier Transform, FFT , 고속 푸리에 변환 알고리즘
6. 확장 유클리드 알고리즘
7. 오일러 피함수

기하학

1. Convex Hull Algorithm
   1. Graham Scan 알고리즘
   2. Jarvis March 알고리즘
   3. Rotating Calipers, 회전하는 캘리퍼스
2. CCW 판별
   1. CCW를 이용한 선분 교차 판정
   2. CCW를 이용한 (반)시계 방향 정렬
3. Incremental delaunay triangulation Algorithm
4. Fortune's Algorithm

그 외 알고리즘, etc Algorithm

1. Mo's Algorithm, 오프라인 쿼리 최적화 알고리즘 O(N sqrt(N))
2. 순열 사이클 분할
3. Offline Dynamic Conectivity, 오프라인 동적 연결성
4. Slope Trick 함수 개형을 통한 최적화
5. Sqrt Decomposition 제곱근 분할법
6. Paralled Binary Search 병렬 이분 탐색
7. Smaller to Larger Technique 작은 집합에서 큰 집합으로 합치는 테크닉
8. Hungarian Algorithm 헝가리안 알고리즘
9. Hiersh Berg 히르쉬 버그 알고리즘
10. Horp croftKarp 호프 크로프트 카프 알고리즘
11. Sparse Table, 희소배열 (트리 알고리즘에 써놓았지만, 이건 사실 트리에서만 쓰는게 아니다, 트리가 함수의 특성이 있을 뿐이다)
12. 유량 그래프 모델링 기법 중 하나인 정점 분할
13. BBST에서 노드 합치기를 구현하자

중요하다고 생각 하는 것

1. 세그먼트 트리는 분할 정복이라는 것을 느껴야함
2. 게임 DP에서, 적에 대한 최적해를 알 수 없을 때, Min - MAX 류의 DP발상
3. 다이나믹 프로그래밍에 대한, 완전한 이해
4. Monge Array에 대한 수학적 이해, 수학적 판별과 직관적 판단

 

내가 알고리즘을 배운 순서는 이렇다. (난이도 순서가 아니다)

1. 그래프탐색 / BFS, DFS (22. 4월 한달 간 공부했다/ 연구소, 구슬치기, 백조의호수, 탈옥, 달이 뜬다 가자 문제품)
2. 비트필드 위에서의 다이나믹 프로그래밍 (22. 4월 말)
3. DP - 냅색 (22. 4월 말)
4. DAG 그래프에서의 위상정렬 (22. 5월 초)
5. 네트워크 플로우 (22. 6월 초)
6. 세그먼트 트리 (22. 6월 말)
7. 쾨닉의 정리 (22. 7월)
8. 강한 연결 요소 (22. 7월 중순)
9. 이분 매칭 (22. 7월 중순)
10. 오일러 투어 트릭 (22. 7월 말)
11. 작은 집합에서 큰 집합으로 합치기 (22. 7월 말)
12. 트리에서의 다이나믹 프로그래밍 (22. 8월 초)
13. Heavy Light Decomposition (22. 8월 초)
14. Divide tree on Centroid and Conquer 센트로이드를 통한 트리에서의 분할정복 (22. 8월 초)
15. 폴라드 로 소인수분해 (22. 8월 중순)
16. 확장 유클리드 알고리즘 (22. 8월 중순)
17. Mo's 알고리즘 (22. 8월 중순)
18. sqrt Decomposition 제곱근 분할법 (22. 8월 중순)
19. DP 다이나믹 프로그래밍의 완전한 이해 (22. 9월 초)
20. Greedy 그리디 (22. 9월 초)
21. ConvexHull 컨벡스헐 (22. 9월 중순)
22. Spinning Calipers 회전하는 캘리퍼스 (22. 9월 중순)
23. 컨벡스헐 트릭을 이용한 다이나믹 프로그래밍 최적화 (22. 9월 중순)
24. 분할 정복을 이용한 다이나믹 프로그래밍 최적화 (22. 9월 말)
25. 오프라인 동적 연결성을 공부 (22. 9월 말)
26. Parlleled Binaray Search (PBS) 병렬 이분 탐색을 공부 (22. 10. 28) ~ (22. 10. 28)
27. Hungarian 헝가리안을 공부 중 (22. 11. 7) ~ (구현 실패, 이해를 다시 해볼 예정)
28. Segment Tree beats 세그비츠 공부 (22. 11. 14) ~ (22. 11. 16)
29. Splay Tree 공부 (22. 11. 17) ~ (22. 12. 2)
30. Link---Cut tree 공부 (22. 12 . 05) ~ (22. 12. 07)
31. Esstree 회문 트리 공부 (22. 12. 07) ~ (포기, lcp를 몰라서)
32. Kinetic Tournament 키네 세그 공부 (22. 12.10) ~ (22. 12. 22)
33. 스케줄링 알고리즘 공부 (22. 12. 15) ~ (포기, 이해가 안되서)
34. Slope Trick 함수 개형을 이용한 최적화 공부 (22. 12. 16) ~ (22. 12. 23)
35. HirschBerg 히르쉬버그 공부 (22. 12. 24) ~ (22. 12. 25)
36. aliens Trick 에일리언 트릭 공부 (22. 12. 29) ~ (22. 12. 30)
37. Incremental delaunay triangulation / Fortune's Algorithm (23. 1.9) ~
38. Esstree 회문 트리 공부 (23. 5. 27)
39. (23.1.17 ) ~ (24.7.16) 군대

 
군대 와서 배운것.
1. 탑트리
2. 오일러 투어 트리
3. 보로노이 다이어 그램
4. HLD를 이용한 tree Dp 최적화

공부를 하면서 중요한 것은 마음가짐을 올바르게 하는 것이다.
계속 배우면서 느낀 것은, 나는 천재가 아니고, 진짜 바보라는 것이었다.
 
바보여서, 진득하게 배우는 방법밖엔 없었다.