PBDS Hash
PBDS Hash에 관한 간단한 정리.
02 / KNOWLEDGE BASE
지식 노트.
알고리즘, 코드 조각, 개념 정리. 필요할 때 다시 꺼내 보는 지식.
모든 노트 49
최근 업데이트 순Hilbert Curve
Hilbert Curve는 정수좌표계에서 사용가능한 일종의 Space-Filling Curve 이다. 1차원 좌표계에서 어떤 좌표 리스트가 있어서 그들을 최단 경로로 방문해야 한다고 한다면 이를 구하는 것은 간단하다. 위치를 정렬해서 오름차순이나 내림차순으로 방문하면 된다. 2차원 좌표
Angle Sort
2D 좌표계에서 외판원 문제를 생각해보자. 정점 P_1, P_2, ..., P_N을 임의의 순서로 전부 순회하고 다시 출발한 정점으로 돌아온다고 할 때, 해당 경로의 휴리스틱적인 최단거리는 어떻게 될 것인가?
Dense BFS
inwooleeme 님이 알려준 밀집 그래프에서의 그래프 최단 거리를 구하는 방법. 관련 문제를 풀면서 확인해보자.
Berlekamp Massey
Berlekamp Massey 관련 기록.
TSP
일단 표제만 정리해두고, 나중에 심도있게 정리해볼 예정.
Graph Basic
그래프는 다음과 같은 요소로 이루어져 있다.
Greedy Basic
수학 증명이 첨가된 PS 이론은 가젤님 블로그에 잘 정리되어 있다. 아래 링크에서 정리한 기본 이론이다.
FFT
언젠가 정리할 알고리즘. 읽을만한 글들을 먼저 정리해 둔다.
빠른 거듭제곱과 Modular Inverse
일반적으로 특정 수를 N 제곱하는데 걸리는 시간은 O(N) 이지만, 간단한 수학으로 이를 O(\log N)에 마칠 수 있다. 이는 거듭제곱 하고자 하는 수를 이진수로 보고, binary lifting 하는 것이라고 보면 된다.
LCS
LCS는 Longest Common Subsequence의 약자로, 두 문자열에서 최대로 공통되는 부분 중 제일 긴 것을 찾는다. 알고리즘은 평범한 O(N^2) 인 대표 DP 유형이지만, 구현 난이도가 살짝 까다롭기 때문에, 정리해본다.
Mo's
개인적으로 공부하다가 그 심플함과 발상에 충격먹은 알고리즘 1순위 (2023/07 기준)
Hash
hash에서 충돌 방지 정책은 중요하다. 가장 간단하게는 이미 사용중인 영역을 만났을 때 주소값을 +1 하는 Open Addressing의 Linear Probing 방식이 대표적이지만, 여기서는 Chaining 방식의 구현을 알아보겠다. Chaining 방식의 경우 값 삭제도 원할하게
A*
유명한 길찾기 휴리스틱 알고리즘. 이 알고리즘 관련해서는 아래 사이트에 모든게 다 있는 듯 하다.
Scenery
ICPC 유명 문제 Scenery 에 대한 풀이 정리
정수론 일반
정수론 일반 관련 기록.
DP Basic
구체적인 기본 유형 풀이는 위 링크에 정리 업데이트 예정이고, 여기는 해당 링크에 있는 유형의 키워드만 정리한다.
Job Scheduling
이 유형은 문제에서 주어진 조건에 따라 풀이 방법이 매우 다양하게 나뉠 수 있다.
Splay Tree
Splay 연산은 해당되는 Node를 루트로 올리는 연산이다. 이를 수행하기 위해 Rotaate 함수를 만드는데, 이 함수는 해당 노드를 부모로 올리는 역할이다.
Binary Search Tree
Worst 때문에 쓸 일 없겠지만 basic 중의 basic.
Segment Tree
Point Update와 Range Query를 지원하는 가장 기본적인 SegTree이다. 메모리는 2*N 만큼 선언하면 된다.
Bipartite Matching
Bipartite Matching 관련 기록.
Dinic
Dinic 관련 기록.
Edmonds-Karp
Ford-Fulkerson 방법을 BFS로 구현한 것을 Edmonds-Karp Algorithm이라고 한다.
MCMF
MCMF 관련 기록.
Merge Sort
Merge Sort 관련 기록.
Radix Sort
Radix Sort 관련 기록.
Binary Search
Binary Search의 구현에 관한 정리. 주제 자체는 solved.ac 기준 실버 티어 정도일 수도 있겠지만, 제대로 쓰기까지 상당한 시간이 걸리는 주제이기도 하다. 또, 각종 알고리즘에서 뜬금없이 튀어나오는 1순위. O(n)을 O(log n)으로 줄여주는 강력한 무기.
Dijkstra
Dijkstra 관련 기록.
Floyd Warshall
Floyd Warshall 관련 기록.
SPFA
SPFA 관련 기록.
Bubble Sort
Bubble Sort 관련 기록.
Quick Sort
Quick Sort 관련 기록.
Queue
Queue 관련 기록.
Vector
Vector 관련 기록.
BigInt
BigInt 관련 기록.
Trie
Trie 관련 기록.
2D-Fenwick Tree
2D-Fenwick Tree 관련 기록.
Fenwick Tree
Fenwick Tree 관련 기록.
Barrett Reduction
Assembly Level에서 가장 느린 Arithmetic 연산을 꼽으라고 한다면, modular 연산일 것이다. 보통 PS에서는 나눗셈 연산이 소수값이 나오지 않도록 하기 위해서 modular 연산을 한 값을 출력하도록 하는 경우가 많은데, 이 경우 일단 modular 연산 자체를
PBDS Set
PBDS Set에 관한 간단한 정리. 알게 되었는데 정리 안하면 나중에 다시 맨땅에서 구글링 해야하므로 한번 알게 된 내용 정리하고 가보려고 한다.
SIMD
SIMD에 관한 간단한 정리. 알게 되었는데 정리 안하면 나중에 다시 맨땅에서 구글링 해야하므로 한번 알게 된 내용 정리하고 가보려고 한다.
Disjoint Set
MST의 크루스칼과 같은 알고리즘에서 유용하게 쓰이는 Disjoint Set에 대한 간단한 정리
Convex Hull
기하 문제에서 많이 쓰이는 볼록 껍질 알고리즘 Convex Hull에 관한 정리
Heap
Heap 관련 정리. Heap은 주로 Array로 구현하며, 가장 큰 아이템이나 가장 작은 아이템을 O(1)의 시간복잡도로 구할 수 있으며, 이를 업데이트 하는데에 O(log n)의 시간이 걸리는 자료구조이다. set 처럼 k 값을 가지는 아이템을 찾거나 할 수는 없지만, 구조가 비교적
LCA
LCA는 Least Common Ancestor의 약자이다. Tree에서의 공통 조상을 찾는 문제에 사용되는 알고리즘이다. 공통 조상이 여러개 있을 수 있으므로, 그 중에 제일 빠른 조상을 LCA로 정의한다. input으로는 서로 다른 두 Node가 주어진다. 이 두 Node를 l과 r
LIS
자꾸 까먹는 LIS 한번 정리해보기
정렬 기본
정렬 알고리즘 관련 기본 정리
Bitcnt
Bit count는 말 그대로 int 나 long long 등에 저장된 숫자가 2진법으로 1이 몇개가 켜져있는지를 세는 것을 말한다. 흔히 __builtin_popcount로 사용하지만, 직접 구현할 경우를 살펴본다.