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

1. Levenshtein Distance란?Levenshtein Distance는 두 문자열 간의 유사도(Similarity)를 측정하기 위한 알고리즘으로, 한 문자열을 다른 문자열로 바꾸기 위해 필요한 최소 연산 횟수(편집 거리, Edit Distance)를 계산한다. 이때 허용되는 연산은 다음 세 가지다.문자 삽입 (Insertion)문자 삭제 (Deletion)문자 교체 (Substitution)예를 들어, 문자열 "kitten"을 "sitting"으로 바꾸는 최소 편집 거리는 3이다.k → s (교체)e → i (교체)끝에 g 추가 (삽입)2. 알고리즘의 동작 원리Levenshtein Distance는 동적 계획법(Dynamic Programming)을 활용하여 2차원 배열(dp 테이블)을 구성..

1. LCS란?LCS(Longest Common Subsequence)는 두 문자열에서 순서를 유지하면서 등장하는 가장 긴 공통 부분 수열(Subsequence)을 찾는 알고리즘이다. 이때 '부분 수열'이란 원래 문자열의 일부 문자를 삭제하여 얻을 수 있는 시퀀스를 의미하며, 반드시 연속될 필요는 없다. 예를 들어문자열 A: "ACDBE"문자열 B: "ABCDE"A와 B의 LCS: "ACDE"LCS는 텍스트 비교, 유전자 서열 분석, 파일 차이(diff) 계산, 데이터 동기화 등에 널리 사용된다.2. LCS 알고리즘의 동작 원리LCS는 일반적으로 동적 계획법(Dynamic Programming)을 사용하여 해결한다. 이때 2차원 배열 dp[i][j]를 만들어, 문자열 A의 i번째 문자까지와 문자열 B의 ..

1. 접미사 배열(Suffix Array)이란?접미사 배열(Suffix Array)은 문자열의 모든 접미사를 사전 순으로 정렬한 후, 각 접미사의 시작 위치를 저장한 배열이다. 문자열 처리에서 자주 사용되는 자료구조로, 문자열 검색, 정렬, 패턴 매칭 등에 활용된다.예를 들어, 문자열 "banana"의 모든 접미사와 해당 인덱스를 정리하면 다음과 같다.접미사인덱스banana0anana1nana2ana3na4a5 이를 사전 순으로 정렬하면,정렬된 접미사시작 인덱스a5ana3anana1banana0na4nana2 → 접미사 배열: [5, 3, 1, 0, 4, 2]2. 접미사 배열의 활용문자열 정렬: 접미사 배열은 문자열 내 모든 부분 문자열의 정렬된 순서를 제공한다.패턴 매칭: 이진 탐색을 통해 특정 패턴이..

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

문자열 검색 알고리즘 (3): Boyer-Moore 알고리즘1. Boyer-Moore 알고리즘이란?Boyer-Moore 알고리즘은 문자열 검색(String Matching) 문제를 해결하기 위한 효율적인 알고리즘 중 하나로, 긴 텍스트에서 특정 패턴을 빠르게 찾는 데 최적화되어 있다. 1977년 Robert S. Boyer와 J. Strother Moore에 의해 개발되었으며, 일반적으로 가장 빠른 문자열 검색 알고리즘 중 하나로 평가된다.Boyer-Moore 알고리즘의 핵심 아이디어는 오른쪽에서 왼쪽으로 패턴을 비교하며, 불일치가 발생하면 미리 계산한 규칙을 이용해 건너뛰는 방식을 적용하는 것이다. 이를 통해 불필요한 비교를 최소화하여 검색 속도를 크게 향상시킬 수 있다.2. Boyer-Moore 알고..

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"텍스트의 첫 번째 문자에서 시..

1. 문자열 알고리즘이란?문자열 알고리즘(String Algorithms)은 문자열을 효율적으로 처리하고 분석하는 알고리즘을 의미한다. 문자열 검색, 정렬, 매칭, 압축 등 다양한 분야에서 활용되며, 특히 텍스트 처리, 자연어 처리(NLP), 바이오인포매틱스, 데이터 압축 등에서 중요하게 사용된다.2. 문자열 알고리즘의 주요 종류문자열 알고리즘은 목적에 따라 여러 가지로 분류할 수 있다. 대표적인 유형과 각 알고리즘의 특징을 정리하면 다음과 같다.2.1 문자열 검색 알고리즘문자열 검색 알고리즘은 주어진 문자열에서 특정 패턴을 효율적으로 찾는 데 사용된다.브루트포스(Brute-Force) 알고리즘: 모든 위치에서 패턴을 하나씩 비교하는 단순한 방식으로 구현이 쉽지만 성능이 낮다.KMP(Knuth-Morri..