공부한 내용 기록하기 공부한 내용 기록하기

1. Rabin-Karp 알고리즘이란?Rabin-Karp 알고리즘은 문자열 내에서 특정 패턴을 효율적으로 찾기 위해 해시 함수를 사용하는 알고리즘이다. 여러 개의 패턴을 한꺼번에 찾는 데 적합하며, 해시 충돌이 적고 효율적인 해시 함수를 사용할 경우 매우 빠르게 동작한다.기본 아이디어는 텍스트의 각 부분 문자열과 찾고자 하는 패턴을 해시 값으로 변환하고, 이 해시 값이 동일할 경우 실제 문자열을 비교하는 방식이다. 일반적인 비교 방식보다 더 빠르게 일치 여부를 판단할 수 있다.2. Rabin-Karp 알고리즘의 동작 원리Rabin-Karp 알고리즘은 다음과 같은 절차로 동작한다:패턴 문자열의 해시 값을 계산한다.텍스트에서 패턴과 같은 길이의 부분 문자열의 해시 값을 계산한다.두 해시 값이 같으면, 실제 ..

1. KMP 알고리즘이란?KMP(Knuth-Morris-Pratt) 알고리즘은 문자열 검색 알고리즘 중 하나로, 텍스트(text)에서 특정 패턴(pattern)을 효율적으로 찾을 수 있도록 설계되었다. 기본적인 브루트포스(Brute Force) 방식보다 성능이 뛰어나며, 검색을 수행하는 동안 불필요한 비교를 줄이는 것이 특징이다.KMP 알고리즘은 한 번 검색된 정보를 활용하여, 이미 일치한 부분을 다시 비교하지 않도록 한다. 이를 통해 최악의 경우에도 O(n + m)의 시간 복잡도를 유지할 수 있다. 여기서 n은 텍스트의 길이, m은 패턴의 길이를 의미한다.2. KMP 알고리즘의 원리KMP 알고리즘은 다음 두 가지 주요 과정으로 구성된다:2.1 접두사-접미사 테이블(Partial Match Table) ..

1. 브루트포스 문자열 검색 알고리즘이란?브루트포스(Brute Force) 문자열 검색 알고리즘은 가장 단순한 패턴 매칭 기법 중 하나로, 주어진 텍스트에서 특정 패턴을 찾기 위해 모든 가능한 위치에서 하나씩 비교하는 방식으로 동작한다. 별도의 전처리 과정이 필요하지 않아 이해하고 구현하기 쉬운 것이 장점이다.2. 브루트포스 알고리즘의 동작 원리브루트포스 문자열 검색은 다음과 같은 방식으로 동작한다.텍스트 문자열의 첫 번째 문자부터 패턴과 비교를 시작한다.패턴의 모든 문자가 일치하면 검색이 완료된다.일치하지 않으면 텍스트에서 한 칸 오른쪽으로 이동하여 다시 비교를 수행한다.텍스트의 끝까지 이동하면서 위 과정을 반복한다.2.1 예제텍스트: "ABABCABAB"패턴: "ABAB"텍스트의 첫 번째 문자에서 시..