알고리즘, 자료구조 (4) 썸네일형 리스트형 Path Comprssion DSU의 amortized O(logN) 증명 Weighted union rule, Path compression 중 하나만 사용하면 amotized \(O(logN)\), 둘 모두를 사용하면 amortized \(O(\alpha(N))\)임이 잘 알려져있습니다. Path compression만을 사용했을 때 시간복잡도의 증명은 한글 자료가 잘 없는 것 같아 작성합니다. Heavy Light Decomposition스러운 논리를 사용합니다. 정점 u가 v의 자식일 때 sz[v] \(\leq\) sz[u] / 2이면 u->v간선은 light edge, 나머지는 heavy edge라고 해봅시다. 당연하게도 heavy edge는 정점당 하나만 생깁니다 (sz[x] := x의 서브트리의 크기) 임의의 정점 (u, v)에 대해 u->v로 가는 경로는 최대 \.. Simulated Annealing INTRO 동아리에서 진행하는 방학 프로젝트에서 다들 휴리스틱을 고르는 분위기여서 저 또한 Simulated Annealing을 적용할 수 있는 문제로 잘 알려진 TSP를 고르게 되었습니다. 언젠가 봐야지하고 6개월쯤 미뤄뒀던 Simulated Annealing을 이제야... (Optimization By Simulated Annealing에도 TSP가 언급되어있네요) 방학 프로젝트의 결과물은 아래 링크에 있습니다. 보고서를 급하게 쓰기도 했고 제가 잘 아는 것도 아니라 오류가 꽤 있을거라 생각됩니다. 너그럽게 봐주세요... https://github.com/kim1109123/Euclidean_TSP GitHub - kim1109123/Euclidean_TSP Contribute to kim110912.. Randomize Binary Search Trees, Treap INTRO 잘 아려진 BBST(Balanced Binary Search Tree : 균형이진탐색트리)의 종류로는 rb tree, b tree 등이 있습니다. 그러나 위의 rb tree와 같이 대부분의 연산을 \(O(logN)\)에 처리하는 트리는 동작 자체도 복잡하고 구현량이 많기 때문에 직접 구현해가며 PS에 사용하기 어렵습니다. (stl에 있는 것을 가져다 쓰면 좋겠지만 연산을 변형해야하는 경우도 존재하니까요) 그래서 삽입, 삭제 등의 연산에 amortized \(O(logN)\)의 시간복잡도를 가지며 상대적으로 구현량이 적은 Splay Tree를 가장 많이 사용합니다. 하지만 Splay Tree도 zig-zag step 등 헷갈릴만한 요소가 많아서 저는 Treap을 선호합니다. Treap은 일반적인.. Efficient Range Minimum Queries using Binary Indexed Trees 주제 : 역원이 존재하지 않는 연산에 대한 구간 쿼리 (펜윅 트리) 펜윅트리에서 요구하는 연산을 $, 이 연산의 역원을 #라고 정의하겠습니다. 흔히 펜윅트리에서 구간 [L, R]에 대한 쿼리를 처리할 때는 ([1, R] 쿼리의 답) # ([1, L) 쿼리의 답)과 같은 형태로 답을 구합니다. $이 +라고 한다면 ([1, R] 쿼리의 답) - ([1, L) 쿼리의 답)을 의미합니다. * 역원은 연산 *에 대해 a * ? = 항등원을 만족하는 연산 ?를 말합니다. 역원이 존재하지 않는 연산은 어떻게 처리해야할까요? 그 예로 \( min(a, ?) = \infty \)를 만족하는 ?는 존재하지 않기 때문에 min에는 역원이 존재하지 않습니다. 그래서 일반적인 형태의 펜윅 트리로는 구간 [L, R]의 min값을.. 이전 1 다음
