1. 다익스트라 알고리즘이란?이 알고리즘은 에츠허르 데이크스트라가 1956년에 고안하고 1959년에 발표되었다. 그의 이름에서 따와 데이크스트라, 다익스트라라고 불리우는 이 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. 최단 경로 탐색 알고리즘으로 널리 알려져있으며, 흔히 인공위성 GPS 소프트웨어 등에서 가장 많이 사용된다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려주기 때문에 음의 간선을 포함할 수 없다. 물론 우리가 살아가는 현실은 음의 간선이란 존재하지 않기에 다익스트라 알고리즘은 현실 세계에서 사용하기 매우 적합한 알고리즘 중 하나라고 할 수 있다. 다익스트라 알고리즘은 하나의 정점에서 모든 정점으로 가는 최단 ..

아호 코라식 알고리즘(Aho-Corasick string matching algorithm)은 Alfred V. Aho와 Margaret J. Corasick이 고안한 문자열 매칭 알고리즘이다. 패턴 1개를 탐색하는 매칭 알고리즘은 선형 시간에 구현됨을 KMP 등 여러 알고리즘을 통해 증명되었으나, 패턴 집합에 대해 해당 알고리즘들을 사용해보면 패턴 개수에 비례해 그 속도가 느려진다는 점이 발생했다.시간복잡도는 O(m + zn)이 되는 것이다.m: 모든 패턴들의 길이 합z: 패턴 수n: text 크기이를 보완한 것이 아호 코라식 알고리즘으로 시간복잡도는 O(m + n + k)이다. 패턴 집합에 대하여 패턴 길이와 텍스트의 선형 시간에 탐색을 처리할 수 있게 된다.k: 텍스트 내에 패턴의 발생 수 아호 코..

1. 마나커 알고리즘(Manacher's Algorithm)이란?어떤 문자열에서 팰린드롬의 개수와 위치를 찾는 알고리즘이다. 팰린드롬이란?팰린드롬(회문, Palindrome)은 전체 문자열을 뒤집었을 때 원래 상태와 같은 수열, 문자열 등을 의미한다.ex) "기러기", "eye", "level", "aba", "aa"  마나커 알고리즘은 문자열 길이의 P 배열에 i번째 문자를 중심으로 한느 가장 긴 팰린드롬의 반지름 크기를 저장한다.시간복잡도는 O(N)으로 접미사배열 + LCP 배열을 이용한 방법 O(NLogN)보다 빠르다. https://small-stepping.tistory.com/936 멘버 마이어스 알고리즘과 Kasai 알고리즘문자열을 다룰 때 빼놓을 수 없는 자료 구조인 접미사 배열(Suffi..

문자열을 다룰 때 빼놓을 수 없는 자료 구조인 접미사 배열(Suffix Array)은 다양한 문제를 푸는데 사용 가능하다.이 접미사 배열은 어떤 문자열 S의 모든 접미사를 사전순으로 정렬해둔 것으로 기본적으로 문자열 길이의 제곱에 비례하는 메모리가 필요하기 때문에 보통 각 접미사의 시작 위치를 담는 정수 배열로 구현된다. 예를 들어, 문자열 S = banana의 접미사 배열은 다음과 같다.Suffixindexa6ana4anana2banana1na5nana3 접미사 배열은 위에서 말했듯 각 접미사의 시작 위치를 담는 정수 배열로 구현되며, 이를 사용해 문자열 검색에 사용할 수 있다. 접미사 배열을 정렬 알고리즘으로 구현할 경우 구현은 매우 쉽다. 그러나 시간 복잡도가 O(nLogn)이 걸리고 최악의 경우 ..

1. 세그먼트 트리란? 간격 또는 세그먼트에 대한 정보를 저장하는데 사용되는 트리 데이터 구조이다.주어진 포인트를 포함하는 저장된 세그먼트에 대해서 쿼리할 수 있다. N개의 원소에 대하여 구성된 세그먼트 트리는 트리를 생성하는 비용은 O(N)이다.원소를 Update하는데 O(Log N)의 시간 복잡도가 필요하고, 쿼리 또한 O(Log N)의 시간 복잡도가 요구된다. 세그먼트 트리는 누적합, 구간합, 구간의 최솟값을 구하는데 사용할 수 있다. 1.1. 생성1차원 배열을 통해 구현하며 0번 Index는 사용하지 않는다.원본 배열 Size의 2배 크기로 구성한다.크기를 2배로 잡는 것은, 원본 배열로 세그먼트 트리의 리프 노드를 구성하게 되면, 세그먼트 트리가 이진트리이므로 (리프노드 개수 / 2)를 하면 모..

노드 정점들을 연결하는데 가장 적은 비용으로 연결하려면 어떻게 해야할까?   해당 질문을 해결하기 위한 대표적인 방법은 크루스칼 알고리즘이다.크루스칼 알고리즘이란, 모든 노드를 지나면서 사이클이 생기지 않고 가장 적은 비용을 가는 경로를 알 수 있다.   이 4개의 그림을 보자.모두 그래프의 모든 정점을 지난다는 것을 알 수 있으며, 순환고리(사이클이 생기지 않는 연결)이다.이러한 연결을 신장 트리라고 한다. 각 그림들의 가중치 합은 다음과 같다.3 + 4 + 1 = 8 4 + 3 + 2 = 94 + 5 + 2 = 113 + 2 + 1 = 6 가장 작은 가중치 합을 가진 그림은 우하단의 그래프이며, 이러한 값을 갖는 연결을 최소 신장트리라고 한다.최소 신장 트리를 구하는 대표적인 방법은 다음과 같다.프림..

1. KMP(Knuth-Morris-Pratt Alogorithm) 알고리즘이란?흔히 발견자 Knuth, Morris, Pratt의 앞글자를 딴 KMP로 읽히는 이 알고리즘은 전체 문자열에서 특정 문자열을 찾는 방식으로 오토마타(Finite-state automaton based search) 알고리즘과 비슷한 형식을 가지나 메모리와 시간 양측에서 모두 이득을 볼 수 있어 문자열 검색 알고리즘에서 브루트포스 외에 흔히 사용되는 알고리즘이다. 시간복잡도는 O(N + M)이다. 2. 구현 방식예를 들어, "ABABABCD" 라는 문자열과 "ABABC"라는 패턴이 존재할 때 KMP 알고리즘으로 문자열을 검색하면 다음과 같은 방식으로 이루어진다. ABABABCDABABC           ABABABCD  AB..

정렬 알고리즘이란? 말그대로 정렬을 위한 것으로, 정렬은 일종의 조건에 맞게 요소들을 나열하는 것을 의미한다. 이 정렬 알고리즘은 종류가 다양한데 대표적인 것들을 하나씩 짧게 알아보도록 하자. 1. 선택 정렬(Selection Sort) 선택정렬 알고리즘은 앞 인덱스부터 시작하여 마지막 인덱스까지 값을 확인하며 최솟값을 비교하는 방식이다. 마지막에 도착했을때 최솟값을 앞 인덱스에 넣어 앞 쪽부터 정렬되도록 만든다. 시간복잡도는 O(n ^ 2)이다. var min_idx = 0 for (i in 0..arr.lastIndex-1) { min_idx = i for (j in i+1..arr.lastIndex) { if (arr[min_idx] > arr[j]) min_idx = j } val term = a..

1. 라빈 카프 알고리즘이란?특이한 문자열 매칭 알고리즘으로, 항상 빠르진 않으나 일반적인 경우 빠르게 작동하는 간단한 문자열 매칭 알고리즘이다. 해시(Hash) 기법을 사용하는데, 이 해시란 일반적으로 긴 데이터를 그것을 상징하는 짧은 데이터로 바꾸는 기법이다. 상징하는 데이터로 바꾸어 처리한다는 점에서 단순 해시 알고리즘의 경우 연산 속도가 O(1)에 달한다는 장점이 존재한다. 단순히 문자열을 비교하는 Native Search의 경우, 시간 복잡도가 O(NM)이 발생하나, 라빈 카프 알고리즘을 사용하면 평균적으로 O(N)으로 시간 복잡도를 단축시킬 수 있다. 2. 구현방식우선, 해시 계산법은 다음과 같다.문자열 AACBDDABC에서 패턴 ACB가 발견되는지를 라빈카프 알고리즘을 통해 탐색한다. 검색 ..

1. 트라이 자료구조란? 문자열의 집합을 표현하는 트리 자료구조. 원하는 원소를 찾기 위해 자주 이용되는 이진 검색들은 원소를 찾는데 O(logN)의 시간이 걸린다. 문자열의 길이가 길수록 더욱 오래 걸리게 되고, 원하는 문자열을 찾는데 O(MlogN)의 시간이 걸리게 될 것이다. 이는 반복수행하게 된다면 더더욱 오래 걸리게 된다. 이를 해결한 것이 문자열 특화 자료구조, 트라이(Trie)이다. 문자열을 빠르게 탐색할 수 있는 자료구조 트라이 자료구조의 시간복잡도는 다음과 같다. 제일 긴 문자열을 L, 총 문자열의 수를 M이라고 할 때 생성시 시간 복잡도는 O(M*L)이다. 탐색시 시간복잡도는 O(L)이다. 2. 작동 원리 트라이는 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리이다..