Heavy-Light Decompostion(작성중)

Introduction

오늘은 HLD에 대해 포스팅을 해보려 한다. 문제 유형이 한정적이고 어려운 테크닉에 속하기에 포스팅할까 망설였다.(어디다 쓰는 알고리즘인데 도대체) 대회 준비를 하는 것도 아니기에 기본적인 자료구조, 알고리즘을 지향하려 했지만, 최근에는 굳이 그럴 필요 있을까 생각한다.

알고리즘은 기업 코테도 있다보니 겸사겸사 시작했지만, 요즘은 하나의 논리를 배우는 거라 생각한다. 우리는 개발을 하면서 언어에 대해 항상 문법만 배우지 말을 잘하는 법을 배우진 않는다. 논리적으로 말하지 않아도 의미만 잘 전달된다면 상관없을지도 모른다. 하지만, 직업 특성상 우리는 항상 효율적인 것을 생각한다. 논리를 배우는 건 필수적이지 않지만 달변가들이 많은 논리를 알고 있는 것은 어찌보면 당연하지 않을까?

서론이 길어졌다. 바로 알고리즘에 대해 알아보자.

Heavy-Light Decomposition

일반적인 그래프에서 정점 \(u\)에서 \(v\)로 가는 경로에 대한 문제는 풀기가 어렵고 제시할 수 있는 유형이 한정적이다. 트리에서 단순 경로는 반드시 하나 존재한다는 특성 떄문에 일반적인 경우에 비해 쉽게 접근할 수 있지만, 경로를 탐색하기 위해 트리 전체를 순회하는 결과를 야기한다. 또한, 정점이나 간선의 속성을 변경하는 작업일 경우엔 더욱이 효율적인 처리가 불가능에 가까워질 것이다.

이를 해결할 수 있는 방법 중 하나가 HLD다. HLD는 트리를 정점 단위가 아닌 chain단위로 분할하여 마치 1차원 배열의 묶음처럼 다룰 수 있게 해준다.

문제 정의

\(N\)개의 정점을 가진 트리가 있다고 하자. 이 때 임의의 두 정점에 대해 이들을 잇는 경로는 \(O(N)\)개의 간선을 가진다. Heavy light decomposition은 트리의 간선들을 적절히 일자 경로인 “묶음”들로 잘라, 임의의 두 간선 사이 경로를 \(O(\log N)\)개의 묶음으로 표현할 수 있게 해 준다. 이것을 세그먼트 트리 등의 일차원 자료 구조와 결합함으로써, 임의의 두 정점 사이의 경로에 대한 연산을 \(O(\log^2N)\)에 할 수 있다.

그런데 특별한 제약 조건이 없는 그래프 문제의 경우 이 모델화에 성공하면 대체로 문제가 쉬워지거나, 전형적인 알고리즘을 요구하는 문제로 바뀌게 됩니다. 오히려 제약 조건이 추가된 형태일수록 그 조건에 의해 나타나는 특성을 코어까지 활용해야 하는 어려운 문제를 자주 마주치게 됩니다.

1차원이라면?

알고스팟에서 이에 대한 기본적인 문제를 제공하지만, 나는 남극 탐험 - 2927 문제를 통해 예시를 풀어보려 한다.

Refernce

• http://theyearlyprophet.com/heavy-light-decomposition.html
• https://www.secmem.org/blog/2019/12/12/HLD/