Problem Solving/Data Structure7 해싱(Hashing) 1. 개요 해싱(Hashing)은 긴 길이의 문자열이나 큰 크기의 값을 어떤 작은 값으로 치환하는 방법이다. 특히 문자열 관련 문제에서 강력한 힘을 발휘하며, 본 글에서 소개할 방법에 따르면, 구현이 간단할 뿐만 아니라 해싱 충돌이 발생할 확률이 매우 낮기 때문에(충돌이 나지 않는다고 가정) 실제 대회에서 자주 사용된다. 2. 구현 dad라는 단어가 있다고 생각하자. 이 단어를 하나의 정수로 치환하려고 한다. 기본적인 아이디어는 "문자의 종류" 진법으로 생각하여 정수로 치환하는 것이다. 'a'는 1, 'b'는 1, … , 'z'는 26으로 생각하자. dad는 아래처럼 하나의 값으로 표현할 수 있다. 'a'를 0부터 취급하지 않는 이유는 "a"와 "aaa"를 구분하지 못함에 있다. 아래의 코드는 하나의 문.. 2020. 8. 7. C++ [STL] vector 구현 1. 정의 구현하고자 하는 자료형 vector를 아래와 같이 정의해보자. A : 값을 저장하는 일차원 배열이다. 배열의 index는 0부터 시작하며, 배열의 최대 크기는 max_size이다. 따라서 A[0]부터 A[max_size-1]까지 총 max_size개의 값을 저장할 수 있다. size : 현재 배열 A에 저장되어 있는 값의 개수를 나타낸다. 따라서 A[0]부터 A[size-1]까지 값이 저장되어 있다. max_size : 배열 A가 최대로 저장할 수 있는 값의 개수를 나타낸다. vector에 값을 추가하다보니, size가 max_size보다 더 커지는 경우를 살펴보자. 다섯번째 값을 추가하고 싶지만, A의 크기가 충분하지 않은 상태이다. 이와 같을 때에는 아래의 과정을 따른다. 1) 기존의 A .. 2020. 8. 5. Heavy Light Decomposition N개의 정점을 가진 트리가 있다고 하자. 이 때 임의의 두 정점에 대해 이들을 잇는 경로는 O(N)개의 간선을 가진다. Heavy light decomposition(HLD)은 트리의 간선들을 적절히 일자 경로인 “묶음”들로 잘라, 임의의 두 간선 사이 경로를 O(lg N)개의 묶음으로 표현할 수 있게 해 준다. 이것을 세그먼트 트리 등의 일차원 자료 구조와 결합함으로써, 임의의 두 정점 사이의 경로에 대한 연산을 O(lg2N)에 할 수 있다. 간선들을 묶음으로 잘 나누는 방법은 다음과 같다. 1. 임의의 정점을 루트(R)로 지정하여, DFS 탐색을 한다. DFS 탐색을 하면서 각 정점에 대해 다음의 2가지를 계산한다. 1) 루트 노드와의 거리 2) 해당 정점이 루트 노드인 subtree의 크기 2. R.. 2018. 2. 15. Rope 튜토리얼 문서 원본 Rope는 scalable string implementation이다: 문자열에 대한 연산들 중 몇 개에 대해서 강력한 성능을 제공한다. 할당(assignment), 연결(concatenation), 그리고 부분문자열(substring)에 해당하는 연산들은 문자열의 길이와 거의 독립적으로 빠르게 수행된다. Rope는 문자들의 Container로 취급되며, 거의 Sequence이다. 각각의 원소를 수정하는 연산은 느리다. vector 또는 string과 비교해 장점과 단점을 비교해보자.장점: 1. Much faster concatenation and substring operations involving long strings. 2. Potentially much better space.. 2017. 1. 19. Persistent Segment Tree 들어가기 이전에 다음 글이 해당 자료구조에 대해 영어로 잘 설명해 놓았다. Persistent Segment Tree를 이용하는 문제로 BOJ 11932 트리와 K번째 수 문제가 있다. 노드의 개수가 N개이고, 각 정점마다 가중치가 있는 트리가 있을 때에 M개의 쿼리에 대해 두 노드 사이를 잇는 경로 상의 K번째 정점 가중치 값을 출력하는 문제이다. 편의를 위해서 가중치들은 다 좌표압축을 하여 1에서부터 N까지의 값만 가진다고 가정하자. 한 쿼리에 대해서 답을 이분탐색하면서 정한 답을 Ans라고 한다면, 두 정점 u와 v 사이를 잇는 경로에 Ans보다 작거나 같은 원소의 개수를 counting해서 그 개수가 K보다 크다면 Ans를 줄이고, K보다 작으면 Ans를 늘이면 된다. 답을 정하는 데에 O(log.. 2016. 6. 14. 이전 1 2 다음
