Boyer-Moore Algorithm 보이어-무어 알고리즘 * String Matching Algorithms (문자열 매칭 알고리즘) (URL) - 전체 문자열 \(\texttt{string[1...m]}\)에서 부분 문자열 \(\texttt{pattern[1...m]}\)을 찾아내는데, 최악의 경우에는, \(\Theta(n*m)\) 시간 동안 수행되지만, 평균적으로 \(\Theta(n)\)과 \(\Theta({n \over m})\) 사이의 시간 동안 수행되어 실무에서 KMP Algorithm보다 더 자주 쓰이는 알고리즘이다. (대체로, \(\Theta({n \over m})\)에 더 가까운 성능을 보인다고 한다.) Mechanism (원리) - Mismatching이 발생했을 때, Bad-Char..
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 "..
