자료구조

자료를 구조해라

자료구조, C언어, 백준

hash table을 구현해 보자

이제 학교에서 해우면서 PS에서 사용하는 자료구조 포스팅은 이게 아마 마지막일듯 싶다. Q. ??? 너는 학교에서 rb-tree도 안배움?? A. 배웠다. 근데 못짠다. 그리고 PS에서 실제 구현하는 사람이 있을까 싶다.... 우리는 map이 있자나!!!! 그리고 내가 rb-tree를 못짜고 map을 사용하는 방법도 모르기에 hash table을 구현해서 문제를 비벼오고 있다.

자료구조

Splay Tree

나는 야호다. 오늘은 Splay Tree에 대해 설명하겠다. Splay Tree는 무엇인가Splay Tree는 균형이진탐색트리(Balanced Binary Search Tree, BBST)의 한종류이다. Splay Tree라는 이름이 붙은 건 Splay라는 재밌고도 신기한 연산을 사용하여 amortized $$O(log n)$$의 시간복잡도를 유지하기 때문이다. 설명에 앞서 균형이진탐색트리에 대해 잠깐 알아보고 가자.

  • QCW-Yaho
자료구조

Persistent Segment Tree

다음과 같은 문제를 생각해보자. 크기가 N인 배열에서 주어지는 [l,r] 범위들의 합을 각각 구하여라. 어디서 본 것같지 않은가? 그렇다. hld 글을 시작했던 그 문제이다. 저 글에서 우리는 이 문제에 update를 얹고 배열을 트리형태로 바꾸었을 때 어떻게 처리해야할 지를 다루었는데 이번에는 문제를 약간 바꿔보겠다. 크기가

  • lovinix