2018. 10. 11. 19:07ㆍCS 이론/자료구조
PS를 하면서 Persistent라는 단어가 붙는 자료구조는 Persistent Segment Tree 외에는 보기 힘들지만, 사실 Persistent라는 prefix는 꽤나 일반적인 의미를 지닌다.
어떤 자료구조를 계속 업데이트하면서도 이전 버전에 접근할 수 있을 때 그 자료구조를 'Persistent하다'고 한다. 조금 더 세부적으로 분류하면, 이전의 모든 버전에 접근, 수정이 가능하다면 Fully persistent, 이전의 모든 버전에 접근이 가능하지만 최종 상태를 제외하면 모두 read - only라면 Partially persistent 혹은 Confluently persistent라고 한다.
분류는 거창하지만 구현이 그렇게 난해한 건 아니다. 일반적인 방법론은 Fat node, Path copying, A combination 등이 있는 모양이지만... 방법론에 갇힌 사고를 하지 않기로 했기 때문에 옮겨적지는 않겠다. 위키피디아에 보면 엄청 길게 설명되어 있다.
결국 'Persistency'가 필요한 이유는 자료구조의 k번째 state에 빠르게 접근하기 위함이기 때문에 persistent DS는 online 알고리즘에서 사용하게 되고, 때문에 거의 모든 persistent 자료구조에는 대응되는 offline 알고리즘이 있다. 가장 대표적으로는 직사각형 쿼리에서 PST를 사용하는 방법과 x좌표 기준으로 쿼리를 정렬하는 방법의 대조가 있다.
PS에서 'persistency'를 활용하라고 낸 문제들은 다음과 같다. 스포가 포함되어 있으니 주의하자.
'CS 이론 > 자료구조' 카테고리의 다른 글
| ???한 자료구조, 알고리즘 모음 (4) | 2018.09.09 |
|---|