알고리즘 공부방

www.secmem.org/blog/2019/10/19/handy-function-about-bit/ 1. 비트마스크 S의 가장 마지막 켜져있는 비트 (LSB) 펜윅 트리에 구현에 자주 이용되는 테크닉이다. int lsb=mask&-mask; 2. 비트마스크 S의 부분집합(submask) 모두 순회 $O(2^N)$에 현재 주어진 비트마스크의 모든 부분집합들을 정확히 한번씩만 순회할 수 있다. for(int i=mask; ; i=mask&(i-1)) { if(i==0) break; } 3. 모든 가능한 비트마스크 S에 대해, S의 부분집합(submask) 모두 순회 모든 $O(2^N)$개의 비트마스크를 모두 순회하며, 각 비트마스크에 대해 부분집합을 모두 순회하는데 드는 시간은 $O(3^N)$이다. S에 ..

1. 로그 자료구조의 속도 비교 BIT (Fenwick Tree) < PQ < Set / Map (STL BBST) < Segment Tree < Lazy Segment Tree < Persistent Segment Tree 단, Set/Map은 삽입되는 자료의 양이 커질 때 급격히 느려진다. 2. Locality 다차원 배열의 인덱싱 순서는 반복문 순회 순서와 같게 하는 것이 제일 빠르다. 실제로 실행 시간의 대부분을 차지하는 것은 덧셈, 곱셈 등의 연산이 아니라, 메모리에 접근하고 값을 저장하는 연산이다. 메모리 접근 연산을 할 때에는 최대한 접근하는 위치들이 서로 인접해 있는 것이 좋다. stackoverflow.com/questions/16699247/what-is-a-cache-friendly-..

문제 oj.uz/problem/view/JOI17_sparklers 문제 보기 - Sparklers (JOI17_sparklers) :: oj.uz 문제 보기 - Sparklers (JOI17_sparklers) oj.uz 수직선 위에 N명의 사람들이 폭죽을 하나씩 들고 서 있다. 처음에는 K번째 사람의 폭죽에만 불이 붙어 있으며, 폭죽에 불이 처음 붙은 후로부터 T초 동안만 불꽃이 유지된다. 불꽃이 꺼지기 전에 어떤 다른 사람과 같은 위치에 있게 되면 그 사람에게 불꽃을 옮길 수 있다. 또한, 각 사람이 1초동안 움직일 수 있는 최대 거리인 속도 X가 정해져 있을 때, 모든 사람의 폭죽에 불이 한번씩 붙을 수 있기 위한 최소의 정수 속도 X를 구해야 한다. $N $[1, N]$은 $[K, K]$ -> ..

많은 Tree DP 문제들의 경우, 각 노드에서 특정 시간 복잡도로 노드들을 합치는 작업을 한다. 일반성을 잃지 않고, 노드의 자식이 3개 이상이라면, 더미 노드를 부모 쪽으로 계속 만들어 주며, 모든 트리를 이진 트리 형태로 변형시킬 수 있다. 따라서, 이진 트리에서 자식 노드 두개의 값만을 합쳐주는 문제로 생각한다. 1. $A$, $B$를 합치기 위해서 $sz(A) \cdot sz(B)$의 시간이 필요할 때, 전체 시간복잡도 $O(N^2)$에 합칠 수 있다. (KOI18 검은 돌) $sz(A) \cdot sz(B)$의 값은 왼쪽 자식의 서브트리의 모든 노드와 오른쪽 자식의 모든 서브트리의 노드를 연결했을 때 간선의 수와 같다. 이 때 어떠한 두 정점 $u$, $v$가 합쳐지는 위치는 바로 그 노드의 ..

Andrew's Chain은 주어진 점 집합들의 Convex Hull을 $O(NlogN)$에 구할 수 있게 해주는 Graham's Scan과는 다른 알고리즘이다. Graham's Scan과는 다르게 Upper Hull과 Lower Hull로 분리해낼 수 있다는 장점이 있고, 정렬 또한 각도 정렬이 아닌 단순한 x축 기준 정렬만 필요하다. 1. 전체 점들을 x축 기준, x축이 같다면 y축 기준으로 정렬한다. 2. 스택에 점들을 하나씩 넣으며, 다음 불변식을 유지하도록 삽입한다. 스택의 점들은 시계 방향으로, 즉 ccw가 음수인 방향으로 굽어 있다는 불변식을 만족해야 한다. 불변식을 만족하지 않다면 점들을 위에서부터 삭제하고 현재 점을 삽입한다. 이 과정을 통해 Upper Hull을 구할 수 있다. 3. 배..

Graham's Scan은 주어진 점 집합들의 Convex Hull을 $O(NlogN)$에 구하는 알고리즘이다. 1. Convex Hull에 무조건 포함되는 한 점 S를 잡는다. 일반적으로 x좌표가 최소인 점, 만약 여러개 있다면 y좌표가 최소인 점으로 잡는다. 2. S를 기준으로 전체 점들을 각도 순으로 정렬한다. 만약 S, p, q가 일직선 위에 있다면 S와의 거리 순으로 정렬한다. 3. 정렬한 순서대로 점들을 하나씩 보며, 스택에 점들을 하나씩 추가한다. 단, 스택의 점들은 들어가 있는 순서대로 시계 반대 방향으로, 즉 ccw가 양수로 유지되어야 한다. 이 불변식을 만족할 수 있도록 적절히 스택에서 점들을 제거해준 후, 새로운 점을 추가해준다. #include using namespace std; ..

문제 oj.uz/problem/view/IOI20_plants 문제 보기 - 식물 비교 (IOI20_plants) :: oj.uz 문제 보기 - 식물 비교 (IOI20_plants) oj.uz 원 위에 0~N-1의 N개의 수가 배열되어 있는 순열 $A$가 있다. 이 때 $R_i$는 i번째 칸부터 오른쪽으로 연속한 $K-1$개의 수들 중 $A_i$보다 큰 수들의 개수로 정의된다. 수열 $R_i$와 쿼리 (x, y)가 Q개 주어질 때, 가능한 모든 $A_i$에서 $A_xA_y$를 만족하는지, 아니면 두 경우 모두 가능한지 판별해야 한다. 단, 주어지는 $R$는 대응되는 $A$가 적어도 하나 존재하는 수열로 주어진다. $K1; init(node*2, tl, mid); init(node*2+1, mid+1, t..

D문제 oj.uz/problem/view/JOI18_tents 문제 보기 - Tents (JOI18_tents) :: oj.uz 문제 보기 - Tents (JOI18_tents) oj.uz N*M의 격자에 텐트를 배치하는데, 각 텐트별 동, 서, 남, 북의 4가지 방향이 있다. 어떤 두 텐트가 같은 행이나 열에 있다면 이 두 텐트는 서로 마주보고 있는 방향이어야 한다. 이 조건들을 모두 만족시킬 때 전체 텐트의 배치로 가능한 경우의 수를 구하자. $N, M