탐색

KMP (문자열 중 특정 패턴을 찾아내는 탐색) 알고리즘 C++ 구현

개념 KMP 알고리즘은 문자열에서 특정 패턴을 효율적으로 찾을 수 있다. 살펴볼 문자열의 길이가 N, 찾고 싶은 패턴의 길이가 M이라면 O(N+M)의 시간 복잡도를 가지는 매우 효율적인 알고리즘이다. KMP 알고리즘이 얼마나 효율적인지 알기 전에, 모든 문자열을 일일이 비교하는 경우를 살펴보자. 모든 문자열을 일일이 비교하는 경우(브루트 포스 : Brute Force) "ABCDABCE"라는 문자열에서 "ABCE"라는 패턴을 찾는다고 해보자. 모든 문자열을 일일이 비교한 경우엔 아래와 같이 탐색을 진행할 것이다. 이처럼 모든 문자열을 비교하는 브루트 포스(Brute Force) 방식은 텍스트의 길이를 N, 찾고자 하는 패턴의 길이를 M이라고 했을 때 시간 복잡도가 O(NM)이다. 이는 매우 비효율적이다...

SPFA (Shortest Path Faster Algorithm)

개념) 다익스트라 알고리즘은 O(ElogV)로 동작하며 (이론적으로는 O(E+VlogV) 음수 간선은 처리할 수 없다. 일반적으로 가장 많이 사용된다. 플로이드-와셜 알고리즘은 O(V3)으로 동작하며, 모든 정점들간의 거리를 모두 구한다는 특징이 있다. 음수 간선이 있어도 잘 동작하며 음수 사이클의 여부를 판단할 수 있다. 벨만-포드 알고리즘은 O(VE)이며 음수 간선이 있어도 잘 동작하고, 음수 사이클의 여부를 판단할 수 있다. 이제 SPFA 알고리즘에 대해 알아보자. SPFA 알고리즘은 벨만-포드 알고리즘의 성능을 향상시킨 것으로, 음수 간선이 있는 그래프에서 최단경로를 빠르게 구할 수 있다. 최악의 시간복잡도는 여전히 O(VE)이지만 실제로는 O(V+E) 정도로 동작한다. 벨만-포드 알고리즘에서는 ..

C++ 그래프를 이용한 BFS / DFS 계속 업데이트할 예정

출처 : https://www.youtube.com/watch?v=tWVWeAqZ0WU 첫번째 문제 #include #include #include #include #include using namespace std; #define TOTAL_SIZE 1000 #define y first #define x second vector graph[TOTAL_SIZE]; bool visited[TOTAL_SIZE]{ false }; int edge = 0; void DFS(int _start) { cout

[C] 이진 탐색 트리

이진탐색트리(Binary Search Tree)이란? 이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다. ( #이진트리 - 각 노드의 자식 노드가 최대 2개인 트리) 1. 각 노드에 중복되지 않는 키(key)가 있다. 2. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다. 3. 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다. 4. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다. 이진 탐색 트리의 특징 이진 탐색 트리는 기존 이진트리보다 탐색이 빠르다. 이진 탐색 트리의 탐색 연산은 트리의 높이(height)가 h라면 O(h)의 시간 복잡도를 갖는다. 이진 탐색 트리 탐색(Search) 이진 탐색 트리의 탐색은 다음과..