Aif

https://yiyj1030.tistory.com/495 [알고리즘/ 파이썬] KMP 알고리즘 알아보기 KMP 알고리즘(Knuth-Morris-Pratt algorithm)이란 문자열 검색을 매우 빠르게 해주는 알고리즘이다. 특정 패턴이 주어졌을 때 전체 문자열을 빠르게 검색하여 그 패턴이 어디에 등장하는 지 찾아준다. KMP yiyj1030.tistory.com KMP 알고리즘을 구현하였는데 수정해야할 사항이 있었다. 사실 내가 구현한 코드는 KMP 알고리즘이라고 할 수 없다. 왜 그런지는 정확하게 설명할 수 없지만 KMP 알고리즘을 사용하지 않았다. KMP 알고리즘의 패턴 테이블을 참조하여 중복 건너뛰기만 한 느낌이다. 일단 KMP 알고리즘이 정확하게 이해되지 않는 부분이 접두부의 인덱스를 패턴 테..

KMP 알고리즘 >> 무식한 탐색 알고리즘의 개선 버전 만든사람의 앞글자를 따서 KMP 알고리즘이라 불림 김명표 Knuth, Morris, Pratt 무식한 탐색 알고리즘은 시간복잡도가 O( 텍스트 길이*패턴 길이 ) 로 상당히 느린데 KMP 알고리즘은 O ( 텍스트 길이 + 패턴 길이 )로 굉장히 효율이 좋아짐 성능이 좋은 알고리즘에 속하지만 대부분의 프로그램은 보이어 무어 알고리즘을 채택하고 있다고 한다. 또한 살짝 다른 기능인 자동완성 기능에서는 트라이 자료구조를 사용하여 데이터를 관리하여 보다 빠르게 탐색을 완료한다고 함. 구현 방법 >> KMP 알고리즘은 무식한 탐색 알고리즘에서 중복된 부분을 건너 뛰어서 탐색하여 성능을 향상시킨다. 이미 탐색한 부분을 건너 뛰는 건 당연한 일이다. 하지만 여기..

카프라빈 알고리즘은 찾고 싶은 문자열과 비교할 타깃 문자열을 해쉬 하여 비교하는 알고리즘이다. 같은 문자를 해쉬하면 같은 값이 나오는 원리를 이용한 것이다. 여기서 중요한 것은 해쉬를 하면 연산이 늘어나서 결국 고지식한 알고리즘과 다를 게 없지 않을까 했는데 그렇지 않다. 그 이유는 카프 라빈은 천재이고, 이 사람들은 해쉬 연산을 최적화하여 속도를 더 올렸다고 한다. 그 방법은 타겟 문자열을 해쉬해 나갈 때, 첫 문자와 마지막 문자만 변하는 형식일 것이다. 여기서 중복되는 가운데 문자열의 해쉬 연산을 줄여서 속도를 올린다. 이러한 해쉬시 알고리즘을 롤링 해시라고 한다. 원리는 기존의 문자열을 패턴길이만큼 해시하여 비교할 때, 다음 해시해야하는 문자열이 이전의 해시값으로 나타내진다. 사실상 롤링 해시를 통..

가장 먼저 떠오르는 문자열 탐색 알고리즘 탐색할 문자열을 타겟 문자열에 하나하나 대입하여 모두 일치할때 까지 돌린다. vector forceSearch(string p, string T) { vector find; for (int i = 0; i < T.size() - p.size(); i++) { for (int j = 0; j < p.size(); j++) { if (p[j] != T[i+j]) { break; } if (j+1 == p.size()) { find.push_back(i); } } } return find; }

그래프의 순회는 그래프의 모든 정점을 방문하여 데이터를 확인하는 알고리즘이다. BFS - 넓이 우선 탐색 DFS - 깊이 우선 탐색 두 가지가 있으며 다양한 알고리즘에 활용되는 기본 연산 느낌이다. 막상 처음 접하면 어렵지만 배우고 나면 쉬운 개념의 알고리즘이다. 처음엔 그래프 구조와 큐를 사용한다는 점을 떠올리지 못해서 어려웠던 것 같다. BFS 그래프 정점에 방문했을 때, 간선이 방문하지 않은 정점을 가르키면 큐에 넣는다. 큐에 넣을 때, 방문을 한 것으로 간주하고 큐에 넣는다. 방문한 정점은 방문했다고 표시 >> 안해도 될듯 큐에서 정점 하나를 꺼내서 위의 과정을 반복 큐가 비면 종료 void Graph::BFS(VORTEX* visit) { EDGE* temp = visit->Ehead; VORT..

레드 블랙 트리의 삭제 연산은 이진 탐색 트리의 삭제와 동일한 연산 과정에 삭제할 노드의 색깔에 따라서 몇 가지 연산을 수행해준다. 나는 이진 탐색 트리의 연산에서 삭제할 노드의 자식이 두개인 경우 삭제할 노드 삭제 >> 왼쪽 자식 중 가장 큰 값의 노드를 삭제한 노드의 자리로 옮김 으로 구현하였다. 이 부분을 살짝 수정해야한다. 왼쪽 자식 중 가장 큰 값의 노드의 데이터를 삭제할 노드의 데이터로 덮어씌움 >> 삭제할 노드를 왼쪽 자식 중 가장 큰 값의 노드를 가르키게함 으로 삭제할 노드를 바꿔주게 했다. 이유는 삽입 연산과 비슷하게 삭제 연산에서도 삭제할 노드의 형제 노드를 확인하는데 루트 노드의 경우 형제 노드가 없다. 그래서 바꿔서 구현했다. 그럼 삭제할 노드를 구했다면 몇가지 체크를 하게된다. 1..

레드 블랙 트리는 삽입과 삭제가 주된 연산이다. 레드 블랙 트리의 삽입 연산은 기본적으로 이진 트리의 연산 방식을 따른다. 이후 레드 블랙 트리의 규칙을 준수하고있는지 체크하는 알고리즘에 의해 자체적으로 밸런싱 작업을 수행한다. 삽입 연산은 이진 트리에서 처럼 null이 나올때 까지 데이터의 크기를 비교하며 알맞은 노드의 자리를 찾아낸다. 여기서 다른 점은 레드 블랙 트리는 null이 아니라 nil 이라는 특수한 노드를 가르키는 곳이 마지막 노드이다. 새로운 노드가 들어갈 자리를 찾았으면 전체 트리를 검사해야한다. 이때 새로운 노드는 항상 레드 노드이다. 블랙 노드를 추가하는 방법도 있겠지만 레드 노드를 추가하는 것이 더 편리할 것이라 생각된다. 레드 노드를 추가하면 부모가 레드 노드인지만 확인하면 되기..

레드 블랙 트리의 연산을 수월하게 하기 위한 연산인 회전에 대해 설명하려한다. 회전 연산은 우회전과 좌회전이 있다. 우회전을 예로 들면 우선 타겟 노드를 정한다. 타겟 노드를 기준으로 왼쪽 자식의 오른쪽 자식 노드를 타겟 노드의 왼쪽 자식을 가르키게 한다. target->left = target->left->right; 그리고 빈 자리가 된 왼쪽 자식의 오른쪽 자식은 타겟 노드를 가르킨다. target->left->right = target; 여기서 위 두 코드를 연속으로 실행하면 당연히 제대로 작동하지 않는다. 그 이유는 타겟의 왼쪽이 이미 바뀌기 때문에 별도의 노드를 선언해서 수행해야한다. NODE* temp = nullptr; temp = target->left; // 타겟 왼쪽 노드 주소 targ..

레드 블랙 트리란 이진 탐색 트리의 단점인 균형을 유지할 수 없는 부분을 보완한 트리이다. 이렇게 이진 탐색 트리의 단점을 보완하여 균형을 유지하는 트리를 밸런싱 트리라고 한다. AVL 트리 와 Red-Black 트리가 대표적이다. 레드 블랙 트리의 구현 레드 블랙 트리는 노드에 레드와 블랙이라는 개념이 추가된다 struct NODE { int data; struct NODE* left; struct NODE* right; struct NODE* parent; // 0 : 레드 / 1 : 블랙 / 2 : 이중 블랙 int black; }; 나는 위와 같이 black라는 변수로 나타냈다. 그리고 원래의 트리에서는 마지막 노드의 left right는 자식 노드가 없으므로 nullptr 이지만, 레드 블랙 트..

이진 트리의 탐색 방법으로는 전위 중위 후위 3가지 방법이 있다. 전위는 뿌리부터 왼쪽으로 타고 내려가면서 출력한 뒤, 왼쪽이 없으면 부모노드로 돌아가 오른쪽노드를 출력하게 된다. 중위는 왼쪽 아래부터 출력한 뒤 부모 노드 > 오른쪽 노드 출력을 반복하게 된다. 후위는 왼쪽 아래부터 출력한 뒤 오른쪽 형제 노드를 출력하고 부모노드를 출력하게 된다. 글로 보면 이해가 힘들지만 코드를 보면 간단하게 이해 가능하다. void BinaryTree::print1(Node* temp) { if (!temp) return; std::cout Data left); print1(temp->right); } void BinaryTree::print2(Node* temp) { if (!temp) return; print2(..