서론 Tarjan’s algorithm에 대해 알아보자. SCC를 구하는 알고리즘은 많지만 크게 두 가지가 존재한다. Kosaraju’s algorithm Tarjan’s algorithm 코사라주 알고리즘은 타잔에 비하면 이해도 쉽고, 구현도 쉬운 편이다. 허나 역방향 그래프 $G^r$과 그래프의 순회를 수행한 정보를 저장할 스택 ...

서론 BIT(Binary Indexed Tree)에 대해 알아보자. 우선 이 자료구조를 알기 전에 Segment Tree에 대해 알고 있다는 전제로 작성한다. 둘다 query와 update가 핵심이고, 시간복잡도도 같다. CP에서 BIT라는 자료구조는 세그트리에 비해 구현에서 이점이 존재한다. 하지만, BIT를 사람들이 잘 안쓰는 이유가 존재하...

서론 KMP 알고리즘에 대해 알아보자. 본론 KMP에 대한 좋은 글은 인터넷에 많이 있으니, 핵심만 알아보자. 결국 KMP 알고리즘은 우리가 원하는 패턴 문자열 $P$의 prefix와 suffix의 최대 길이를 어떻게 구해야 되는지가 관건이다. 문자열 $S[0 \dots n-1]$에 대하여 위의 최대 길이를 구해야 한다. 이러한 길이를 구하기 ...

6주차 계획 알고리즘 공부함 test

5주차 계획 SegTree 템플릿 정리 대회에서 사용하기 위한 세그트리 템플릿을 정리하였다. 링크

4주차 계획 Lazy SegTree 일반적인 세그트리에서 구간 업데이트, 질의가 가능한 자료구조인 Lazy Segment Tree를 공부했다. 링크

3주차 계획 Tarjan’s algorithm 복습 SCC를 찾는 Tarjan’s 알고리즘에 대해 복습하였고, 이에 관련하여 포스트를 작성하였다. 링크

2주차 계획 BIT(Binary Indexed Tree)를 복습 Fenwick Tree, 즉 BIT에 공부하였고 이에 대한 포스트를 작성하였다. 링크

1주차 계획 KMP 알고리즘 복습 kmp 알고리즘에 대해 복습하였고, 이에 관련하여 포스트를 작성하였다. 링크

목표 알고리즘 딥한 알고리즘(대회용)을 공부하는게 목표이다. 1주차: KMP 알고리즘 2주차: BIT 자료구조 3주차: Tarjan’s algorithm(Finding SCC) 4주차: Lazy SegTree 5주차: Segment Tree 6주차: 이분 매칭 1주차 링크 2주차 링크 3주차 링크 4주차 링크 5주차...