알고리즘 공부를 시작하면서
개발/알고리즘

알고리즘 공부를 시작하면서

2021년 7월 14일, Baekjoon Online Judge에 가입했다. 그 후 한 달 남짓한 기간동안 500문제 정도를 풀었고, 기초적인 알고리즘을 공부하며 AtCoder와 Codeforces에도 참가하게 되었다.

 

그런데 지금까지는 알고리즘을 공부하면서 정리를 해 놓지 않고 머릿속으로만 이해했다. 그렇게 하니까 학습을 제대로 하지 않는 것 같은 느낌이 들어서, 이제부터 다시 기초적인 알고리즘을 블로그에 정리해두려고 한다.

 

아직 초보자의 글이고 공부하면서 정리해 놓는 거라 오류나 잘못된 설명, 혼동을 줄 수 있는 표현을 굉장히 많이 사용할 수 있다. 읽는 사람이 있을지는 모르겠지만 만약 있다면 읽으시면서 오류나 설명이 더 필요한 부분은 댓글로 알려주시면 더 공부해서 수정/보충하도록 하겠다.

목차

목차는 난이도 순이 아니다. 또한 더 밑에 있는 내용이 위에 있는 내용의 선행조건이 될 수도 있다.

 

Part I - 기초 알고리즘

Part II - 수학

Part III - 그래프와 트리

  • 그래프의 정의와 표현
  • 깊이 우선 탐색(Depth-First Search, DFS)
  • 너비 우선 탐색(Breadth-First Search, BFS)
  • 그리드에서의 그래프 탐색(DFS/BFS on Grid)
  • 다익스트라 알고리즘(Dijkstra)
  • 플로이드-와샬 알고리즘(Floyd-Warshall)
  • 벨만-포드 알고리즘(Bellman-Ford)
  • SPFA(Shortest Path Faster Algorithm)
  • 0-1 너비 우선 탐색(0-1 BFS)
  • 위상 정렬(Topological Sort)
  • 이분 그래프(Bipartite Graph)
  • 트리(Tree)
  • 트리의 순회(Tree Treversal)
  • 트리의 지름(Diameter of Tree)
  • 최소 스패닝 트리(Minimum Spanning Tree)
  • 크루스칼 알고리즘(Kruskal's Algorithm)
  • 프림 알고리즘(Prim's Algorithm)
  • 오일러 경로/회로(Eulerian Path/Circuit)
  • 강한 연결 요소(Strongly Connected Component)
  • 이중 연결 요소(Biconnected Component)
  • 2-SAT 문제(2-Satisfiabilty Problem)
  • 최소 공통 조상(Lowest Common Ancestor)
  • 네트워크 유량(Network Flow)
  • 포드-풀커슨 알고리즘(Ford-Fulkerson)
  • 에드몬드-카프 알고리즘(Edmonds-Karp)
  • 이분 매칭(Bipartite Matching)
  • 최소 컷(Minimum Cut)
  • 최소 비용 최대 유량(Minimum Cost Maximum Flow)
  • 디닉 알고리즘(Dinic's Algorithm)
  • 호프크로프트-카프 알고리즘(Hopcroft-Karp)

Part IV - 동적 계획법

  • 누적 합(Prefix Sum)
  • 최장 증가 부분 수열(LIS)
  • 최장 공통 부분 수열(LCS)
  • 배낭 문제(Knapsack)
  • 트리에서의 동적 계획법(Tree DP)
  • 비트마스킹을 이용한 동적 계획법(Bit DP)
  • 행렬을 이용한 동적 계획법
  • 볼록 껍질을 이용한 최적화(Convex Hull Trick)
  • 분할 정복을 이용한 최적화(D&C Optimization)
  • 단조 큐를 이용한 최적화(Monotone Queue Optimization)
  • 커누스 최적화(Knuth's Optimization)
  • 함수 개형을 이용한 최적화(Slope Trick)
  • 에일리언 트릭(Alien Trick)

Part V - 자료 구조

  • 이진 검색 트리(Binary Search Tree)
  • 유니온 파인드(Union-Find)
  • 희소 배열(Sparse Table)
  • 세그먼트 트리(Segment Tree)
  • 펜윅 트리(Fenwick Tree)
  • 레이지 프로퍼게이션(Lazy Propagation)
  • 머지 소트 트리(Merge Sort Tree)
  • 평방 분할(Square Root Decomposition)
  • Mo's Algorithm
  • 스플레이 트리(Splay Tree)
  • 레드 블랙 트리(Red-Black Tree)
  • AVL 트리(AVL Tree)
  • 동적 세그먼트 트리(Dynamic Segment Tree)
  • 퍼시스턴트 세그먼트 트리(Persistent Segment Tree)
  • 세그먼트 트리 비츠(Segment Tree Beats)
  • 블록 컷 트리(Block-Cut Tree)
  • 헤비-라이트 분할(Heavy-Light Decomposition)
  • 센트로이드 분할(Centroid Decomposition)
  • 링크 컷 트리(Link-Cut Tree)
  • 리-차오 트리(Li-Chao Tree)

Part VI - 문자열

  • 해시(Hashing)
  • 정규 표현식(Regular Expression)
  • KMP 알고리즘
  • 라빈-카프 알고리즘(Rabin-Karp)
  • 트라이(Trie)
  • Manacher's Algorithm
  • Z 알고리즘
  • 접미사 배열/LCP 배열(Suffix Array/LCP Array)
  • 아호-코라식 알고리즘(Aho-Corasick)

Part VII - 기하

  • CCW(Counter-Clockwise)
  • 선분 교차(Line Intersection)
  • 다각형의 넓이(Area of Polygon)
  • 볼록 껍질(Convex Hull)
  • 그라함 스캔(Graham Scan)
  • 모노톤 체인(Monotone Chain)
  • 회전하는 캘리퍼스(Rotating Calipers)
  • 반평면 교집합(Half-Plane Intersection)
  • 최소 외접원(Minimum Enclosing Circle)

Part VII - 기타

  • 비트마스킹(Bitmasking)
  • 투 포인터(Two Pointers)
  • 슬라이딩 윈도우(Sliding Windows)
  • 스위핑(Sweeping)
  • Meet in the Middle
  • 좌표 압축(Coordinate Compression)
  • 양방향 탐색(Bidirectional Search)
  • 구성적(Constructive)
  • 애드 혹(Ad-Hoc)
  • 휴리스틱(Heuristic)
  • 무작위화(Randomization)
  • 오프라인 쿼리(Offline Query)

    티스토리툴바