[문자열] 문자열 패턴 매칭 문자열 패턴 매칭 패턴 매칭에 사용되는 알고리즘 고지식한 패턴 검색 알고리즘 ( 브루트 포스 ) : 하나씩 확인하는 고지식한 패턴으로 최악의 경우에는 모든 텍스트의 위치에서 패턴을 비교해야 하므로 시간 복잡도가 O(MN)이다. 라빈-카프 알고리즘 : 문자열 검색을 위해 해시 값 함수를 이용하는 방식, 최악의 경우 시간 복잡도가 O(MN)이지만 평균적으로는 선형에 가까운 속도를 가진다. 해쉬값을 구하는 과정에서 일정 자리수가 넘어가게 되면 MOD연산을 통해 자리수를 줄이게 된다. -> 해시 충돌이 발생할 수 있다. 보이어-무어 알고리즘 : 끝까지 비교해서 틀리는 경우를 방지하기 위해 오른쪽에서 왼쪽으로 비교 최악의 시간 복잡도는 O(MN)이지만 최선의 시간 복잡도는 O(N/M)으로 평균적으로 가장 빠른 속.. 2021. 4. 6. [Graph] 최단 경로 최단 경로 최단 경로 : 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로 하나의 시작 정점에서 끝 정점까지의 최단 경로→ 벨만-포드(Bellman-Ford) 알고리즘 : 음의 가중치를 허용 → 다익스트라(dijkstra) 알고리즘 : 음의 가중치를 허용하지 않음 모든 정점들에 대한 최단 경로 : 플로이드-워샬(Floyd-Warshall) 알고리즘 Dijkstra 알고리즘 ( 다익스트라 알고리즘 - O(E log V)) 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 매우 유사 우선순위 큐를 사용하여 효과적으로 최소 간선을 찾아 낼 수 있다. (입력 : O(log V), 출력.. 2021. 3. 30. [Graph] 최소 신장 트리(MST) 최소 신장 트리(MST) 그래프에서 최소 비용 문제 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 두 정점 사이의 최소 비용의 경로 찾기 신장 트리 n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리(Minimun Spaning Tree) 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 KRUSKAL 알고리즘 (크루스칼 알고리즘 - O(E log V)) 간선을 하나씩 선택해서 MST를 찾는 알고리즘 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가 시킴. → 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택 n-1개의 간선이 선택될 때까지 2를.. 2021. 3. 29. [Graph] 서로소 집합 서로소 집합 서로소 또는 상호 배타 집합들은 서로 중복 포함된 원소가 없는 집합 ( 교집합이 없다 ) 집합에 속한 하나의 특정 멤버를 통해 각 집합을 구분 ( 대표자 ) 서로소를 표현하는 방법 연결리스트 트리 ( 사용하기 가장 편함 → 많이들 사용함 ) 서로소 집합 연산 Make-Set(x) : 먼저 각각 자신만을 원소로 갖는 집합을 구성하는 Method Find-Set(x) : 해당 Parameter의 대표자를 찾는 Method Union-Set(x, y) : 해당 파라미터의 집합이 다를 경우에 두 집합을 합침 → 같은 집합인지 확인하기 위해서 Find-Set(x), Find-Set(y)를 호출 서로소 집합 표현 연결 리스트 같은 집합의 원소들은 하나의 연결리스트로 관리 연결 리스트의 맨 앞의 원소를 .. 2021. 3. 26. [Graph] Graph 탐색 그래프 탐색(순회) 그래프 순회는 비선형구조인 그래프로 표현된 모든 자료(정점)를 빠짐없이 탐색하는 것을 의미→ 깊이 우선 탐색 (Depth First Search, DFS) → 너비 우선 탐색 (Breadth First Search, BFS) 너비 우선 탐색(BFS) 너비 우선 탐색은 탐색 시작점의 인접한 정점들을 먼저 차례로 방문한 후, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비 우선 탐색을 진행해야 하므로, 선입선출 형태의 자료규조인 큐를 사용 BFS(G, v) // 그래프 G, 탐색 시작 정점 v 큐 생성 시작 정점 v를 큐에 삽입 정점 v를 방문한 것으로 표시 while(큐가 비어있지 않은 경우){ t = 큐.. 2021. 3. 25. [Graph] Graph 이론 그래프 그래프는 아이템(사물 또는 추상적 개념)드로가 이들 사이의 연결 관계를 표현한다. 정점(Vertex) : 그래프의 구성요소로 하나의 연결점 간선(Edge) : 두 정점을 연결하는 선 차수(Degree) : 정점에 연결된 간선의 수 그래프는 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조 V : 정점의 개수, E : 그래프에 포함된 간선의 개수 V개의 정점을 가지는 그래프는 최대 V*(V-1)/2 개의 간선이 가능 선형 자료구조나 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하기에 용이하다. 그래프 유형 무향 그래프(Undirected Graph) 유향 그래프(Directed Graph) 가중치 그래프(Weighted Graph).. 2021. 3. 24. 이전 1 다음
