Computer Science and Engineering/Algorithm

간단한 그래프 기초 그래프(참고링크)는 객체 간 관계를 나타내는 자료구조로 정점(vertex) 집합 $ V $ 와 간선(edge) 집합 $ E $ 를 통해 $ G = (V, E) $ 로 나타내는 것이 일반적이다. 여기서는 오일러 경로와 해밀턴 경로에 필요한 몇 가지 개념만 다시 확인하겠다.경로(path)는 간선으로 연결된 연속적인 정점들의 집합이고, 그 중 동일한 정점이 단 한 번만 등장하는 경로를 단순 경로(simple path)라 한다.사이클(cycle)은 시작 정점과 끝 정점이 동일한 경로이다.일반적으로 그래프는 연결 리스트(linked list)를 통한 인접 리스트(adjacency-list)와 배열(array)을 통한 인접 행렬(adjecency-matrix)로 구현되는데 간선이 적을 때는 인접..

점과 선 (Point and Line) 2차원 평면에서 점은 각 차원의 위치로 나타낸다. 즉 다음과 같은 클래스를 통해 나타낸다.class Point{public: int x; int y; Point(int x, int y) { this->x = x; this->y = y; }};선은 두 개 이상의 점을 이은 것으로 다음과 같다.class Line{public: Point pt1; Point pt2; Line(Point pt1, Point pt2) { this->pt1 = pt1; this->pt2 = pt2; }};이를 통해서 다각형도 표현 가능한데, 한 꼭지점을 기준으로 하여 그 점으로부터 다각형의 둘레를 한..

동적 계획법 (DP) 최적화 이론 중 하나의 기술로 기존에 사용된, 즉 사전에 계산된(pre-computed) 값들을 재활용하는 방법이다. 즉 특정 알고리즘이라기 보다는 문제 해결 방식 중 하나이다. 다만 사전에 계산된 값들을 저장해두고 사용해야 하기 때문에 추가적인 메모리 사용이 필요하다.구현 방식에서 분할 정복(divide and conquer)과 유사한 측면이 있다. 앞에서 설명한 것 처럼 주어진 문제를 나누어 보고, 이 중 기존 계산을 이용할 수 있는 것을 불러와 사용하기 때문이다.그 방법에 따라 메모이제이션(memoization)과 타블레이션(tabulation)으로 나뉘는데 메모이제이션은 하향식(top-down)으로 보통 재귀 함수(recursion)와 함께 사용한다. 계산한 결과를 딕셔너리나..

KMP 알고리즘 (KMP Algorithm) 라빈-카프 알고리즘과 같이 문자열 탐색에서 직선적인 방법(참고링크)의 단점을 극복하기 위한 알고리즘이다. 알고리즘을 고안한 세 사람의 이름을 따서 KMP 알고리즘이라 이름 붙었다.라빈-카프 알고리즘은 문자열을 숫자로 바꾸고 해싱하는 방법으로 비교횟수를 줄였다면 KMP 알고리즘은 패턴 문자열의 접두부(prefix), 접미부(suffix) 매칭을 통해 불필요한 비교를 제거함으로써 비교횟수를 줄인다.불필요한 비교라는 것을 알아보기 위해 다음과 같이 텍스트 문자열과 패턴 문자열을 가정해보자.$$ \text{Text : } T = adcbadeadcbadcbadcf, \qquad \text{Pattern : } P = adcbadcf $$이제 비교를 해보자. 비교에서 ..

라빈-카프 알고리즘 (Rabin-Karp Algorithm) 문자열 탐색에서 직선적인 방법(참고링크)으로 일일이 문자열을 탐색하는 방식은 최악의 경우 $ O(n m ) $ 의 시간복잡도를 가지기 때문에 $ n $ 과 $ m $ 이 길어진다면 부적절하다.이를 극복하기 위해 나온 방법 중 하나가 라빈-카프 알고리즘으로 라빈-카프 알고리즘은 문자열을 숫자값으로 바꾸고 해시(hash) 값을 계산하여 매칭한다.예를 들어서 영문 알파벳이라 하면 26자가 있으므로 26진법의 숫자값으로 문자열을 변환한다. $ a $ 를 $ 0 $ 으로, $ b $ 를 $ 1 $ 로 매칭하는 방법으로 각 문자열을 하나의 수로 만드는 것이다. 간단하게 패턴 문자열 $ abba $ 를 변환하면 $ 0110 $ 으로 $ 110 $ 이 된다...

기본 표기법 문자열(참고링크)은 문자가 연속으로 나열된 것으로 문자열에 들어갈 수 있는 문자 집합을 $ \Sigma $ 로 표기한다. 공문자열은 아무런 원소가 없는 문자열로 $ \lambda $ 혹은 $ \epsilon$ 으로 표기한다. 단 $ \emptyset $ 과 $ \{ \epsilon \} $ 은 다르다.사람마다, 맥락마다 다르지만 여기서는 문자열의 탐색 대상이 되는 전체 문자열을 텍스트 문자열(text string)이라 하고, 이 텍스트 문자열에서 찾고자 하는 문자열을 패턴 문자열(pattern string)이라 한다.일바적으로 텍스트 문자열의 길이를 $ n $, 패턴 문자열의 길이를 $ m $ 으로 정의한다. 우직한 문자열 매칭 알고리즘 (Naïve String Matching Algorit..

레드블랙 트리 자가 균형 이진탐색트리로 특정 규칙을 설정하고, 이를 따르도록 하여 균형을 유지한다. 2-3-4 트리와 매우 유사하며, 모든 레드블랙 트리는 2-3-4 트리와 일대일 대응이 가능하다.레드블랙 트리는 루트노드에서 리프노드까지 경로에 나타나는 노드의 색을 제한함으로써 그러한 경오 중 어떠한 것도 다른 것보다 두 배 이상 길지 않음을 보장하고, 이를 통해 근사적 균형을 항상 보장한다.레드블랙 트리의 특성은 다음과 같고, 이를 만족하는 이진탐색트리를 레드블랙 트리라 한다.모든 노드는 적색(red) 혹은 흑색(black)이다.루트노드는 흑색이다.모든 리프노드는 흑색이다.노드가 적색이면 그 노드의 자식은 모두 흑색이다.각 노드로부터 그 노드의 자손인 리프노드로 가는 경로들은 모두 같은 수의 흑색 노드..

순차탐색 (Sequential Search) 이름 그대로 순차적으로 탐색하는 알고리즘이다. 정렬되지 않은 상태에서는 순차탐색이 유일한 방법일 때가 많다.int sequential_search(int arr[], int n, int key) { for (int i = 0; i 연결리스트라면 다음과 같을 것이다.struct node sequential_search(struct node head, int key) { for (struct node* t = head->link; t != NULL; t = t->link) { if (t->key == key) { return t; } } return NULL;}평균적인 경우 시간복잡도: $ O(n)..

외부 정렬 (External Sort) 메인 메모리(main memory)인 램에 전체 데이터를 올릴 수 없다면 보조 메모리(auxiliary memory)인 하드 디스크, SSD 등에서 일부 데이터만을 메인 메모리에 가져와 정렬해야 한다. 이를 외부 정렬이라 한다. 앞으로 메인 메모리는 메모리, 보조 메모리는 디스크라 하겠다. 일부 데이터만을 가져올 수 있기 때문에 한 번에 데이터 정렬이 불가능하고, 여러번 메모리와 디스크를 오가며 정렬해야 하고, 따라서 이 경우 비교 횟수 보다는 읽고 쓰는 시간, 즉 I/O 횟수가 더 중요하게 작용한다. 따라서 외부 정렬에서 시간복잡도 기준은 I/O 횟수이다.외부 정렬을 앞서 말한대로 외부에서 데이터를 불러와서 정렬하는 정렬 단계(sort phase)와 이를 다시 합..

최소 최대 선택 (Minimum and Maximum Selection) 가장 간단하게 배열에서 최대값과 최소값을 찾는 방법은 모든 값을 비교하면서 크면, 혹은 작으면 선택하고, 아니면 넘기는 방식으로, 배열의 크기가 $ n $ 이라 할 때 최대값 혹은 최소값을 찾을 때 $ O(n) $ 의 시간복잡도를 요구한다.그러나 만약 최대값과 최소값을 한번에 찾으려고 한다면 이를 두 번 반복해야 할텐데 한번에 두 값씩 가져와서 비교하는 방식으로 이를 효율적으로 만들 수 있다. 배열에서 두 값을 가져오고, 이를 큰 값과 작은 값으로 나누고, 큰 값은 기존 최대값과, 작은 값은 기존 최소값과 비교하며 업데이트하는 것이다.int* find_min_max(int list[], int n) { int min = lis..