# [06-09] 문자열 알고리즘
문자열 알고리즘은 텍스트 검색, 패턴 매칭, 압축 등 문자열 처리에 특화된 효율적인 알고리즘들입니다.
🎯 문자열 알고리즘이란
문자열 문제의 중요성
문자열 처리는 컴퓨터 과학에서 가장 기본적이면서도 중요한 분야입니다.
실생활 응용:
텍스트 검색:
- 구글, 네이버 검색
- Ctrl+F (문서 내 검색)
- 코드 에디터의 찾기
DNA 분석:
- 유전자 서열 매칭
- 유사한 패턴 찾기
텍스트 편집:
- 맞춤법 검사
- 자동 완성
- 표절 탐지
데이터 압축:
- ZIP, RAR
- 중복 패턴 제거기본 문제: 패턴 매칭
텍스트: "ABCABCDABCDE"
패턴: "ABCD"
목표: 패턴이 텍스트의 어디에 있는가?
답: 인덱스 3 (0부터 시작)
0123456789...
텍스트: ABCABCDABCDE
패턴: ABCD
찾음! (인덱스 3)이번 글에서 다룰 알고리즘
1. 순진한 방법 (Naive)
- 기본 접근
- 비교 대상
2. KMP 알고리즘
- 실패 함수
- 불필요한 비교 건너뛰기
3. 라빈-카프 알고리즘
- 해싱 이용
- 다중 패턴 매칭
4. 트라이 (Trie)
- 문자열 집합 저장
- 빠른 검색🔍 순진한 문자열 매칭
순진한 방법이란?
순진한 방법(Naive/Brute Force)은 가장 직관적인 패턴 매칭 방법입니다.
핵심 아이디어:
텍스트의 모든 위치에서 패턴과 비교
텍스트: ABCABCDABCDE
패턴: ABCD
위치 0: ABCA vs ABCD → 불일치 (마지막)
위치 1: BCAB vs ABCD → 불일치 (첫 글자)
위치 2: CABC vs ABCD → 불일치 (첫 글자)
위치 3: ABCD vs ABCD → 일치! ✓
...특징:
장점:
- 구현 간단
- 이해 쉬움
단점:
- 비효율적
- 불필요한 비교 많음순진한 방법 구현
def naive_search(text, pattern):
"""
순진한 문자열 매칭
text: 검색 대상 텍스트
pattern: 찾을 패턴
Returns: 패턴이 나타나는 모든 위치 리스트
시간복잡도: O(nm)
- n: 텍스트 길이
- m: 패턴 길이
- 최악의 경우 모든 위치에서 m번 비교
"""
n = len(text)
m = len(pattern)
positions = []
# 텍스트의 각 위치에서 시도
for i in range(n - m + 1):
# 패턴의 각 문자와 비교
j = 0
while j < m and text[i + j] == pattern[j]:
j += 1
# 모든 문자가 일치하면
if j == m:
positions.append(i)
return positions
# 사용 예시
text = "ABCABCDABCDE"
pattern = "ABCD"
result = naive_search(text, pattern)
print(f"텍스트: {text}")
print(f"패턴: {pattern}")
print(f"발견 위치: {result}")
# 비교 횟수 세기
def naive_search_count(text, pattern):
"""비교 횟수를 세는 버전"""
n = len(text)
m = len(pattern)
positions = []
comparisons = 0
for i in range(n - m + 1):
j = 0
while j < m and text[i + j] == pattern[j]:
comparisons += 1
j += 1
# 불일치한 경우도 비교 횟수 추가
if j < m:
comparisons += 1
if j == m:
positions.append(i)
return positions, comparisons
result, count = naive_search_count(text, pattern)
print(f"\n총 비교 횟수: {count}")최악의 경우:
텍스트: AAAAAAAAAA (n개)
패턴: AAAAB (m개)
매 위치에서 m-1개는 일치, 마지막만 불일치
→ (n-m+1) × m 번 비교
→ O(nm)
예: n=10, m=5
AAAAAAAAAA
AAAAB (5번 비교)
AAAAB (5번 비교)
AAAAB (5번 비교)
...
6개 위치 × 5번 = 30번 비교🔄 KMP (Knuth-Morris-Pratt) 알고리즘
KMP란?
KMP 알고리즘은 불필요한 비교를 건너뛰는 효율적인 패턴 매칭 알고리즘입니다.
핵심 통찰:
순진한 방법의 문제:
텍스트: ABCABCDABCDE
패턴: ABCD
|||X
ABC는 일치, D만 불일치
다음 위치에서 다시 처음부터?
ABCD
X
낭비!
이미 "ABC"가 일치한다는 정보를 알고 있는데
처음부터 다시 비교할 필요 없음!KMP의 아이디어:
패턴 자체에서 정보 추출
패턴: ABCDABC
"ABC"로 시작하고 "ABC"로 끝남!
→ 불일치 시 3칸 건너뛸 수 있음
이 정보를 "실패 함수"로 미리 계산실패 함수 (Failure Function)
실패 함수는 패턴의 각 위치에서 접두사와 접미사의 최대 일치 길이를 저장합니다.
개념:
패턴: ABCDABC
각 위치에서:
A 접두사=접미사 = 없음 → 0
AB 접두사=접미사 = 없음 → 0
ABC 접두사=접미사 = 없음 → 0
ABCD 접두사=접미사 = 없음 → 0
ABCDA 접두사=접미사 = A → 1
ABCDAB 접두사=접미사 = AB → 2
ABCDABC 접두사=접미사 = ABC → 3
실패 함수: [0, 0, 0, 0, 1, 2, 3]의미:
실패 함수[i] = k 의미:
"pattern[0:k] == pattern[i-k+1:i+1]"
즉, i 위치까지의 부분 문자열에서
길이 k인 접두사와 접미사가 같음
예: ABCDABC (i=6)
실패 함수[6] = 3
→ ABC(접두사) == ABC(접미사)실패 함수 계산
def compute_failure_function(pattern):
"""
KMP 실패 함수 계산
pattern: 패턴 문자열
Returns: 실패 함수 배열
시간복잡도: O(m)
- m: 패턴 길이
원리:
- 동적 계획법
- 이전 정보를 활용하여 다음 값 계산
"""
m = len(pattern)
failure = [0] * m
# j: 현재 접두사 길이
# i: 현재 확인 중인 위치
j = 0
# i=1부터 시작 (i=0은 항상 0)
for i in range(1, m):
# 불일치 시 j를 줄여가며 확인
while j > 0 and pattern[i] != pattern[j]:
j = failure[j - 1]
# 일치하면
if pattern[i] == pattern[j]:
j += 1
failure[i] = j
# 불일치면 failure[i] = 0 (이미 초기화됨)
return failure
# 사용 예시
pattern = "ABCDABC"
failure = compute_failure_function(pattern)
print(f"패턴: {pattern}")
print("위치: ", " ".join(str(i) for i in range(len(pattern))))
print("실패: ", " ".join(str(f) for f in failure))
# 여러 예시
patterns = ["AAAA", "ABAB", "ABABC", "ABCDABCA"]
print("\n다양한 패턴의 실패 함수:")
for p in patterns:
f = compute_failure_function(p)
print(f"{p:12s} → {f}")실패 함수 계산 과정:
패턴: ABCDABC
i=0: failure[0] = 0 (초기값)
i=1: pattern[1]='B', pattern[0]='A'
불일치 → failure[1] = 0
i=2: pattern[2]='C', pattern[0]='A'
불일치 → failure[2] = 0
i=3: pattern[3]='D', pattern[0]='A'
불일치 → failure[3] = 0
i=4: pattern[4]='A', pattern[0]='A'
일치! j=1 → failure[4] = 1
i=5: pattern[5]='B', pattern[1]='B'
일치! j=2 → failure[5] = 2
i=6: pattern[6]='C', pattern[2]='C'
일치! j=3 → failure[6] = 3
결과: [0, 0, 0, 0, 1, 2, 3]KMP 매칭
def kmp_search(text, pattern):
"""
KMP 문자열 매칭
text: 검색 대상 텍스트
pattern: 찾을 패턴
Returns: 패턴이 나타나는 모든 위치 리스트
시간복잡도: O(n + m)
- n: 텍스트 길이
- m: 패턴 길이
- 실패 함수 계산: O(m)
- 매칭: O(n)
"""
n = len(text)
m = len(pattern)
# 1. 실패 함수 계산
failure = compute_failure_function(pattern)
positions = []
j = 0 # 패턴에서 현재 비교 중인 위치
# 2. 텍스트 순회
for i in range(n):
# 불일치 시 실패 함수 활용
while j > 0 and text[i] != pattern[j]:
j = failure[j - 1] # 건너뛰기!
# 일치하면
if text[i] == pattern[j]:
j += 1
# 패턴 전체 일치
if j == m:
positions.append(i - m + 1)
j = failure[j - 1] # 다음 매칭을 위해
return positions
# 사용 예시
text = "ABCABCDABCDE"
pattern = "ABCD"
result = kmp_search(text, pattern)
print(f"텍스트: {text}")
print(f"패턴: {pattern}")
print(f"발견 위치: {result}")
# 비교 횟수 세기
def kmp_search_count(text, pattern):
"""비교 횟수를 세는 버전"""
n = len(text)
m = len(pattern)
failure = compute_failure_function(pattern)
positions = []
comparisons = 0
j = 0
for i in range(n):
while j > 0 and text[i] != pattern[j]:
j = failure[j - 1]
comparisons += 1
comparisons += 1 # 현재 비교
if text[i] == pattern[j]:
j += 1
if j == m:
positions.append(i - m + 1)
j = failure[j - 1]
return positions, comparisons
result, count = kmp_search_count(text, pattern)
print(f"\n총 비교 횟수: {count}")
print(f"순진한 방법과 비교: {count} vs 더 많음")KMP 실행 과정:
텍스트: ABCABCDABCDE
패턴: ABCD
실패: [0, 0, 0, 0]
i=0: text[0]='A', pattern[0]='A'
일치, j=1
i=1: text[1]='B', pattern[1]='B'
일치, j=2
i=2: text[2]='C', pattern[2]='C'
일치, j=3
i=3: text[3]='A', pattern[3]='D'
불일치! j=failure[2]=0
text[3]='A', pattern[0]='A'
일치, j=1
i=4: text[4]='B', pattern[1]='B'
일치, j=2
i=5: text[5]='C', pattern[2]='C'
일치, j=3
i=6: text[6]='D', pattern[3]='D'
일치, j=4
매칭 발견! 위치=3
...
핵심: 불일치 시 실패 함수로 건너뛰기!🔢 라빈-카프 (Rabin-Karp) 알고리즘
라빈-카프란?
라빈-카프 알고리즘은 해싱을 이용한 패턴 매칭 알고리즘입니다.
핵심 아이디어:
문자열을 숫자로 변환하여 비교
패턴: "ABC"
해시: hash("ABC") = 123
텍스트를 순회하며:
- 각 부분 문자열의 해시 계산
- 해시가 같으면 실제 문자열 비교
장점:
- 여러 패턴을 동시에 검색 가능
- 평균적으로 빠름해시 함수:
문자열을 숫자로:
"ABC" → 1×100 + 2×10 + 3×1 = 123
일반적으로:
hash = s[0]×d^(m-1) + s[1]×d^(m-2) + ... + s[m-1]×d^0
d: 진법 (보통 256, 문자 종류 수)
m: 패턴 길이롤링 해시 (Rolling Hash)
롤링 해시는 이전 해시값을 재사용하여 다음 해시를 빠르게 계산하는 기법입니다.
원리:
텍스트: "ABCDE"
패턴 길이: 3
hash("ABC") = 1×100 + 2×10 + 3×1 = 123
hash("BCD")를 처음부터 계산?
= 2×100 + 3×10 + 4×1 = 234
롤링 해시:
hash("BCD") = (hash("ABC") - 1×100) × 10 + 4
= (123 - 100) × 10 + 4
= 234
이전 값 재사용!공식:
hash_new = (hash_old - text[old_pos]×d^(m-1)) × d + text[new_pos]
old_pos: 이전 시작 위치
new_pos: 새로운 끝 위치라빈-카프 구현
def rabin_karp(text, pattern, d=256, q=101):
"""
라빈-카프 문자열 매칭
text: 검색 대상 텍스트
pattern: 찾을 패턴
d: 진법 (문자 종류 수)
q: 소수 (해시 충돌 감소용)
Returns: 패턴이 나타나는 모든 위치 리스트
시간복잡도:
- 평균: O(n + m)
- 최악: O(nm) (해시 충돌 많을 때)
특징:
- 해싱 이용
- 다중 패턴 매칭에 유리
- 롤링 해시로 최적화
"""
n = len(text)
m = len(pattern)
positions = []
# d^(m-1) % q 미리 계산
h = pow(d, m - 1, q)
# 패턴과 텍스트 첫 윈도우의 해시 계산
pattern_hash = 0
text_hash = 0
for i in range(m): # ord(): 문자를 컴퓨터가 이해하는 숫자(아스키 코드)로 바꿈 (예: 'A' -> 65)
pattern_hash = (d * pattern_hash + ord(pattern[i])) % q
text_hash = (d * text_hash + ord(text[i])) % q
# 텍스트 순회
for i in range(n - m + 1):
# 해시가 같으면
if pattern_hash == text_hash:
# 실제 문자열 비교 (해시 충돌 대비)
if text[i:i+m] == pattern:
positions.append(i)
# 다음 윈도우의 해시 계산 (롤링)
if i < n - m:
# 이전 문자 제거, 새 문자 추가
text_hash = (d * (text_hash - ord(text[i]) * h) +
ord(text[i + m])) % q
# 음수 방지
if text_hash < 0:
text_hash += q
return positions
# 사용 예시
text = "ABCABCDABCDE"
pattern = "ABCD"
result = rabin_karp(text, pattern)
print(f"텍스트: {text}")
print(f"패턴: {pattern}")
print(f"발견 위치: {result}")
# 다중 패턴 매칭
def rabin_karp_multiple(text, patterns, d=256, q=101):
"""
여러 패턴을 동시에 검색
라빈-카프의 장점 활용!
"""
# 각 패턴의 해시 계산
pattern_hashes = {}
for pattern in patterns:
h = 0
for char in pattern:
h = (d * h + ord(char)) % q
pattern_hashes[h] = pattern
results = {p: [] for p in patterns}
# 패턴 길이 (모두 같다고 가정)
m = len(patterns[0])
n = len(text)
# 텍스트 해시 계산 및 매칭
h_multiplier = pow(d, m - 1, q)
text_hash = 0
for i in range(m):
text_hash = (d * text_hash + ord(text[i])) % q
for i in range(n - m + 1):
# 해시가 어떤 패턴과 일치하는지 확인
if text_hash in pattern_hashes:
pattern = pattern_hashes[text_hash]
if text[i:i+m] == pattern:
results[pattern].append(i)
# 롤링 해시
if i < n - m:
text_hash = (d * (text_hash - ord(text[i]) * h_multiplier) +
ord(text[i + m])) % q
if text_hash < 0:
text_hash += q
return results
# 다중 패턴 예시
text = "ABCABCDABCDE"
patterns = ["ABC", "BCD", "CDE"]
results = rabin_karp_multiple(text, patterns)
print("\n\n다중 패턴 매칭:")
for pattern, positions in results.items():
print(f"{pattern}: {positions}")🌳 트라이 (Trie)
트라이란?
트라이(Trie)는 문자열 집합을 효율적으로 저장하고 검색하는 트리 자료구조입니다.
핵심 아이디어:
공통 접두사를 공유
문자열 집합: ["cat", "car", "dog"]
트리 구조:
root
/ \
c d
| |
a o
/ \ |
t r g
"ca"를 공유 → 메모리 절약특징:
장점:
- 검색: O(m) (m: 문자열 길이)
- 접두사 검색 빠름
- 자동 완성에 유용
단점:
- 메모리 많이 사용
- 각 노드마다 자식 배열트라이 구현
class TrieNode:
"""
트라이의 노드
Attributes:
children: 자식 노드 딕셔너리 {문자: TrieNode}
is_end: 이 노드가 단어의 끝인가?
"""
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
"""
트라이 자료구조
문자열 집합을 효율적으로 저장
"""
def __init__(self):
"""루트 노드로 시작"""
self.root = TrieNode()
def insert(self, word):
"""
단어 삽입
word: 삽입할 단어
시간복잡도: O(m)
- m: 단어 길이
동작:
1. 루트부터 시작
2. 각 문자마다 자식 노드 확인
3. 없으면 생성, 있으면 이동
4. 마지막 노드에 is_end 표시
"""
node = self.root
for char in word:
# 자식 노드가 없으면 생성
if char not in node.children:
node.children[char] = TrieNode()
# 다음 노드로 이동
node = node.children[char]
# 단어의 끝 표시
node.is_end = True
def search(self, word):
"""
단어 검색
word: 검색할 단어
Returns: bool: 단어가 존재하면 True
시간복잡도: O(m)
"""
node = self.root
for char in word:
# 자식 노드가 없으면 단어 없음
if char not in node.children:
return False
node = node.children[char]
# 단어의 끝이어야 함
return node.is_end
def starts_with(self, prefix):
"""
접두사로 시작하는 단어가 있는가?
prefix: 접두사
Returns: bool: 접두사를 가진 단어가 있으면 True
시간복잡도: O(m)
자동 완성에 유용!
"""
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
# 접두사까지 도달했으면 True (is_end 확인 불필요)
return True
def find_all_with_prefix(self, prefix):
"""
접두사로 시작하는 모든 단어 찾기
prefix: 접두사
Returns: 접두사를 가진 모든 단어 리스트
자동 완성 기능!
"""
node = self.root
# 접두사까지 이동
for char in prefix:
if char not in node.children:
return []
node = node.children[char]
# 이 노드부터 DFS로 모든 단어 수집
results = []
self._collect_words(node, prefix, results)
return results
def _collect_words(self, node, current_word, results):
"""
DFS로 모든 단어 수집 (헬퍼 함수)
"""
# 단어의 끝이면 추가
if node.is_end:
results.append(current_word)
# 모든 자식 탐색
for char, child in node.children.items():
self._collect_words(child, current_word + char, results)
# 사용 예시
trie = Trie()
# 단어 삽입
words = ["cat", "car", "card", "care", "dog", "dodge", "door"]
for word in words:
trie.insert(word)
print("삽입된 단어:", words)
# 검색
print("\n검색:")
print(f"'car' 존재? {trie.search('car')}")
print(f"'can' 존재? {trie.search('can')}")
# 접두사 확인
print("\n접두사 확인:")
print(f"'ca'로 시작? {trie.starts_with('ca')}")
print(f"'do'로 시작? {trie.starts_with('do')}")
print(f"'da'로 시작? {trie.starts_with('da')}")
# 자동 완성
print("\n자동 완성:")
prefix = "car"
suggestions = trie.find_all_with_prefix(prefix)
print(f"'{prefix}'로 시작하는 단어: {suggestions}")
prefix = "do"
suggestions = trie.find_all_with_prefix(prefix)
print(f"'{prefix}'로 시작하는 단어: {suggestions}")트라이 시각화:
단어: cat, car, card, care, dog, dodge, door
root
/ \
c d
| |
a o
| / \
r g o
/|\ | |
d e t e r
| | |
(card)(dodge)(door)
각 노드의 is_end:
- t: True (cat)
- r: True (car)
- d: True (card)
- e: True (care)
- g: True (dog)
- e: True (dodge)
- r: True (door)💡 실무 팁
알고리즘 선택
# 단순 패턴 매칭 → KMP
kmp_search(text, pattern) # O(n+m)
# 여러 패턴 동시 검색 → 라빈-카프
rabin_karp_multiple(text, patterns)
# 사전, 자동 완성 → 트라이
trie = Trie()
trie.find_all_with_prefix("car")성능 비교
알고리즘 시간 공간 특징
--------------------------------------------------
순진한 O(nm) O(1) 간단
KMP O(n+m) O(m) 단일 패턴 최적
라빈-카프 O(n+m)평균 O(1) 다중 패턴
트라이 O(m) O(총길이) 접두사 검색실무 고려사항
# 짧은 텍스트 → 순진한 방법도 OK
if len(text) < 1000:
naive_search(text, pattern)
# 긴 텍스트 → KMP
else:
kmp_search(text, pattern)
# 여러 패턴 → 라빈-카프 또는 Aho-Corasick
rabin_karp_multiple(text, patterns)
# 자동 완성, 사전 → 트라이
trie = Trie()🎯 핵심 정리
패턴 매칭
순진한 방법:
- 모든 위치에서 비교
- O(nm)
- 간단하지만 느림
KMP:
- 실패 함수로 최적화
- O(n+m)
- 단일 패턴에 최적
라빈-카프:
- 해싱 이용
- O(n+m) 평균
- 다중 패턴에 유리트라이
문자열 집합 저장:
- 공통 접두사 공유
- 검색: O(m)
- 자동 완성, 사전
- 메모리 많이 사용시간복잡도 비교
연산 순진한 KMP 라빈-카프 트라이
--------------------------------------------------------
패턴 매칭 O(nm) O(n+m) O(n+m)평균 -
다중 패턴 O(nmk) O(nmk) O(n+mk) O(n+m)
접두사 검색 - - - O(m)
자동 완성 - - - O(m+결과)🔗 다음 글에서는
[07-01] 시간 복잡도 (Time Complexity)
- Big-O 표기법: 알고리즘 성능을 수학적으로 표현하기
- 점근적 분석: 입력 크기가 커질 때의 성능 이해
- 복잡도 계산: 다양한 알고리즘의 시간복잡도 분석
- 최선/평균/최악: 상황별 알고리즘 성능 비교
이전 글: [06-08] 그래프 알고리즘
다음 글: [07-01] 시간 복잡도
시리즈: P1. Computer Science
AI 전문가를 꿈꾸는 도전자