hellogaon

KMP(Knuth Morris Pratt)는 문자열 검색 알고리즘입니다.길이가 H인 문자열에서 길이가 N인 문자열을 검색하고 싶을 경우완전탐색으로 보게 된다면 시간복잡도가 O(HN)이 되지만KMP는 O(H + N)만에 문자열을 검색하게 해주는 알고리즘입니다.기본적인 원리는 문자열을 검색하다가 일치하지 않는 부분이 나왔을 경우H의 다음 글자와 N의 처음부터 비교하는 것이 아닌지금까지 일치했던 부분의 접미사도 되고 접두사도 되는 문자열의 최대 길이만큼은 또 다시 일치하므로그 길이 이후부터 비교해 나가는 방식입니다.이 때, 접미사도 되고 접두사도 되는 문자열의 최대 길이를 저장해놓은 테이블을부분 일치 테이블이라고 부르는데 이를 구하는 방법 또한N에서 자신을 제외하고 N을 찾는 방법으로 구할 수 있기에비슷한 두..

트립(Treap)은 tree와 heap의 합성어로STL에서 제공하지 않는 기능이 필요할 때 이진 검색 트리(Binary Search Tree)를직접 간단하게 구현 할 수 있는 자료구조입니다.예를 들어 어떤 수보다 작은 원소의 수 또는 k번째 원소를 찾는 연산은 STL에서 지원이 되지 않기에관련한 기능이 필요할 경우 사용할 수 있습니다. 기본 문제 2465번: 줄 세우기

상호배타적 집합(Disjoint Set)은 유니온 파인드(Union Find) 자료구조로도 불리며어떤 두 부분집합 사이에도 교집합은 없고 모든 부분집합의 합집합은 전체 집합인 자료를 표현합니다.이 자료구조는 아래의 2가지 함수를 지원합니다. 1. find(u) : 노드 u가 속해있는 집합의 루트를 반환한다.2. merge(u, v) : 노드 u가 속해있는 집합과 노드 v가 속해있는 집합을 합친다. find함수로 find(u)와 find(v)의 값이 같다면 u와 v는 같은 집합, 다르다면 다른 집합에 있는 정보를 얻을 수 있으며다른 집합에 있을 경우 merge함수를 이용하여 두 집합을 합칠 수 있습니다.추후 그래프파트의 최소 스패닝 트리에서 이 자료구조를 사용하기에 알아두면 좋은 자료구조입니다. 기본 문제..