EDWARD

Boyer-Moor method는 이론이나 실제 효율에서 KMP법보다 뛰어나서 실제 문자열 검색에서 널리 사용하는 알고리즘이다. 패턴의 끝문자에서 시작하여 앞쪽을 향해 검사를 수행한다. 이 과정에서 일치하지 않는 문자를 발견하면 미리 준비한 표를 바탕으로 패턴이 이동하는 값을 결정한다. 예를 들어 'ABCXDEZCABACABAC'에서 패턴 'ABAC'를 검색하는 과정을 살펴보자. 위 그림의 a처럼 텍스트와 패턴의 첫 문자를 나란히 놓고 패턴의 마지막 문자 C에 주목한다. 같은 위치에 있는 텍스트의 X는 패턴 안에 포함되어 있지 않다. 따라서 b~d 처럼 패턴을 이동해도 텍스트와 패턴은 일치하지 않는다. 이처럼 패턴에 포함되지 않는 문자를 텍스트에서 발견하면 그 위치까지는 건너뛸 수 있다. 그로므로 b~d..

brute force method는 일치하지 않는 문자를 만나면 다시 패턴의 첫 문자부터 검사를 수행하지만, KMP method는 검사한 결과를 버리지 않고 효율적으로 사용할 수 있는 알고리즘이다. 에를 들어 텍스트 'z a b c a b x a c c a d e f'에서 패턴 'abcabd'를 검색할 때 KMP 알고리즘을 사용해보자. A. 먼저 텍스트와 패턴의 첫 문자부터 차례로 검사를 수행한다. 텍스트의 첫 문자 z는 패턴에 포함되지 않는 문자이므로 불일치하다. B. 패턴을 오른쪽으로 1칸 민다. 패턴의 앞쪽부터 차례로 검사를 수행해 가면 패턴의 마지막 문자 d가 텍스트의 문자 x와 불일치하다. C. 여기서 텍스트 안의 ab와 패턴 안의 ab가 일치하는 것에 주목한다. 이 부분이 검사를 마친 부분이라..

문자열 검색(string search)은 어떤 문자열 안에 다른 문자열이 포함되어 있는지 검사하고, 포함되어 있다면 어디에 위치하는지 찾아내는 것을 말한다. 검색되는 쪽의 문자열을 text, 찾아내는 문자열을 pattern이라고 한다. 브루트 포스 브루트 포스법(brute force method)이란 선형 검색을 단순하게 확장한 알고리즘이라서 단순법이라고 한다. 예를 들어 텍스트 'ABABCDEFGHA'에서 패턴 'ABC'를 브루트 포스로 검색하는 순서를 알아보자. A. 텍스트의 첫 문자 'A'에서 시작하는 문자 3개가 패턴과 일치하는지 검사한다. A와 B는 일치하지만 C가 일치하지 않는다. B. 패턴을 오른쪽으로 1칸 밀고, 텍스트의 2번째 문자와 그 이후 부분이 일치하는지 검사한다. 불일치. C. 패..

도수 정렬(counting sort)은 원소의 대소 관계를 판단하지 않고 빠르게 정렬하는 알고리즘으로, 분포수 세기(distribution counting) 정렬이라고도 한다. 알고리즘 순서 단계 1. 배열 내 요소값들의 개수를 저장하는 카운트 배열(도수 분포표) 'f'를 생성하고 배열의 모든 원솟값을 0으로 초기화한다. 주어진 배열 'a'를 스캔하며 원솟값이 배열 f의 인덱스와 일치하는 곳에 카운트를 올리며 도수분포표를 채운다. 단계 2. 배열 f에 원소가 몇개 들어있는지 확인하기 위해 두 번째 원소부터 바로 앞의 원솟값을 더하는 과정을 통해 누적 도수 분포표를 만든다. 단계 3. 배열 a와 원소 수가 같은 작업용 배열 b가 필요하다. 배열 a의 원소를 맨 끝에서 맨 앞으로 스캔하면서 배열 f와 대조하..

개념 힙 정렬(heap sort)은 힙의 특성을 이용하여 정렬하는 알고리즘이다. 힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전 이진 트리이다. 이때 부모의 값이 자식의 값보다 항상 작아도 힙이라고 한다. 즉, 두 값의 대소 관계가 일정하면 된다. 힙에서 부모와 자식 관계는 일정하지만 형제(sibling)사이의 대소 관계는 일정하지 않다. 위의 사진은 힙의 원소를 배열에 어떻게 저장할 것인지를 나타낸다. 먼저 가장 위쪽에 있는 루트(10)를 저장하고, 한 단계 아래에서 왼쪽부터 배열의 인덱스 값을 1씩 증가시키면서 각 원소를 저장한다. 가장 마지막에 있는 원소 1까지 반복하여 힙을 배열에 저장하면 완료된다. 이러한 순서로 힙을 배열에 저장하면 다음과 같은 부모 인덱스와 왼쪽, 오른쪽..

병합정렬(merge sort)은 배열을 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘이다. 정렬을 마친 배열의 병합 쪼개진 두 배열이 정렬을 마친 후 병합하는 과정을 살펴본다. 각 배열에서 주목하는 원소의 값을 비교하여 작은 쪽의 원소를 꺼내 새로운 배열에 저장한다. 이 작업을 반복하며 정렬을 마친 배열을 만든다. 위의 코드는 3개의 반복문을 늘어놓는 단순한 병합 알고리즘이다. 병합하는 데 필요한 시간 복잡도는 O(n)이다. 더보기 def merge_sorted_list(a, b, c): pa, pb, pc = 0, 0, 0 # 각 배열의 커서(인덱스) na, nb, nc = len(a), len(b), len(c) # 각 배열의 원소 수 while pa < na..

정의 퀵 정렬(suick sort)은 가장 빠른 정렬 알고리즘으로 알려져 있으며 널리 사용된다. 배열 안의 한 원소(요소)를 선택하는 데, 이 원소를 pivot이라고 한다. pivot을 기준으로 pivot보다 작은 원소들은 왼쪽 그룹으로 큰 원소들은 오른쪽 그룹으로 옮긴다. 다시 각 그룹에서 pivot을 선택하여 나누기를 반복하고 모든 그룹이 1명씩 남으면 정렬이 완료된다. 1. 배열을 두 그룹으로 나누기 5 7 1 4 6 2 3 9 8 위의 배열에서 6을 pivot으로 선택하여 그룹을 나눈다. pivot을 x, 왼쪽 끝 원소의 인덱스를 pl, 오른쪽을 pr이라고 하겠다. 그룹을 나누려면 pivot 이하인 원소를 배열 왼쪽(맨 앞쪽)으로, 피벗 이상인 원소를 배열 오른쪽(맨 뒤쪽)으로 이동시켜야 한다. ..

정의 셸 정렬(shell sort)은 단순 삽입 정렬의 장점을 살리고 단점은 보완하여 더 빠르게 정렬하는 알고리즘이다. 단순 삽입의 특징 - 장점 : 이미 정렬을 마쳤거나 정렬이 거의 끝나가는 상태에서는 속도가 아주 빠르다. - 단점 : 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아진다. 셀 정렬은 먼저 정렬할 배열의 원소를 그룹으로 나눠 각 그룹별로 정렬을 수행한다. 그 후 정렬된 그룹을 합치는 작업을 반복하여 원소의 이동 횟수를 줄인다. 위의 배열은 먼저 서로 4칸씩 떨어진 원소를 꺼내어 4개의 그룹으로 나누고 그룹별로 정렬한다. 이런 방법을 '4 - 정렬'이라고 한다. 아직 정렬을 마치지 않았지만 정렬의 상태와 가까워졌다. 이어서 2칸 떨어진 원소를 모두 꺼내 '2 - 정렬'을 진행한다. 이후..

단순 선택 정렬의 정의 단순 선택 정렬(straight selection sort)은 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘이다. 다음은 단순 선택 정렬의 과정이다. 아직 정렬하지 않은 범위에서 값이 가장 작은 원소를 선택하고, 아직 정렬하지 않은 부분의 맨 앞 원소와 교환하는 작업을 반복한다. 이 과정을 n - 1번 반복하면 정렬하지 않은 부분이 없어지면서 전체 정렬을 완료한다. 알고리즘의 개요는 다음과 같다. for i in range(n - 1): min # a[i], ... a[n-1]에서 키 값이 가장 작은 원소의 인덱스 a[i]와 a[min]의 값을 교환 더보기 더보기 def selection_sort(a): n = len(a) for i in ran..

정렬 알고리즘의 정의 정렬(sorting)이란 텍스트나 숫자 등의 key를 항목 값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 말한다. 데이터를 정렬하면 쉽게 검색할 수 있다. 값이 작은 데이터를 앞쪽에 늘어놓는 것을 오름차순(ascending order)정렬이라 하고, 반대를 내림차순(descending order) 정렬이라 한다. 정렬 알고리즘은 데이터를 교환-선택-삽입하면서 정렬을 완료한다. 대부분의 정렬 알고리즘은 이 세가지를 응용한다. 안정성 여러 정렬 알고리즘 가운데 안정적인(stable) 알고리즘과 그렇지 않은 알고리즘으로 나눌 수 있다. 위의 그림처럼 안정적인 정렬 알고리즘은 값이 같은 원소의 순서가 정렬한 후에도 유지되는 것을 말한다. 안정적이지 않은 알고리즘..