알고리즘/이론 (46) 썸네일형 리스트형 다중 문자열 검색, 아호-코라식 알고리즘 [1. 개요] 트라이를 활용하여 해결 할 수 있는 문제 중 하나로, 다중 문자열 검색 문제가 있다. 문자열 H 에서 여러 문자열(N) 의 출현위치를 모두 계산하는 문제 단순한 해결법은 KMP 알고리즘을 찾고자 하는 문자열 개수 만큼 반복하는 방법 그러나 이보다 더 빠르게 계산 할 수 있는 방법이 있다. 트라이에 포함된 문자열들이 접두사를 공유할 경우, 탐색 공간을 줄일 수 있다. 찾고자 하는 문자열들을 모두 트라이에 저장한 뒤, 이 트라이를 이용하여 모든 문자열을 한꺼번에 찾을 수 있다. 부분 매치 테이블 KMP 알고리즘 시, 전처리 되는 데이터 문자열 H의 어떤 시작위치 에서 찾고자하는 문자열과 matched 만큼 일치했을 때 각 접두사마다 이 접두사의 접두사도 되고, 접미사도 되는 문자열의 최대 길이.. 트라이 - 예제 [1. 문제 설명] https://algospot.com/judge/problem/read/SOLONG [2. 풀이 접근] [3. 코드] 문자열 - 트라이 [1. 개요] 트라이(trie) 는 문자열의 집하을 표현하는 트리 자료구조로 M 이 모든 문자열의 최대 길이일 때. 원하는 원소(문자열)를 O(M) 시간내에 찾을 수 있다. 트라이의 루트는 항상 길이 0인 문자열에 대응 되며 노드의 깊이가 깊어질 때마다 대응되는 문자열의 길이는 1 씩 늘어난다. 특성 종료 노드는 해당 위치에 대응되는 문자열이 트라이가 표현하는 집합에 포함되어 있다는 것을 의미한다. 루트에서 한 노드까지 내려가는 경로에서 만나는 글자들을 모으면 해당 노드에 대응되는 접두사를 얻는다. 각 노드에 대응되는 문자열을 저장하지 않는다. [2. 트라이 노드] 트라이 노드는 보통 다음과 같이 구성된다. 자손 노드를 가리키는 포인터 목록 => 입력에 등장 할 수 있는 모든 문자에 대응되는 원소를 갖는.. 접미사 배열 - 예제1 [1. 코드] 문자열 - 접미사 배열 [1. 개요] 접미사 배열은 굉장히 다양한 문자열 문제를 푸는 데 사용 할 수 있으며, 이 자료구조는 아래와 같은 데이터를 표현한다. 어떤 문자열 S 의 모든 접미사를 사전순으로 정렬 이때, 배열에 실제로 저장하는 것은 각 접미사의 시작 위치이다. 예를들어, A[i] = 7 일 때, S[7...] 을 표현하는 것이다. 그래서 이 자료구조를 이용하여 아래와 같은 문제를 해결 할 수 있다. 문자열 검색 찾고자 하는 "문자열 N" 이 "문자열 H" 의 어떤 접미사의 접두사라는 점을 이용한다. H 의 접미사 배열을 이진 탐색하여, 문자열 N 이 출현하는 위치를 찾을 수 있다. [2. 접미사 배열 생성] 접미사 배열을 생성하는 가장 단순한 방법의 시간복잡도는 O(n^2logn) 으로, 일반적인 경우에서는 이 보다.. 문자열 - kmp 알고리즘 [1. 개요] 문자열 검색 문제 문자열 H 가 문자열 N 을 부분 문자열로 포함하는지 확인 포함한다면, N 과 일치하는 부분 문자열의 시작 위치를 찾는 문제 N 이 H 에서 여러 번 출현한다면, N 이 출현하는 모든 위치를 반환해야 한다. 단순한 탐색 알고리즘의 경우 시간 복잡도는 O(|N| x |H|) 로, 입력되는 문자열의 길이가 매우 긴 경우(그리고 특정 형태의 입력에 대해서), 꽤나 비효율적인 알고리즘 이지만, 현실적인 경우에서 그런 경우는 흔하지 않다. KMP 알고리즘은 검색 과정에서 얻는 정보를 버리지 않고 활용하여, 동일한 문제에 대한 시간복잡도를 O(|N| + |H|) 로 상당히 개선할 수 있다. [2. 알고리즘 원리] KMP 알고리즘의 아래와 같은 특성을 이용한다. H[i...] 에서 N.. dfs-위상정렬 - 예제1 [3. 코드] Union-find - 예제1 [1. 문제 설명] 모순이 없는 경우, 한 파티에 올 수 있는 사람의 최대 수 (vim 파티, emacs 파티 중) [2. 풀이 접근] [3. 코드] 동적 계획법 - 예제5 [1. 문제 설명] [2. 풀이 접근] [3. 코드] 펜윅 트리 - 예제 1 [1. 문제 설명] [2. 풀이 접근] [3. 코드] 이전 1 2 3 4 5 다음
