Rabin-Karp Algorithm 라빈-카프 알고리즘 * String Matching Algorithms (문자열 매칭 알고리즘) (URL) - 전체 문자열 \(\texttt{string}\) 내에서 부분 문자열 \(\texttt{pattern}\)을 찾아내는데, Hash Algorithm을 이용하여 \(\texttt{string}\)과 \(\texttt{pattern}\)의 해시값을 비교하는 방법이다. Mechanism (원리) 1. 부분 문자열 \(\texttt{pattern}\)에 해당되는 수치값(해시값)을 계산한다. - \(\texttt{pattern}\)을 구성하는 Alphabet Set을 \(\Sigma\) 라 하면, \(\texttt{pattern}\)에 해당되는 해시값 \(\mathrm..
Sparse Matrix (smatrix) 희소 행렬 - 원소 대부분이 0인 행렬(희소 행렬; Sparse Matrix)을 효율적으로 처리할 수 있는 ADT를 구현한다. Main Specification (주요 기능) 1. Basic Matrix Operations - 행렬끼리의 덧셈, 뺄셈, 곱셈에 대한 Operator들이 Overloading되어 있다. 2. Matrix Specific Operations - 행렬의 Transpose(전치)를 수행하는 Member Function \(\texttt{transpose()}\)가 구현되어 있다. - 행렬의 Inverse Matrix(역행렬)를 구하는 Member Function \(\texttt{inverse()}\)가 구현되어 있다. \(\texttt{..
Polynomial Model 다항식 모델 - 다항식을 표현 및 처리할 수 있는 ADT를 구현한다. Main Specification (주요 기능) 1. Basic Operations - 다항식의 앞에 '+' 혹은 '-'를 위치시켜 부호를 유지하거나 반전(Negation)시키는 Operator들이 Overloading되어 있다. - 다항식끼리의 덧셈, 뺄셈, 곱셈에 대한 Operator들이 Overloading되어 있다. 2. Mathematical Functions - 1차, 2차, 3차식에 한하여, \(f(x) = 0\) (Equation)에 대한 해를 출력하는 Member Function \(\texttt{findRoot()}\)가 구현되어 있다. - 2차식, 3차식에 한하여, Discriminan..
Magic Square 마방진 각 행의 합, 각 열의 합, 주대각선의 합이 모두 같은 n X n Matrix를 의미한다. - n X n Matrix는 1부터 \(n^2\)까지의 정수로 채워진다. Example. 5 X 5 Magic Square 15 8 1 24 17 16 14 7 5 23 22 20 13 6 4 3 21 19 12 10 9 2 25 18 11 Implementation in C++ void Magic(const int n) { const int MaxSize = 51; int square[MaxSize][MaxSize], k, l; if( (n < MaxSize) || (n < 1) ) throw "Error! n out of range"; else if( !(n%2) ) throw "..
Eratosthenes' Sieve 에라토스테네스의 체 * 소수 (Prime Number) : 약수가 1과 자기 자신만 존재하는 자연수 * 합성수 (Composite Number) : 소수가 아닌 수 * 통상적으로, 1은 소수가 아닌것으로 정의한다. - 2 이상의 자연수 \(n\)이 소수인지를 \(\Theta(n)\) 시간에 찾아낼 수 있는 알고리즘이다. (소수 판별을 Bruteforcing 방법으로 찾아낼 경우, \(\Theta(n^2)\) 시간이 소요된다.) - \(n\)이 소수인지를 판별하기 위해, 먼저 \(2 \leq P_i \leq \lfloor\sqrt{n}\rfloor\) 인 소수 \(P_i\)들을 Bruteforcing하여 찾아낸 다음, 2 이상, \(n\) 이하의 수들 중 \(P_i\)의..
