공부/알고리즘3 Boyer & Moore Algorithm (보이어&무어 알고리즘) 문자열 패턴을 찾는 알고리즘 Naive Algorithm : 가장 쉽게 생각할 수 있는, O(N^2)의 전체 탐색 알고리즘이다.(Brute-Force Algorithm) Rabin & Karp Algorithm : 해시를 이용한 문자열 탐색 알고리즘이다. Boyer & Moore Algorithm : 일반적으로 가장 빠른 알고리즘이다. Suffix Tree / Array : 접미사 트리/배열이라고 불리는 테이블을 이용한 알고리즘이다. KMP : Knuth, Morris, Prett 3명이서 만든 알고리즘으로, 접두사와 접미사를 이용해서 패턴을 찾는다. 위의 5개 중에서 이번에는 Boyer & Moore Algorithm에 대해서 정리해보고자 한다. KMP 알고리즘의 개선판이라고 할 수 있다. Worst .. 2021. 11. 16. 플로이드 와샬 (Floyd-Warshall) 알고리즘 이번에는 플로이드 와샬 알고리즘에 대해서 공부를 해보았다. 지난번 다익스트라 알고리즘에 이어서 최단거리와 관련된 알고리즘이다. 다익스트라는 하나의 정점에서 출발했을 때, 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이었다면, 플로이드 와샬은 '모든 정점'에서 '모든 정점'으로의 최단 경로를 구해야할때, 플로이드 와샬을 사용해야 한다. 플로이드 와샬 알고리즘의 핵심 아이디어는 '거쳐가는 정점'을 기준으로 최단거리를 구하는 것이라고 보면 된다. 1 , 2, 3, 4의 총 4개의 노드를 가진 그래프가 있다. 이를 바탕으로 플로이드 와샬을 그려보면 초기 그래프에 대한 표를 작성할 수 있고, 그 다음을 차례대로 노드1만 거치는 경우 부터 노드4만 거치는 경우를 따져가면서 값을 업데이트하면 된다. 그럼 오른쪽 .. 2021. 11. 9. Shortest Paths(다익스트라 알고리즘 (Dijkstra Algorithm)) 이번에는 다익스트라 알고리즘에 대해서 공부를 해보았다. 다익스트라 알고리즘은 단일 시작점으로부터 다른 노드들까지의 최단 경로를 구하는 알고리즘이다. 또한, 음의 가중치를 허용하지 않는 최단경로를 말한다. 위의 그림을 설명하자면, 시작점을 제외한 모든 저점과 시작점 사이의 거리를 무한으로 표현하고 다음과 같은 수행을 반복한다. 1. 현재 선택한 정점(처음엔 시작점)에 곧장 연결되고, 아직 방문하지 않은 정점들을 모두 본다. 2. 선택한 정점과 보고있는 정점 사이의 거리와 시작 정점과 선택한 정점까지의 최단거리의 합이 현재까지 구한 시작 정점과 보고 있는 정점 사이의 거리보다 짧을 경우, 이를 갱신해준다. 3. 1, 2번 수행이 모두 끝난 이후, 아직 방문하지 않은 정점들 중 시작점과의 거리가 가장 짧은 정.. 2021. 11. 2. 이전 1 다음
