자료구조 hash table을 구현해 보자 이제 학교에서 해우면서 PS에서 사용하는 자료구조 포스팅은 이게 아마 마지막일듯 싶다. Q. ??? 너는 학교에서 rb-tree도 안배움?? A. 배웠다. 근데 못짠다. 그리고 PS에서 실제 구현하는 사람이 있을까 싶다.... 우리는 map이 있자나!!!! 그리고 내가 rb-tree를 못짜고 map을 사용하는 방법도 모르기에 hash table을 구현해서 문제를 비벼오고 있다. Q. 이글에선 충돌 어떻게 처리할거임? A.
자료구조 stack을 구현해 보자 스.택.을.구.현.해.보.자 알지? 연결리스트로할꺼임ㅋ 코드부터 보자 그리고 당연한 이야기겠지만 마지막에는 문제를 통해서 아래 코드를 검증해 볼 것이다. struct node { int num; struct node * pre; }; struct node *f, *r; void push(int); struct node pop(); int isempty(); void push(int num) { struct node *temp; temp
자료구조 Splay Tree 나는 야호다. 오늘은 Splay Tree에 대해 설명하겠다. Splay Tree는 무엇인가 Splay Tree는 균형이진탐색트리(Balanced Binary Search Tree, BBST)의 한종류이다. Splay Tree라는 이름이 붙은 건 Splay라는 재밌고도 신기한 연산을 사용하여 amortized $$O(log n)$$의 시간복잡도를 유지하기 때문이다. 설명에 앞서 균형이진탐색트리에 대해 잠깐 알아보고 가자. 이진탐색트리는 특정 데이터의 삽입, 삭제,
자료구조 Persistent Segment Tree 다음과 같은 문제를 생각해보자. 크기가 N인 배열에서 주어지는 [l,r] 범위들의 합을 각각 구하여라. 어디서 본 것같지 않은가? 그렇다. hld 글을 시작했던 그 문제이다. 저 글에서 우리는 이 문제에 update를 얹고 배열을 트리형태로 바꾸었을 때 어떻게 처리해야할 지를 다루었는데 이번에는 문제를 약간 바꿔보겠다. 크기가 N인 배열에서 주어지는 [l,r] 범위의
자료구조 queue를 구현해 보자 큐가 뭔지 다 알것이라 생각한다. 바로 코드부터 보자 아 그전에 연결리스트로 구현 할 것이다. Q. 하... ㅆ ㅣ.. ㅂ...... A. ㅎㅎ;; ㅈㅅ.. ㅋㅋ!! struct node { int x, y; struct node* next; }; struct node* f, * r; void push(int, int); struct node pop(); void push(int x, int y) { struct node*
자료구조 priority_queue를 구현해 보자 사실 난 알고있는 알고리즘이 몇개 없다. 그래서 그나마 조금 할줄아는 구현글을 써보고자 한다. 사실 다른자료구조 부터 먼저 할려고 했지만 이 글이 나오자마자 우선 priority queue(이하 pq)부터 하고자 맘먹었다. pq는 매우 좋은 자료구조라 할 수 있다. 그 범용성도 매우 넓다. 예를들어 https://www.acmicpc.net/problem/1753 https://www.
알고리즘 Heavy Light Decomposition 다음과 같은 문제를 생각해보자. 크기가 N인 배열에서 주어지는 [l,r] 범위들의 합을 각각 구하여라. 이 글을 찾아올 정도의 사람이라면 아마 일일이 더하는 것이 아니라 누적합을 구해서 각 쿼리를 O(1)에 처리할 것이다. 저 배열에 단일점 업데이트가 있다면 세그먼트 트리를 쓸 것이고, 구간 업데이트가 있다면 Lazy propagation을 얹어서 쓸 것이고.
