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; }

다익스트라 알고리즘 최단 경로를 구하는 알고리즘 임의의 시작 정점에서 각각의 정점으로의 최단 경로를 구해낸다. 프림 알고리즘과 유사하다. 프림 알고리즘과 같이 그리디 알고리즘 기반이다. 전체적인 흐름은 시작 정점을 지정하고 해당 정점으로 가는 간선을 우선순위 큐에 넣는다. 이 간선은 시작을 나타내는 간선으로 가중치는 0이고 출발지는 -1로 한다. 우선순위 큐가 빌때까지 반복 { 우큐에서 하나 뺌 우큐에서 하나 삭제 해당 간선이 방문했을 경우 다음 반복 해당 간선 방문으로 표시 그래프를 모두 확인하여 시작 정점에 붙은 간선을 확인하여 거리가 현재 가중치보다 높게 저장된 간선을 현재 가중치로 계산하여 저장 후 우큐에 삽입 } 말로 보면 좀 힘들고 코드로 보는게 편할듯 하다.. int calDistance(i..

알고리즘을 하면서 포인터는 많이 익숙해졌는데 다익스트라 알고리즘을 공부하면서 버그를 수정하다 다른 예제 코드에서 다음과 같은 부분을 확인했다. void dijkstra(vector& graph, int start) void dijkstra(vector* graph, int start) 일반적으로 나는 포인터를 사용하고있었는데 & 를 사용하고있었다. 포인터는 해당 변수의 주소를 또 다른 변수에 저장하는거고 참조는 해당 변수의 또 다른 변수를 복제하는 느낌인거같다. alias 처럼 참고 - https://dayday-kim.tistory.com/5 참조변수와 포인터변수의 차이 [1] 레퍼런스와 포인터 : 이 둘은 분명 다른 개념이다. ⓐ : 포인터 포인터 변수를 설명하기 위해서, C의 이 예제를 가지고 와 ..

최소신장트리를 만드는 알고리즘으로 크루스칼 알고리즘이 있다. 개념자체는 단순하다. 그래프의 모든 간선을 가중치의 순서대로 이어 붙인다. 그렇다면 중복되는 간선은 어떻게 걸러내야 할지 고민하게 된다. 이 방법은 집합 개념을 도입하여 해결한다. 만약 최소 가중치의 간선을 최소신장트리에 포함하려 할 경우를 생각해 본다. 처음에는 아무도 집합을 이루지 않기에 바로 최소신장트리에 포함된다. 하지만 계속 반복되면 같은 집합 내에서 간선이 선택될 경우가 발생한다. 이는 순환을 발생시키므로 위와 같은 상황을 제외하면 최소신장트리가 완성된다. vector set; int findParent(vector set, int child) { int parent = set[child]; while (parent != child)..

프림알고리즘을 구현하려고 꽤 많은 시간을 사용했다. 그래프 구조라는 것에 대해 고민이 많았졌는데 에초에 구조라는게 그냥 데이터를 관리하기 위해 정해놓은 룰이기도하고 뭔가 자료구조에대해 굉장히 모호해지고 어려워졌다.... 어쨋든 프림 알고리즘은 그래프의 한 정점을 시작점으로 하여 가장 적은 가중치의 간선을 통해 탐색해 나가서 결국엔 최소의 가중치로 모든 정점을 그래프구조로 만들게된다. 이름은 최소신장트리 이지만 최소신장그래프도 가능한것이다. 그러면 크게 최소신장그래프를 저장하기위한 그래프를 선언하고 현재 가장 적은 가중치의 간선을 판단하기 위해 우선순위 큐를 사용한다. 그리고 전체적인 흐름은 다음과 같다. 우선순위 큐가 빌때까지 반복 { 우선순위 큐에서 간선 하나를 빼고 이미 방문한 정점이면 컨티뉴 간선의..

최소 신장 트리 란 간선에 가중치가 추가된 그래프 자료구조에서 한 정점에서 다른 정점으로 이동 경로가 가장 적은 가중치를 갖는 트리 대표적으로 프림 알고리즘, 크루스칼 알고리즘 두 개가 있다. 프림 알고리즘 - 간선이 많은 복잡한 그래프에 적합 임의의 정점을 최소신장트리에 삽입한다. -> 최소신장트리의 루트노드로 만듬 최소신장트리의 노드들을 체크하여 간선의 가중치가 최소값인 노드를 찾는다. 체크할 간선이 가르키는 노드는 최소신장트리에 있으면 안됨 찾은 노드를 최소신장트리에 추가한다. 우선순위 큐를 이용하여 탐색해야할 간선들을 관리하여 최소신장트리를 만들어갈 수 있다. 크루스칼 알고리즘 - 간선의 개수가 적은 경우 적합한 알고리즘 간선들의 가중치를 정렬한 뒤 최소신장 트리가 완성 될때 까지 간선을 작은 순..

Topological Sort 위상 정렬 비순환 방향 그래프 일 때 정렬가능하다. * DAG (Directed Acyclic Graph) - 사이클이 없는 방향 그래프 책에서는 DFS를 이용한 방법으로 구현하였다. 나는 이해가 잘 안되서 다른 사람들의 설명을 추가로 보았다. BFS, DFS, 진입 간선을 이용한 여러 방법이 있었는데 진입 간선을 이용한 방법이 제일 편했다. 구현 방향 그래프에서 진입 간선이 없는 정점을 큐에 추가한다. 큐에서 하나를 꺼내서 간선을 제거한다. 진입 간선이 없는 정점을 큐에 추가한다. 반복 void Graph::TopologicalSort() { int num = getVortexcnt(); ind.resize(num + 1, 0); VORTEX* temp = graph->V..