1/26
Loading...
🔍패턴 찾기 문제
📝 오늘의 문제 텍스트: "HELLO WORLD HELLO" 찾을 패턴: "HELLO" 🎯 목표: 텍스트에서 패턴이 어디에 나타나는지 찾기! ❌ 단순한 방법: 모든 위치에서 5글자씩 비교 → 최악의 경우 O(n×m) = 많은 비교 필요 ✅ 더 빠른 방법이 있습니다!
Loading...
📝 오늘의 문제 텍스트: "HELLO WORLD HELLO" 찾을 패턴: "HELLO" 🎯 목표: 텍스트에서 패턴이 어디에 나타나는지 찾기! ❌ 단순한 방법: 모든 위치에서 5글자씩 비교 → 최악의 경우 O(n×m) = 많은 비교 필요 ✅ 더 빠른 방법이 있습니다!
문자열 해싱(String Hashing)은 문자열을 고유한 숫자(해시값)로 변환하는 기법입니다. 다항식 해시 공식: hash = (c[0]×p^(n-1) + c[1]×p^(n-2) + ... + c[n-1]) mod m 여기서 c[i]는 문자의 ASCII 코드, p는 기본값(보통 31), m은 큰 소수입니다. 롤링 해시를 사용하면 윈도우가 한 칸 이동할 때 O(1)에 새 해시를 계산할 수 있어, 패턴 매칭에서 O(n+m) 시간복잡도를 달성합니다!