본문 바로가기

Problem Solving/Algorithm12

Minimum Spanning Tree(최소 스패닝 트리) 1. Kruskal Algorithm (크루스칼 알고리즘) : Merge Sort + Union-Find2. Prim Algorithm(프림 알고리즘) : Heap 2017. 2. 7.
Shortest Path Faster Algorithm The Shortest Path Faster Algorithm (SPFA) is a single-source shortest paths algorithm. It is similar to Dijkstra's algorithm in that it performs relaxations on nodes popped from some sort of queue, but, unlike Dijkstra's, it is usable on graphs containing edges of negative weight, like the Bellman-Ford algorithm. Its value lies in the fact that, in the average case, it is likely to outperform Be.. 2016. 7. 28.
Divide & Conquer Optimization in DP 동적계획법에서의 분할정복 최적화 기법에 대해서 글을 써보려고 한다. 일반적으로 j E1) return; int M = (L1 + R1) / 2; ll res = 0; for (int i = max(S1, M - D); i res) res = T[M] * (M - i) + V[i], opt[M] = i; if (answer < res) answer = res; f(L1, M - 1, S1, opt[M]); f(M + 1, R1, opt[M], E1); } int main() { scanf("%d%d", &N, &D); for (int i = 1; i 2016. 6. 12.
Lowest Common Ancestor(최소 공통 조상) 1. 두 노드 a와 b에 대해, 서로 높이가 다르다면 높이를 맞추어줌. 2. 2의 거듭제곱 꼴로 높이를 낮추다가 공통 조상이 없어지는 곳으로 이동. int lca(int a, int b, int K) { if (a == b) return a; //a = b // LCA는 a나 b보다 최소 높이 1보다 위에 있음. for (int i = K; i >= 0; i--) { if (parent[i][a] != parent[i][b]) return lca(parent[i][a], parent[i][b], i); //분기되는 최초의 지점으로 이동 } return parent[0][a]; // LCA는 바로 위의 조상. } 3. a와 b가 같아지거나 LCA를 찾기 이전까지 계속 '2.'를 반복. 2016. 3. 31.
Smallest Enclosing Circle/Sphere Problem 관련하여 내가 Codeforces에 올린 Blog article흔히 가장 먼 두 점의 거리를 2로 나누면 답이 되는 원 또는 구의 반지름이 될 거라 생각하지만, 원의 경우에서부터 다음과 같은 반례가 있다.Codeforces에 올린 글에 링크 걸어놓은 논문에 의하면 gradient descent 방법으로 최적해를 구할 수 있음이 밝혀져 있다.따라서 전체 점들에 대한 컨벡스 다각형의 내부의 한 점에서 가장 먼 점으로 계속 이동해 나가다보면(한 term에 이동하는 비율은 단조 감소해야함) 반지름이 최소인 구의 좌표를 알 수 있다.연습문제로는 내가 만든 BOJ 11930번 문제가 있다. 2016. 2. 17.

티스토리툴바