CHUCK CHUCK 박사

잼잼 개발자

[Algorithm] Strings - Regular Expression Matching

문자열 정규 표현식 매칭

Rabin-Karp? Rabin-Karp 알고리즘은 문자열에서 특정 패턴을 찾는 데 사용되는 효율적인 해시 기반 문자열 검색 알고리즘입니다. 이 알고리즘의 핵심은 해시 함수를 이용해 텍스트와 패턴의 해시 값을 계산하고, 이를 비교하여 패턴을 찾는 방식입니다. 동작 방식: 패턴과 텍스트의 첫 번째 부분의 해시 값을 계산합니다...

[Algorithm] Strings - Knuth–Morris–Pratt Algorithm

문자열 Knuth–Morris–Pratt

Knuth–Morris–Pratt(KMP)? KMP 알고리즘은 문자열 검색 알고리즘으로, 주어진 문자열 내에서 특정 패턴이 존재하는지, 또는 어디에 존재하는지를 효율적으로 찾는 방법입니다. 이 알고리즘은 패턴의 부분 일치 정보를 미리 계산하여 불필요한 비교를 피하는 방식으로 동작합니다. 알고리즘의 핵심 개념: Prefix ...

[Algorithm] Strings - Longest Common Substring Problem

문자열 LCS

Longest Common Substring? Longest Common Substring (LCS) 문제는 두 문자열 간에 가장 긴 공통 부분 문자열을 찾는 문제입니다. 이때, 부분 문자열은 문자열에서 연속된 문자들로 이루어진 부분을 말하며, 중간에 문자가 생략될 수는 없습니다. 어디에 사용되는지: 유전자 서열 비교: 유...

[Algorithm] Strings - Rabin Karp Algorithm

문자열 라빈 카프

Rabin-Karp? Rabin-Karp 알고리즘은 문자열에서 특정 패턴을 찾는 데 사용되는 효율적인 해시 기반 문자열 검색 알고리즘입니다. 이 알고리즘의 핵심은 해시 함수를 이용해 텍스트와 패턴의 해시 값을 계산하고, 이를 비교하여 패턴을 찾는 방식입니다. 동작 방식: 패턴과 텍스트의 첫 번째 부분의 해시 값을 계산합니다...

[Algorithm] Strings - Levenshtein Distance

문자열 레벤슈타인 거리

레벤슈타인 거리 (Levenshtein Distance)? 설명: 레벤슈타인 거리는 두 문자열 사이에서 하나의 문자열을 다른 문자열로 변환하기 위해 필요한 최소 편집 횟수를 의미합니다. 여기서 편집 작업은 삽입(Insertion), 삭제(Deletion), 교체(Substitution) 세 가지로 이루어집니다. 이 거리는 문자열 유...

[Algorithm] Strings - Z Algorithm

문자열 Z 알고리즘

Z 알고리즘? Z 알고리즘은 문자열에서 특정 패턴을 찾거나 문자열 내에서 일치하는 부분을 빠르게 계산하는 효율적인 방법입니다. 주어진 문자열에서 각 접두사와 원래 문자열의 접두사와의 일치하는 길이를 저장하는 Z 배열을 기반으로 동작합니다. Z 배열이란? Z 배열의 각 요소는 해당 인덱스에서 시작하는 부분 문자열이 원래 문자...

[Algorithm] Strings - Hamming Distance

문자열 해밍 거리

해밍 거리 (Hamming Distance)? 설명: 해밍 거리는 두 이진 문자열 간에 서로 다른 비트의 개수를 의미합니다. 즉, 두 개의 동일한 길이의 문자열에서 각 위치에서 다른 값을 가진 비트의 수를 측정하는 데 사용됩니다. 이는 주로 오류 검출 및 교정, 데이터 전송에서 사용됩니다. 사용 사례: 오류 검출 및 교정:...

[Algorithm] Sets - Combination Sum Problem

집합 최대 조합 합 문제

조합 합 문제 (Combination Sum Problem)? 설명: 조합 합 문제는 주어진 배열 내의 숫자들을 사용하여 특정 목표값을 만들 수 있는 모든 조합을 찾는 문제입니다. 이 문제에서 각 숫자는 여러 번 사용할 수 있으며, 숫자의 순서는 중요하지 않습니다. 주로 백트래킹(Backtracking)을 통해 효율적으로 해결할 수...

[Algorithm] Sets - Maximum subarray problem

집합 최대 부분 배열 문제

최대 부분 배열 문제 (Maximum Subarray Problem)? 설명: 최대 부분 배열 문제는 배열 내에서 연속된 부분 배열 중 합이 가장 큰 부분 배열을 찾는 문제입니다. 이 문제는 Kadane’s Algorithm이라는 알고리즘을 사용해 효율적으로 해결할 수 있습니다. 이 알고리즘의 시간 복잡도는 O(n)으로 매우 효율적...

[Algorithm] Sets - Knapsack Problem

집합 배낭 문제

배낭 문제 (Knapsack Problem)? 배낭 문제는 제한된 용량의 배낭에 다양한 무게와 가치가 있는 물건들을 넣어 최대 가치를 얻는 문제입니다. 배낭 문제는 최적화 문제 중 하나로, 다양한 변형들이 존재하며 실제로 여러 가지 분야에 응용될 수 있습니다. 대표적으로 세 가지 배낭 문제가 있습니다: 0/1 배낭 문제 (0...