[Python] 문자열 정렬 - 브루트 포스법/보이어·무어법

1. 브루트포스(Brute Force) 알고리즘

🔹 개념

브루트포스 알고리즘은 텍스트의 처음부터 끝까지 한 문자씩 비교하며 패턴을 찾는 방식이다. 가장 기본적인 문자열 검색 방법으로, 모든 경우를 일일이 확인하기 때문에 시간 복잡도는 O(nm)이다.

🔹 동작 방식

1. 텍스트(txt)의 첫 번째 문자부터 패턴(pat)과 비교를 시작한다.
2. 패턴의 첫 번째 문자부터 한 글자씩 비교한다.
3. 만약 불일치가 발생하면, 텍스트 커서를 한 칸 앞으로 이동하고 다시 비교를 시작한다.
4. 패턴이 완전히 일치하면 해당 위치를 반환한다.

🔹 코드 구현 (Python)

# 브루트포스 문자열 검색

def bf_match(txt: str, pat: str) -> int:
    n = len(txt)
    m = len(pat)
    
    for i in range(n - m + 1):  # 가능한 모든 위치에서 검사
        j = 0
        while j < m and txt[i + j] == pat[j]:  # 패턴과 비교
            j += 1
        if j == m:  # 패턴이 완전히 일치하면 위치 반환
            return i
    return -1  # 패턴이 발견되지 않음

---

2. 보이어-무어(Boyer-Moore) 알고리즘

🔹 개념

보이어-무어 알고리즘은 패턴의 마지막 문자부터 비교하며, 불일치 시 여러 칸을 건너뛸 수 있도록 최적화된 알고리즘이다. 일반적으로 O(n/m)에 가까운 성능을 내며, 긴 텍스트에서 특히 강력한 성능을 발휘한다.

🔹 동작 방식

1. 배드 문자 규칙(Bad Character Rule): 패턴의 마지막 문자가 불일치하면, 패턴 내에서 해당 문자의 위치를 찾아서 점프한다.
2. 굿 서픽스 규칙(Good Suffix Rule): 패턴의 일부가 일치했을 때, 그 부분을 재사용하여 점프한다.

🔹 불일치 시 점프 거리 계산

• 패턴에 포함되지 않는 문자를 만난 경우:
  • 패턴 내에 해당 문자가 없으면, 패턴의 길이(m)만큼 이동할 수 있다.
• 패턴에 포함된 문자를 만난 경우:
  • 패턴 내에서 해당 문자가 가장 오른쪽에 등장하는 위치로 이동한다.
    예를 들어, pat = "ABCD", txt = "XXXCXXX"라면, C는 패턴 내에서 세 번째 위치에 있으므로 3-2=1칸 이동한다.
  • 같은 문자가 패턴 안에서 중복해서 존재하지 않으면 역시나 패턴의 길이(m)만큼 이동한다.
    예를 들어 pat = "ABCD", txt = "XXXDXXX"라면 이동할 필요가 없으므로 이동량은 m이다.

🔹 코드 구현 (Python)

# 보이어-무어 문자열 검색

def preprocess_bad_character(pat: str):
    bad_char = {}
    m = len(pat)
    for i in range(m):
        bad_char[pat[i]] = i  # 가장 오른쪽에 등장하는 위치 저장
    return bad_char

def bm_match(txt: str, pat: str) -> int:
    bad_char = preprocess_bad_character(pat)
    n, m = len(txt), len(pat)
    s = 0  
    
    while s <= n - m:
        j = m - 1
        while j >= 0 and txt[s + j] == pat[j]:
            j -= 1
        
        if j < 0:
            return s
        
        shift = max(1, j - bad_char.get(txt[s + j], -1))
        s += shift
    
    return -1

🔹 코드 설명

1. preprocess_bad_character(pat: str)

   • 패턴 내의 각 문자에 대해 가장 오른쪽 위치를 기록하는 테이블을 만든다.
   • 예를 들어, pat = "ABCD"라면 { 'A': 0, 'B': 1, 'C': 2, 'D': 3 }가 된다.

2. bm_match(txt: str, pat: str) -> int

   • bad_char 테이블을 활용하여, 불일치가 발생하면 점프할 거리를 결정한다.
   • while j >= 0 and txt[s + j] == pat[j]에서 오른쪽에서부터 문자를 비교하며 일치하는 경우 j를 감소시킨다.
   • if j < 0:에서 j가 -1이 되면 패턴이 완전히 일치한 것이므로 s 반환.
   • shift = max(1, j - bad_char.get(txt[s + j], -1))에서 배드 문자 규칙을 적용하여 점프할 거리를 결정한다.

---

3. 알고리즘 비교 요약

알고리즘	시간 복잡도	방식	특징
브루트포스	O(nm)	처음부터 한 문자씩 비교	구현이 쉽지만 비효율적
보이어-무어	O(n/m) (평균)	패턴 끝에서부터 비교 & 점프	긴 텍스트에서 특히 빠름

✔ 보이어-무어는 건너뛰기를 최대화하여 빠르게 검색한다! 🚀