'분류 전체보기' 카테고리의 글 목록 (11 Page)

본문 바로가기

[Algorithm] KMP 알고리즘 KMP 알고리즘 ? 전체 문자열 : 문자열 전체 패턴 문자열 : 찾고 싶은 문자열 전체 문자열에서 일치하는 패턴 문자열을 찾아야 할 때 사용 패턴 문자열이 여러 번 존재할 수 있고 각각 어디 위치인지 찾아야 할 때 접두사, 접미사의 개념을 활용하여 반복되는 연산을 줄이고 매칭 할 문자열의 위치로 빠르게 점프 전체 시간복잡도 O(n+m) : n = 전체 문자열의 길이, m = 패턴 문자열의 길이 O(n^2)의 문자열 탐색 방식을 사용한 경우라면 for ( int i =0; i < 전체 문자열의 길이; i++) { // text[i] : 전체 문자열 중 i 번째 문자 bool flag = true for ( int j =0; j < 패턴 문자열의 길이; j++ ) { // pattern[j] : 패턴 문자열..

[자료구조] Trie 트라이 Trie는 ? 저장된 문자열을 효과적으로 탐색할 수 있는 자료구조 트리 구조 시간 복잡도 O(N) : N은 문자열의 길이 prefix tree, radix tree, retrieval tree 등으로 부름 단점 : 거대한 공간 복잡도 trie는 문자열 탐색에 굉장히 유용한 자료구조이다 문자열이 주어지게되면 문자를 저장하는 노드를 하나씩 생성해가면서 트리구조를 만든다 자동으로 정렬된 효과를 볼수 있다는 장점도 있다 예시 root 노드는 가장 상위 노드를 의미한다 "ALCUK" "EZ" "EZYUN" "EZYOON" 4글자를 넣은 Trie 트리 모양 구현 - 간단한 기본 코드 #include #include #include using namespace std; const int ptr_num = 10; st..

2021년 새해 기념 보호되어 있는 글입니다.

이전 1 ··· 8 9 10 11 다음

티스토리툴바