알고리즘 공부방

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

Biconnected Component는 biconnected (단절점이 없는) maximal subgraph이다. BCC는 그래프를 단절점/단절선을 기준으로 쪼갠 후, 이를 기준으로 정점/간선들을 묶어 트리로 만든다. 크게 2가지의 BCC가 있다. 1. Edge disjoint BCC = 단절점을 기준으로 쪼갠 간선의 집합 2. Vertex disjoint BCC = 단절선을 기준으로 쪼갠 정점의 집합 Vertex disjoint BCC의 경우에는 단절선을 모두 자른 후, 남은 컴포넌트들이 하나의 BCC를 구성하고, 이를 하나의 정점으로 압축한다면 트리가 된다. Edge disjoint BCC의 경우에는 BCC가 간선의 집합으로 구성되어 있기 때문에, 한 정점은 여러 개의 BCC에 포함될 수 있다. 특..

1. 합이 N인 수들 중 서로 다른 수들의 개수는 최대 $O(\sqrt{N})$개 이다. 서로 다른 수들을 최대한 많이 만들기 위해서는, 모든 수들이 서로 다르고, 1, 2, ... 와 같이 1부터 하나씩 채워 나가는 것이다. $1+2+...+x=N$이니, $x=N$이니, $\sqrt{N}$ 이상의 수들은 많아봤자 $O(\sqrt{N})$개가 된다. $\sqrt{N}$ 이상과 이하인 수들로 나누어 $\sqrt{N}$ 이상인 수들은 그 개수가 $\sqrt{N}$개 이하임을 이용하고, $\sqrt{N}$ 이하인 수들은 그 크기가 $\sqrt{N}$이하임을 이용하여 서로 다른 방법으로 해결할 수 있다.

문제 oj.uz/problem/view/JOI18_construction 문제 보기 - Construction of Highway (JOI18_construction) :: oj.uz 문제 보기 - Construction of Highway (JOI18_construction) oj.uz 트리가 주어지고, 처음에는 1번 노드밖에 없다. 한번의 업데이트 때마다, 지금 존재하는 트리에 하나의 간선을 추가하여 새로운 노드를 붙이는데, 이 때 루트에서부터 새로 붙인 노드까지의 경로의 정점들의 가중치를 일렬로 나열했을 때 만들어지는 수열의 inversion을 출력해야 한다. 또한, 업데이트 이후, 루트에서부터 새로 붙인 노드까지의 경로의 모든 정점들의 가중치는 모두 새로 붙인 정점의 가중치로 바뀌게 된다. $N

1. 각 노드에서 light edge를 타고 갈 때마다 서브트리의 크기는 1/2 이하로 감소한다. heavy edge가 가장 서브트리의 크기가 큰 간선이므로, 만약 light edge를 타고 가도 서브트리의 크기가 1/2 초과로 유지된다면, $sz[heavy]>=sz[light]>N/2$, $sz[heavy]+sz[light]>N$으로 모순이다. 2. 각 노드에서 루트 방향으로 부모를 타고 올라갈 때 만나는 light edge의 개수는 $O(logN)$개이다. Property 1에 의해 light edge를 타고 내려가면 서브트리의 크기가 1/2 이하로 감소하니, light edge를 타고 올라가면 서브트리의 크기가 2배 이상으로 증가한다. 전체 트리의 노드의 수가 N개 이니, light edge의 수는..

문제 oj.uz/problem/view/JOI19_cake3 문제 보기 - Cake 3 (JOI19_cake3) :: oj.uz 문제 보기 - Cake 3 (JOI19_cake3) oj.uz N개의 케이크 조각이 있고, 이중 M개를 뽑아 적당히 배열하여 $\sum_{i=1}^{M}V_i-\sum_{i=1}^{M}|C_i-C_{i+1}|$값을 최대화해야 한다. $M1; node->lc=new Node(); node->rc=new Node(); makeTree(node->lc, tl, mid); makeTree(node->rc, mid+1, tr); } Node *addTree(Node *node, int tl, int tr, int pos) { if(poscnt+1; ret->sum=node->sum+co..

문제 oj.uz/problem/view/JOI19_mergers 문제 보기 - Mergers (JOI19_mergers) :: oj.uz 문제 보기 - Mergers (JOI19_mergers) oj.uz 트리 상의 각 노드는 특정한 색으로 칠해져 있을 때, 트리가 "분할 가능하다"는 것은 트리를 연결된 두 개의 컴포넌트로 쪼개서, 모든 색이 정확히 하나의 컴포넌트에만 속하게 할 수 있다는 것이다. 서로 다른 두 색을 합칠 수 있을 때, 합치는 연산의 횟수를 최소로 해서 트리가 분할 가능하지 않도록 해야 한다. $Ndep[v]) swap(u, v); for(int i=20; i>=0; i--) if(dep[par[v][i]]>=dep[u]) v=par[v][i]; if(u==v) return u; for..