-
kjp4155's profile image
kjp4155
May 15, 2019
Atcoder Educational DP contest 풀이
Atcoder에서 열렸던 Educational DP contest 문제들에 대한 풀이입니다. 자주 나오는 다이나믹 프로그래밍 유형들을 연습할 수 있는 좋은 셋이라고 생각합니다. 문제마다 간략한 풀이를 작성했습니다. 코드는 Atcoder에서 자유롭게 열람이 가능하므로 문제마다 링크를 달아두었습니다. 어느정도는 난이도 순서대로 정렬되어 있지만, 사람마다 느끼는 난이도가 다를 수 있습니다. A. Frog 1 문제 링크 $d_i :$ $i$ 번째 Stone까지 도달하는 최소 비용 $d_i = min(d_{i-1} + h_i - h_{i-1} ,\ d_{i-2} + h_i - h_{i-2} )$ 위와 같은 점화식으로 간단히 해결할 수...
-
kjp4155's profile image
kjp4155
March 27, 2019
O(1) LCA Algorithm (with Sparse Table)
목표 및 문제 소개 LCA(Lowest Common Ancestor)란 루트가 정해진 트리에서, 두 노드 간의 공통 조상이면서 루트에서 가장 먼 노드를 뜻합니다. 노드가 $N$개인 트리에서 임의의 두 노드 간의 LCA를 쿼리당 $O(lgN)$에 구하는 알고리즘은 잘 알려져 있습니다. 각 노드별로 $ 2^k $ 번째 조상을 미리 계산해둔 뒤, Binary Lifting을 활용해 구하는 방식입니다. 이에 대한 지식이 부족하다면 링크 에서 먼저 공부한 뒤에 이 글을 읽으시는 것을 추천합니다. 이 글에서 소개하고자 하는 알고리즘과 밀접한 관련은 없지만, 전반적인 개념에 도움이...
-
kjp4155's profile image
kjp4155
January 3, 2019
LiChao Tree (with Dynamic Segment Tree)
목표 LiChao Tree는 직선이 실시간으로 추가되는 Convex hull trick 문제를 해결하기 위한 자료구조입니다. 구현이 비교적 간단하면서 유용한 자료구조인데, 한글로 설명된 자료가 없어 포스트를 작성하게 되었습니다. 이 포스트의 목표는 LiChao Tree를 이용해 (백준 12795) 반평면 땅따먹기 문제를 해결하는 것입니다. 이 문제를 해결하는 방법은 다양하지만, LiChao Tree를 사용한 솔루션이 가장 수행시간이 빠릅니다. 사전지식 - Dynamic Segment Tree LiChao Tree는 Dynamic Segment Tree에 기반한 자료구조입니다. Dynamic Segment Tree란 구간의 범위에 따라 모든 노드를 만들어놓고 시작하는 일반적인 Segment Tree와는...