KMP 알고리즘이란? 'Knuth-Morris-Pratt' 의 줄임말입니다. 이 알고리즘을 설계한 사람들입니다. 전체 문자열에서, 특정 문자열(패턴)을 빠르게 찾는 알고리즘입니다. 이와 비슷하게 문자열을 찾는 여러 알고리즘이 있습니다. 대략적으로 소개하자면 다음과 같습니다. - Naive Algorithm : 가장 쉽게 생각할 수 있는, O(N²)의 전체 탐색 알고리즘입니다. - Rabin & Karp Algorithm : 해시를 이용한 문자열 탐색 알고리즘입니다. - Boyer & Moore Algorithm : 일반적으로 가장 빠른 알고리즘입니다. - Suffix Tree / Array : 접미사 트리 / 배열이라고 불리는, 테이블을 이용한 알고리즘입니다. KMP 알고리즘 역시 이해하기 어렵습니다. ..

확장된 유클리드 알고리즘이란? '확장된' 이라는 말이 붙었습니다. 그렇다면 유클리드 알고리즘이란 무엇일까요? 많은 분들이 알고 계신 것처럼, 유클리드 알고리즘은 최대공약수 (GCD) 를 구할 때 사용합니다. 만약 375와 275의 최대공약수를 구하고 싶다면 아래와 같이 유클리드 알고리즘을 적용할 것입니다. GCD(375, 275) → 25 여기에 덧붙여, 확장된 유클리드 알고리즘은 두 개의 숫자 375, 275에 대해서, 각각에 어떤 값을 곱하고 더해야 최대공약수인 25가 되는지도 알려줍니다. 즉, 아래와 같이 알려준다는 것입니다. xGCD(375, 275) → GCD = 25, S = 3, T = -4 여기에서 구해진 S와 T의 값을 이용하면, 375 * (3) + 275 * (-4) = 25 가 됨을..

프림(Prim) 알고리즘이란? 최소신장트리(MST, Minimum Spanning Tree) 를 찾기 위한 대표적인 알고리즘입니다. 여기에서 최소신장트리란, 아래와 같이 모든 노드를 연결하는 부분 그래프 중, 가장 비용이 적은 것입니다. 하늘색으로 표시한 경로가 최소신장트리입니다. 여기에서 최소신장트리의 길이는 (4 + 8 + 16 + 20) = 48 이 되겠습니다. 최소신장트리를 찾는 알고리즘은 크루스칼(Kruskal) 과 프림(Prim) 이 대표적입니다. 오늘은 그 중에서도 프림 알고리즘에 대해서 알아보겠습니다. 동작원리 프림 알고리즘에서는 MST의 후보가 될 간선을 담을 우선순위 큐가 필요합니다. 우선순위 큐는 최소의 비용을 가지는 경로가 우선순위를 갖게 합니다. (보통 Min Heap을 이용해서 ..

Convex Hull 이란? Convex Hull은 우리말로 번역하면 '볼록외피' 라는 뜻입니다. 말로는 잘 이해되지 않으니, 다음 그림을 보며 설명드리겠습니다. 7개의 노드가 있습니다. 여기에서, 가장 바깥의 노드들로만 전체를 감싸면, 그것이 Convex Hull이 됩니다. 아래와 같이 말이죠. 이러한 Convex Hull을 구하는 알고리즘은 여러가지 종류가 있습니다. Graham's Scan, Andrew Algorithm 등이 있는데, 오늘 여기에서는 Graham's Scan 알고리즘에 대해서 알아보겠습니다. 동작 원리 Convex Hull을 구현하기에 앞서, 계산기하학에서 자주 사용되는 CCW (Counter Clock Wise) 라는 용어에 대해 이해할 필요가 있습니다. 우리는 3개의 노드가 있..

퀵 정렬 (Quick Sort)이란? 이름부터가 퀵 정렬 (Quick Sort) 입니다. 빠르다는거겠죠? 맞습니다. 일반적인 상황에서 빠른 정렬 시간을 보장해준다고 합니다. 버블정렬, 삽입정렬, 선택정렬 등은 O(N²) 의 시간을 가지지만, 퀵 정렬은 평균적인 상황에서 O(N * log N) 의 시간을 가집니다. 그러므로 빠른 정렬이라고 할 수 있겠죠. 최악의 경우에서는 O(N²) 의 시간복잡도를 가집니다. 이 경우는 이미 정렬이 완료되어있는 경우로, 이런 경우에는 합병정렬을 사용하는 것을 고려해볼 수 있습니다. 동작 원리 아래와 같은 배열이 있다고 가정해보겠습니다. 퀵 정렬을 사용하기 위해서는 피벗 (Pivot) 이라는 기준점을 잡아주어야 합니다. 즉, 피벗을 기준으로 작은 것과 큰 것을 구분해서 정렬..

합병정렬이란? 퀵정렬 (Quick Sort) 와 함께 대표적으로 사용되는 빠른 정렬 알고리즘입니다. 얼마나 빠르냐구요? 퀵정렬과 동일하게 O(N * log N) 입니다. 물론 완전히 동일한 시간이 걸린다는 것은 아닙니다. 퀵정렬은 최악의 경우 (이미 정렬되어있는 경우) 에서는 O(N²) 까지 걸릴 수 있거든요. 하지만 합병정렬은 나누고 병합하는 과정에서 O(N * log N)이 거의 보장됩니다. 그러므로, 특정한 경우에서는 퀵정렬 대신 병합정렬을 사용하기도 합니다. 동작 원리 다음과 같은 배열이 있다고 가정해볼게요. 우리는 병합정렬을 하기 위해서, 크게는 아래 그림과 같은 과정을 거칠 것입니다. 그림에서 보시는 것처럼, 합병정렬은 크게 3가지의 과정을 가집니다. (1) 분할 - N 길이의의 배열을 N /..