-
Heavy-Light Decomposition
서론 알고리즘 문제를 풀다 보면 많은 경우에 문제를 그래프 문제로 모델화할 수 있음을 보게 됩니다. 여러 요소들간의 관계가 주어지는 경우에는 각 요소를 정점으로, 관계를 간선으로 두는 방식의 모델화가 자주 사용되고, DP 문제는 대다수의 경우 DAG(Directed Acyclic Graph)의 형태로 각 상태가 이어지게 되므로 역시 그래프 문제의 일종으로 볼 수 있습니다. 그런데 특별한 제약 조건이 없는 그래프 문제의 경우 이 모델화에 성공하면 대체로 문제가 쉬워지거나, 전형적인 알고리즘을 요구하는 문제로 바뀌게 됩니다. 오히려 제약 조건이 추가된 형태일수록 그...
-
2018 ICPC world Finals C. Conquer the world와 Tree DP optimization
2018년 World Finals에서 어느 팀도 풀지 못했던 문제인 Conquer the world(https://www.acmicpc.net/problem/15691) 문제에 대한 풀이와 사용된 아이디어에 대해 간단히 소개한다. 문제 문제 자체는 굉장히 간단하다. edge마다 이동할 때 드는 cost가 있는 트리가 있고, vertex $i$에 현재 $X_i$명이 있으며 최종 상태에는 적어도 $Y_i$명이 있어야 할 때, 사용해야 하는 cost를 minimize하는 문제이다. Heavy-Light Decomposition 이미 상당히 유명해진 트릭인 heavy-light decomposition에 대해 먼저 간략히 설명하고 넘어갈 것이다. rooted tree에서 heavy edge란, vertex $v$의 자식들 중 가장 subtree의 크기가 큰(vertex...
-
Exchange argument
Exchange argument란? 임의의 상태에서 매순간 손해보지 않으면서, 원소끼리의 교환을 통해 얻어지는 상태로 나아가는 것을 반복하면 최적의 상태를 얻을 수 있다는 탐욕적인 주장입니다. 이해를 위해 다양한 문제에서의 활용을 소개해보겠습니다. 구두 수선공(링크) 우리는 주어지는 작업의 순서를 정해서 최적의 작업순서를 정해야 합니다. 임의의 작업 순서가 정해졌을 때 비용은 $ (T_{k_1}) \times S_{k_2} + (T_{k_1}+T_{k_2}) \times S_{k_3} + … (T_{k_1}+T_{k_2}+…T_{k_{n_-1}}) \times S_{k_n} $ 이 됩니다. 여기서 $ i $ 번째와 $ i+1 $ 번째의 작업의 순서를 서로 바꾸는 시행에...
-
Data Forecast
Data Forecast contents What is Data Forecast? Basic Concepts what is STL Decomposition? Data Forecast methods conclusion What is Data Forecast? Data Forecast 란 무엇인가? 데이터 예측은 많은 경우에 필요하고 그 중요성 또한 크다고 할 수 있다. 만약 돌에 걸려 넘어지게 되었을 때, 그 결과를 예측해보면 쉽게 ‘다칠 것이다’라고 말할 수 있다. 하지만 자율주행 자동차를 제작한다고 생각해보자 자동차가 빠른속도로 다가오는 트럭을 상대로 미래를 예측해야 하는 상황이 생길 것이다. 관측 가능한 모든 데이터를 고려해보자 자동차의 현재...
-
On Factoring Given Any Bits
서론 이번에 Belluminar 라고 하는 대회에 참가했습니다. 해당 대회는 각 팀마다 문제를 두 개 씩 출제하고, 대회 시간 동안 문제를 풀면서 점수를 겨루는 방식으로 구성되어 있습니다. 저는 이번에 공부했던 테크닉을 문제로 내기로 결심해서 작성을 했는데, 생각보다 만족스러운 퀄리티로 문제가 나오지 않아 아쉬웠습니다. 본래라면 공부한 내용을 포스트로 바로 쓰겠지만, 제 이름이나 아이디를 검색해 그대로 솔버에 사용하는 것을 원치 않았기 때문에 이러한 소셜 해킹을 방지하기 위해서 이제서야 포스팅을 하게 되었습니다. 이번 포스트는 제가 냈던 문제의 근간이 되는...