Alex-Moon Alex-Moon

트리의 구조와 관련 용어 트리는 아래의 사진과 같이 노드(node)와 가지(edge)로 구성된다. 각 노드는 가지를 통해 다른 노드와 연결된다. 루트 : 트리의 가장 위쪽에 있는 노드를 루트라고 한다. 루트는 트리 하나에 1개만 존재한다. 리프 : 가장 아래쪽에 있는 노드를 의미한다. 단말 노드(terminal node), 외부 노드(external node)라고도 한다. 물리적으로 가장 밑에 위치한다는 의미가 아니라 가지가 더 이상 뻗어나갈 수 없는 마지막에 노드가 있다는 뜻이다. 비단말 노드(non-terminal node) : 리프를 제외한 노드. 내부 노드(internal node)라고도 한다. 자식 : 어떤 노드와 가지가 연결되었을 때 아래쪽 노드. 노드는 자식을 몇개라도 가질 수 있다. 부모 ..

리스트는 데이터에 순서를 매겨 늘어놓은 자료구조다. 구조가 간단한 리스트로 선형 리스트(linear list) 또는 연결 리스트(linked list)가 있다. 위의 그림은 연결 리스트의 기본 구조다. A에서 F까지 데이터가 순서대로 나열되고 각 데이터가 화살표로 연결되어 있다. 이런 구조에서는 누군가를 건너뛰거나 뒤돌아 앞사람에게 연락해서는 안 된다. 연결 리스트에서 각각의 원소를 node라고 한다. 노드는 data와 pointer를 갖고 있다. 맨 앞에 있는 노드를 head node, 맨 끝에 있는 노드를 tail node라고 한다. 각 노드에서 바로 앞에 있는 노드를 predecessor node, 바로 뒤에 있는 노드를 successor node라고 한다. 배열로 연결 리스트 만들기 뒤쪽 노드 꺼..

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..