복습용 블로그

KMP 알고리즘은 ctrl + F 와 같이 긴 문자열에서 특정 패턴을 찾을 때 사용되는 알고리즘이다.  단순히 하나씩 검색 시, 검색 대상 문자열 길이가 N, 검색 패턴 길이가 M일 때 O(NM) 이 소요되지만, KMP를 이용 시 O(N+M)이 소요된다.  KMP 알고리즘은 다음과 같이 동작한다. - 실패 함수를 통해 패턴의 prefix와 suffix의 일치하는 최대 길이를 계산- 계산된 실패함수를 바탕으로 패턴 매칭 실패 시 suffix 위치로 이동 실패 함수 (아래에서 pi 함수)ababaabbabab 와 같은 패턴이 있을 때, prefix와 suffix의 공통 최대 길이를 구하는 함수이다. ababaabbabab의 경우, abab / aabb / abab 와 같이 prefix와 suffix의 공통 ..

Trie 자료구조는 Tree와 유사하지만, element 개별로 트리를 구성하는 것이 아닌, 공통 prefix를 기준으로 tree를 구성한다.  대표적인 Trie 예시는 string 간의 공통 substring 검색, 검색엔진에서 검색어 유무 확인, 이더리움의 state 저장에 사용되는 merkle patricia trie 등이 있다. Trie 예시 : 알파벳 소문자로만 이루어진 경우 입력 : apple, app, banana, bbb, ccc, cat  root를 기준으로 새로운 문자열 삽입 시, char 단위로 null이 아닌 곳을 따라 가다가 null 인 지점을 만나게 되면 해당 노드부터 한 글자씩 노드를 추가로 생성하면 된다.  입력된 문자열이 Trie에 존재하는 지 여부의 경우, 마찬가지로 Tr..

KD Tree : 일반적인 바이너리 트리를 k 차원으로 확장한 트리 데이터 타입이 n 차원 벡터일 때 (x1, ..., xn)x1을 기준으로 트리 구성, x2를 기준으로 트리 구성, ..., xn을 기준으로 트리 구성, x1을 기준으로 트리 구성, ... 을 반복하여 트리를 만드는 것 ex) 2차원에 대한 KD Tree 만들기input : (5, 3), (5, 4), (3, 9), (4, 6), (6, 2), (1, 1), (4, 1), (6, 7)root : (5, 3)left child : xi 차원의 값을 기준으로 작은 것, right child : xi 차원의 값을 기준으로 이상인 것  위와 같이 차원을 분리하여 각 차원에 대한 대소 비교를 통해 트리를 구성하는 것이 KD Tree  KD Tree..

C++의 STL에는 vector와 queue 등 아주 좋은 친구들이 많다. 그 중 PS 에서 많이 쓰는 vector와 priority_queue 의 정렬 기능에 대해 정리하고자 한다. 1. vector algorithm STL 을 이용해 sort 함수로 vector를 쉽게 정렬할 수 있다. (단순 배열도 가능) sort(vec.begin(), vec.end()) 가 기본 사용법이며, vec의 처음부터 끝까지를 기본적으로 오름차순으로 정렬한다. 역순 정렬을 하고자 하면 sort(vec.rbegin(), vec.rend()) 와 같이 사용 가능하다. 하지만 이는 int, float, pair 등 기본 타입에만 적용이 된다. 따라서 operator 가 정의되지 않은 데이터 타입 (struct 로 직접 만든 데..

MST (Minimum Spanning Tree, 최소 신장 트리) 는 그래프에서 전체 가중치 합이 최소가 되도록 만든 트리입니다. MST를 구하는 방식으로는 크루스칼 알고리즘, 프림 알고리즘이 있습니다. 크루스칼 알고리즘은 모든 edge를 정렬 후, 가중치 순으로 하나씩 이어보며, 사이클이 발생하면 다음 엣지를 대상으로 검사하는 방식입니다. 그러므로 복잡도는 정렬 시 사용되는 O(E log E) 입니다. 프림 알고리즘은 아무 노드를 시작점으로 해당 노드로부터 가장 가까운 노드를 이어나가는 것을 반복합니다. 이 때, 선택된 다음 노드와 연결된 노드와 시작점 노드 간의 거리를 업데이트하며, 다음 가까운 노드 선택 시 해당 거리를 기준으로 선택합니다. 프림 알고리즘의 경우, 가장 가까운 노드를 찾는다의 기준..