세그먼트 트리 (2) 썸네일형 리스트형 Randomize Binary Search Trees, Treap INTRO 잘 아려진 BBST(Balanced Binary Search Tree : 균형이진탐색트리)의 종류로는 rb tree, b tree 등이 있습니다. 그러나 위의 rb tree와 같이 대부분의 연산을 \(O(logN)\)에 처리하는 트리는 동작 자체도 복잡하고 구현량이 많기 때문에 직접 구현해가며 PS에 사용하기 어렵습니다. (stl에 있는 것을 가져다 쓰면 좋겠지만 연산을 변형해야하는 경우도 존재하니까요) 그래서 삽입, 삭제 등의 연산에 amortized \(O(logN)\)의 시간복잡도를 가지며 상대적으로 구현량이 적은 Splay Tree를 가장 많이 사용합니다. 하지만 Splay Tree도 zig-zag step 등 헷갈릴만한 요소가 많아서 저는 Treap을 선호합니다. Treap은 일반적인.. [BOJ 9576] 책 나눠주기 https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net Tag : greedy 문제요약 각 학생은 [a, b]에 있는 책을 하나씩 고를 수 있다. 책 한권은 한 사람만 고를 수 있다. 이 때 최대 매칭을 구하라. 풀이 이 문제를 처음봤을 땐 티어를 안보고 생각해서 이건 무조건 이분매칭 기본 문제다! 라고 생각했던 기억이 있네요. (http://boj.kr/2563bad26f364ee6aa5c04e9f97845b7 이분매칭 AC 코드) 정해로 돌아와서 생각.. 이전 1 다음
