티스토리

Note. Hongjun Jang

검색하기

블로그 홈

Note. Hongjun Jang

hongjun7.tistory.com/m

Competitive Programming, Machine Learning

구독자: 22

방명록 방문하기

주요 글 목록

해싱(Hashing) 1. 개요 해싱(Hashing)은 긴 길이의 문자열이나 큰 크기의 값을 어떤 작은 값으로 치환하는 방법이다. 특히 문자열 관련 문제에서 강력한 힘을 발휘하며, 본 글에서 소개할 방법에 따르면, 구현이 간단할 뿐만 아니라 해싱 충돌이 발생할 확률이 매우 낮기 때문에(충돌이 나지 않는다고 가정) 실제 대회에서 자주 사용된다. 2. 구현 dad라는 단어가 있다고 생각하자. 이 단어를 하나의 정수로 치환하려고 한다. 기본적인 아이디어는 "문자의 종류" 진법으로 생각하여 정수로 치환하는 것이다. 'a'는 1, 'b'는 1, … , 'z'는 26으로 생각하자. dad는 아래처럼 하나의 값으로 표현할 수 있다. 'a'를 0부터 취급하지 않는 이유는 "a"와 "aaa"를 구분하지 못함에 있다. 아래의 코드는 하나의 문.. 공감수 2 댓글수 5 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 .. 공감수 3 댓글수 1 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.. 공감수 0 댓글수 2 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.. 공감수 0 댓글수 0 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.. 공감수 3 댓글수 1 2016. 6. 14.
트리에서의 Sqrt Decomposition 1) 트리에서 branch를 나눔2) branch를 나누는 기준은 현재 정점에서 자식 노드들이 여럿일 때, 첫 번째 branch는 부모와 x를 잇는 branch와 같다고 하고, 나머지들은 각각 새로운 branch.3) 현재 branch의 길이가 이상이면 cut.그림으로 표현하면 대충 이런 식이 된다.dfs numbering하면서 branch를 나누는 코드는 아래와 같다.cn : branch number, bc : branch에 포함된 노드의 개수, col[x] : x 노드의 branch indexy라는 노드에서 x라는 노드로 올라가면서 일련의 작업을 하는 코드는 아래와 같다. 붉은색 부분에는 branch 전반에 대한 작업, 푸른색 부분에는 특정 노드에 대한 작업을 해주면 된다. 이 코드는 노드와 부모 노.. 공감수 0 댓글수 0 2016. 5. 19.
Persistent Segment Tree 1. SPOJ 'COT - Count on a tree'2. SPOJ 'MKTHNUM - K-th Number'3. Codeforces Round #140 (Div. 1) Problem E. Noble Knight's Path 공감수 0 댓글수 0 2016. 2. 25.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.