문자열 알고리즘 (String Algorithms)

핵심 인사이트 (3줄 요약)

문자열 패턴 매칭과 처리를 위한 고속 알고리즘. KMP, 라빈-카프, 보이어-무어가 핵심. O(n+m) 선형 검색으로 검색엔진·생물정보학의 기반.

📝 기술사 모의답안 (2.5페이지 분량)

📌 예상 문제

"문자열 알고리즘의 원리와 동작 과정을 설명하고, 유사 알고리즘과 비교하여 적합한 활용 시나리오를 기술하시오."

Ⅰ. 개요

1. 개념

문자열 알고리즘(String Algorithms)은 문자열의 검색, 매칭, 변환, 분석을 위한 알고리즘으로, 텍스트 처리, 검색 엔진, 생물정보학, 컴파일러 등 다양한 분야에서 핵심적으로 활용된다.

💡 비유: "Ctrl+F 찾기 기능" - 방대한 문서에서 특정 단어를 찾을 때 사용하는 기능의 원리

등장 배경:

1. 기존 문제점: 브루트 포스는 O(n×m)으로 대용량 텍스트에서 비효율적
2. 기술적 필요성: DNA 서열 분석, 검색 엔진 등에서 고속 패턴 매칭 필요
3. 시장 요구: 실시간 텍스트 처리, 침입 탐지 시스템 등 즉각적 검색 수요

핵심 목적: 선형 시간 O(n+m)으로 텍스트에서 패턴을 효율적으로 검색

Ⅱ. 구성 요소 및 핵심 원리

2. 패턴 매칭 알고리즘 구성 요소

3. 구조 다이어그램

┌─────────────────────────────────────────────────────────────┐
│               KMP 알고리즘 구조                              │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  텍스트 T:  [A][B][A][B][A][B][C][A][B][A][B]               │
│                ↓                                            │
│  패턴 P:    [A][B][A][B][C]                                │
│                                                             │
│  LPS 테이블 (Longest Proper Prefix = Suffix):               │
│  ┌─────────────────────────────────────────────────────┐   │
│  │ 인덱스:  0  1  2  3  4                               │   │
│  │ 패턴:   [A][B][A][B][C]                              │   │
│  │ LPS:    [0][0][1][2][0]                              │   │
│  └─────────────────────────────────────────────────────┘   │
│                                                             │
│  매칭 실패 시 LPS만큼 건너뜀 → 불필요한 비교 제거          │
│                                                             │
└─────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────┐
│               보이어-무어 알고리즘 구조                      │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  검색 방향: ← (오른쪽에서 왼쪽으로 비교)                    │
│                                                             │
│  Bad Character Rule:                                        │
│  텍스트:  ... [X][?][?][?][?]                               │
│  패턴:       [A][B][C][D][E]                                │
│                       ↑                                     │
│              불일치 발생 → X가 패턴에서 위치만큼 이동       │
│                                                             │
│  Good Suffix Rule:                                          │
│  일치한 접미사를 활용하여 더 많이 이동                     │
│                                                             │
└─────────────────────────────────────────────────────────────┘

4. 동작 원리 단계별 설명

KMP 알고리즘:

① LPS 테이블 생성 → ② 패턴 매칭 시작 → ③ 불일치 시 LPS 활용 → ④ 건너뛰기 → ⑤ 완료

• 1단계: 패턴의 각 위치에서 가장 긴 고유 접두사=접미사 길이 계산
• 2단계: 텍스트과 패턴을 왼쪽부터 순차 비교
• 3단계: 불일치 발생 시 LPS 테이블 참조
• 4단계: 이미 매칭된 접두사만큼 패턴 이동 (텍스트 포인터는 되돌아가지 않음)
• 5단계: 모든 매칭 위치 반환

5. Python 코드 예시

from typing import List, Tuple

# ==================== KMP 알고리즘 ====================

def compute_lps(pattern: str) -> List[int]:
    """
    LPS(Longest Proper Prefix which is also Suffix) 테이블 계산

    Args:
        pattern: 검색할 패턴 문자열

    Returns:
        LPS 테이블 (각 위치에서의 최장 일치 접두사=접미사 길이)

    예시: "ABABC" → [0, 0, 1, 2, 0]
    """
    m = len(pattern)
    lps = [0] * m
    length = 0  # 이전 위치까지의 최장 일치 길이
    i = 1

    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]  # 이전 LPS로 롤백
            else:
                lps[i] = 0
                i += 1

    return lps


def kmp_search(text: str, pattern: str) -> List[int]:
    """
    KMP 알고리즘으로 패턴 검색

    시간복잡도: O(n + m)
    공간복잡도: O(m)

    Returns:
        패턴이 발견된 모든 시작 인덱스 리스트
    """
    n, m = len(text), len(pattern)

    if m == 0 or m > n:
        return []

    lps = compute_lps(pattern)
    matches = []

    i = 0  # 텍스트 인덱스
    j = 0  # 패턴 인덱스

    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1

            if j == m:  # 완전 매칭
                matches.append(i - j)
                j = lps[j - 1]  # 계속 검색
        else:
            if j != 0:
                j = lps[j - 1]  # LPS만큼 점프
            else:
                i += 1

    return matches


# ==================== 라빈-카프 알고리즘 ====================

def rabin_karp_search(text: str, pattern: str,
                       base: int = 256,
                       prime: int = 101) -> List[int]:
    """
    라빈-카프 알고리즘: 해시 기반 패턴 매칭

    시간복잡도: 평균 O(n + m), 최악 O(n × m)
    공간복잡도: O(1)

    다중 패턴 검색에 유리함
    """
    n, m = len(text), len(pattern)

    if m == 0 or m > n:
        return []

    matches = []
    h = pow(base, m - 1, prime)  # base^(m-1) mod prime

    # 초기 해시 계산
    pattern_hash = 0
    text_hash = 0

    for i in range(m):
        pattern_hash = (base * pattern_hash + ord(pattern[i])) % prime
        text_hash = (base * text_hash + ord(text[i])) % prime

    # 슬라이딩 윈도우
    for i in range(n - m + 1):
        # 해시가 일치하면 실제 비교
        if pattern_hash == text_hash:
            if text[i:i + m] == pattern:
                matches.append(i)

        # 다음 윈도우 해시 계산 (롤링 해시)
        if i < n - m:
            text_hash = (base * (text_hash - ord(text[i]) * h) +
                        ord(text[i + m])) % prime

            # 음수 해시 처리
            if text_hash < 0:
                text_hash += prime

    return matches


# ==================== 보이어-무어 알고리즘 ====================

def boyer_moore_search(text: str, pattern: str) -> List[int]:
    """
    보이어-무어 알고리즘: 오른쪽→왼쪽 비교

    시간복잡도: 평균 O(n/m), 최악 O(n × m)
    공간복잡도: O(k) - k는 알파벳 크기

    실제 응용에서 가장 빠른 성능
    """
    n, m = len(text), len(pattern)

    if m == 0 or m > n:
        return []

    # Bad Character 테이블
    bad_char = {}
    for i in range(m):
        bad_char[pattern[i]] = i

    matches = []
    s = 0  # 패턴의 시작 위치

    while s <= n - m:
        j = m - 1  # 패턴의 오른쪽 끝부터 비교

        # 오른쪽에서 왼쪽으로 비교
        while j >= 0 and pattern[j] == text[s + j]:
            j -= 1

        if j < 0:  # 매칭 발견
            matches.append(s)
            # 다음 위치 계산
            s += m - bad_char.get(text[s + m], -1) if s + m < n else 1
        else:
            # Bad Character Rule 적용
            bc_shift = j - bad_char.get(text[s + j], -1)
            s += max(1, bc_shift)

    return matches


# ==================== 접미사 배열 ====================

def build_suffix_array(text: str) -> List[int]:
    """
    접미사 배열 생성 (O(n log² n) 구현)

    모든 접미사를 사전순으로 정렬한 인덱스 배열
    """
    n = len(text)
    suffixes = [(text[i:], i) for i in range(n)]
    suffixes.sort()
    return [idx for _, idx in suffixes]


def build_lcp_array(text: str, suffix_array: List[int]) -> List[int]:
    """
    LCP(Longest Common Prefix) 배열 생성

    인접한 접미사 쌍의 최장 공통 접두사 길이
    Kasai 알고리즘: O(n)
    """
    n = len(text)
    rank = [0] * n

    # 역순 매핑: 위치 → 접미사 배열 내 순위
    for i, sa_idx in enumerate(suffix_array):
        rank[sa_idx] = i

    lcp = [0] * (n - 1)
    h = 0

    for i in range(n):
        if rank[i] == 0:
            continue

        j = suffix_array[rank[i] - 1]

        while i + h < n and j + h < n and text[i + h] == text[j + h]:
            h += 1

        lcp[rank[i] - 1] = h

        if h > 0:
            h -= 1

    return lcp


# ==================== 테스트 및 검증 ====================

if __name__ == "__main__":
    text = "ABABDABACDABABCABAB"
    pattern = "ABABCABAB"

    print("=" * 50)
    print("문자열 패턴 매칭 알고리즘 테스트")
    print("=" * 50)
    print(f"텍스트: {text}")
    print(f"패턴: {pattern}")
    print()

    # KMP
    kmp_result = kmp_search(text, pattern)
    print(f"KMP 검색 결과: {kmp_result}")

    # LPS 테이블 확인
    print(f"LPS 테이블: {compute_lps(pattern)}")

    # 라빈-카프
    rk_result = rabin_karp_search(text, pattern)
    print(f"라빈-카프 검색 결과: {rk_result}")

    # 보이어-무어
    bm_result = boyer_moore_search(text, pattern)
    print(f"보이어-무어 검색 결과: {bm_result}")

    # 접미사 배열
    test_text = "banana"
    sa = build_suffix_array(test_text)
    lcp = build_lcp_array(test_text, sa)
    print(f"\n'{test_text}'의 접미사 배열: {sa}")
    print(f"LCP 배열: {lcp}")

Ⅲ. 기술 비교 분석

6. 장단점 분석

7. 대안 기술 비교

★ 선택 기준:

• 단일 패턴, 안정적 성능 → KMP
• 다중 패턴 동시 검색 → 라빈-카프 또는 Aho-Corasick
• 일반 텍스트 검색(평균 최고 속도) → 보이어-무어
• 반복 패턴, 생물정보학 → 접미사 배열/트리

8. 응용 구조 비교

Ⅳ. 실무 적용 방안

9. 실무 적용 시나리오

10. 실제 기업/서비스 사례

• Google 검색: 역인덱스 + 트라이 구조로 수십억 문서에서 밀리초 내 검색
• ClamAV: Aho-Corasick으로 수백만 개 바이러스 시그니처 동시 탐지
• BLAST(NCBI): 시퀀스 정렬에 KMP 변형 + 접미사 배열 활용
• grep/ripgrep: 보이어-무어 변형으로 대용량 파일 고속 검색

11. 도입 시 고려사항

1. 기술적:

   • 패턴 길이와 텍스트 크기에 따른 알고리즘 선택
   • 메모리 제약 시 라빈-카프 고려
   • 유니코드/멀티바이트 문자 처리

2. 운영적:

   • 다중 패턴 업데이트 빈도에 따른 구조 선택
   • 실시간 vs 배치 처리 요구사항

3. 보안적:

   • ReDoS(정규표현식 DoS) 방지를 위한 입력 검증
   • 패턴 주입 공격 방지

4. 경제적:

   • 오픈소스 라이브러리 활용 (PCRE, Hyperscan)

12. 주의사항 / 흔한 실수

• ❌ Unicode 문자를 바이트 단위로 처리 → 문자 경계 오류
• ❌ 라빈-카프에서 소수 선택 미흡 → 해시 충돌 빈발
• ❌ 보이어-무어에서 Good Suffix Rule 미구현 → 성능 저하
• ❌ 대소문자 구분 처리 누락 → 매칭 실패

13. 관련 개념

📌 문자열 알고리즘 핵심 연관 개념 맵

┌─────────────────────────────────────────────────────────────────┐
│  [정규표현식] ←──→ [문자열 알고리즘] ←──→ [접미사 구조]        │
│       ↓                  ↓                  ↓                  │
│  [컴파일러]         [트라이]          [생물정보학]              │
│                           ↓                                     │
│                      [검색엔진]                                  │
└─────────────────────────────────────────────────────────────────┘

Ⅴ. 기대 효과 및 결론

14. 정량적 기대 효과

15. 미래 전망

1. 기술 발전 방향:

   • SIMD/벡터화를 활용한 병렬 패턴 매칭 (Hyperscan)
   • GPU 기반 고속 문자열 처리

2. 시장 트렌드:

   • AI 기반 자연어 처리와 결합
   • 실시간 로그 분석/보안 탐지 수요 증가

3. 후속 기술:

   • 양자 문자열 검색 알고리즘
   • 근사 문자열 매칭 (Fuzzy Matching)

결론: 문자열 알고리즘은 텍스트 처리의 핵심 기술로, KMP/라빈-카프/보이어-무어의 적절한 선택이 성능을 결정한다. 다중 패턴 검색에는 Aho-Corasick, 반복 패턴 분석에는 접미사 구조가 필수적이다.

※ 참고 표준: CLRS 'Introduction to Algorithms', IEEE POSIX 정규표현식, Unicode Standard

어린이를 위한 종합 설명

문자열 알고리즘을 쉽게 이해해보자!

문자열 알고리즘은 마치 숨은그림찾기와 같아요. 커다란 그림(텍스트)에서 작은 그림(패턴)을 찾을 때, 처음부터 끝까지 한 칸씩 다 보는 것보다 똑똑하게 찾는 방법이 있어요.

첫째, KMP는 "이미 본 건 다시 안 봐도 돼!"라는 원리예요. 패턴의 앞부분과 뒷부분이 같은 걸 미리 계산해두면, 틀렸을 때도 처음으로 돌아가지 않고 중간부터 다시 시작할 수 있어요. 마치 암기카드로 외운 내용은 다시 안 외워도 되는 것과 같아요.

둘째, 보이어-무어는 "뒤에서부터 확인하기"예요. 마지막 글자가 틀리면 앞부분은 볼 필요가 없어요. 한 번에 많이 건너뛸 수 있어서 실제로 가장 빨라요. 마치 숙제할 때 답부터 확인하고 풀면 빠른 것과 비슷해요.