Bull

소개만든 사람의 이름 앞 글자를 따서 Knuth, Morris, Prett로 지었다. 해당 알고리즘은 문자열 A에서 문자열 B가 어디에 있는지 찾는 알고리즘이다. 이는 브루트포스를 통해서 모든 경우를 찾아도 되지만, O(NM) 시간복잡도를 가지기 때문에 해당 알고리즘을 사용하면 O(N+M)으로 단축시킬 수 있다.KMP 알고리즘 내에서는 LPS (Logest Prefix which is also Suffix) 알고리즘이 사용되는데, 이는 다른 글로 정리 하였다. [1]에 정리하였다. [1] LPS 정리도 [2] 자료를 통해서 정리를 하였는데, 해당 블로그 글을 작성하신 분이 정리를 참 잘해놓으셔서 이해하는데 큰 도움을 얻었다.원리[1] LPS를 설명할 때 패턴이 일치되는 부분의 접두사와 접미사를 각 문자..

소개패턴 매칭. 원래는 KMP 알고리즘을 알기 전에, 아호-코라식 알고리즘을 우선적으로 알게 되었다. 하고있는 프로젝트에서 문장을 가지고 특정 문자열이 포함되어 있는 찾아야 했다. 하지만, 일반적인 브루트 포스 방식으로 한다면 시간이 오래 걸릴 것이란 것을 알고 있다. 그래서 제미나이가 나에게 아호-코라식 알고리즘을 소개해주었다. 알아보니 아호-코라식 알고리즘을 알기전에 KMP 알고리즘이 사용되기 때문에 그것을 먼저 알 필요가 있었다.문자열 패턴 매칭은 다음과 같은 예시로 설명할 수 있다."The rain in Spain stays mainly in the plain" (영화 "마이 페어 레이디" 중)rain, Spain, mainly, plain 과 같이 ain 패턴이 많기 때문에, 단순 브루트 포스는..

오른쪽 1 제거// C++#include #include int main() { unsigned int num = 0xFFFFFFFF; while (num > 0) { std::cout (num) (num) num -= num & -num 혹은 num = num & (num - 1) 을 해주면 된다. # 결과1111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111001111111111111111111111111111100011111111111111111111111111110000111111111111111111111111111000001111111111111111..

개념 그래프는 데이터 구조의 하나로서, 여러 개의 정점(Vertex)과 이들을 연결하는 간선(Edge)으로 구성된다. 그래프는 사회 네트워크, 인터넷 연결, 도로망 등 다양한 시스템을 모델링하는 데 사용된다. 그리고 간선을 나타낼 때는 단방향, 양방향을 고려할 수 있다. 가장 일반적인 두 가지 방법은 인접 리스트(Adjacency List)와 인접 행렬(Adjacency Matrix)을 사용하는 것이다. 예시 위와 같은 그래프는 다음과 같이 설명할 수 있다. (양방향이라 할때) $0$ → 1,4 0은 1,4로 연결되어있다. $1$ → 0,2,3,4 1은 0,2,3,4와 연결되어있다. $2$ → 1,3 2는 1,3과 연결되어있다. $3$ → 1,2,4 3은 1,2,4와 연결되어있다. $4$ → 0,1,3 ..

설명 뤼카의 정리(Lucas' Theorem)는 조합론에서 사용되는 중요한 정리로, 특히 모듈로 $p$ ($p$가 소수일 때)의 이항계수를 계산할 때 유용하다. 이 정리는 프랑스의 수학자 에두아르 뤼카(Édouard Lucas)에 의해 발견되었다. 공식 뤼카의 정리의 핵심은 이항계수 $\binom{n}{k}$ (n과 k는 양의 정수, $\binom{n}{k}$는 n 위에 k를 쓴 이항계수를 의미)가 소수 $p$에 대하여 모듈로 $p$로 나눈 나머지를 구할 때, $n$과 $k$를 $p$진법(베이스 p)으로 확장한 후 각 자릿수를 별도로 이항계수 계산에 적용하여 최종 결과를 모듈로 $p$로 얻을 수 있다. 이를 수학적으로 표현하면, $n$과 $k$를 $p$진법으로 표현했을 때, $(n = n_0 + n_1p..