[알고리즘] Week 8: 고급 문자열 알고리즘 - 문자열 검색 알고리즘

Day 1: 고급 문자열 알고리즘 소개

• 강의 내용:
  • 문자열 알고리즘의 중요성
    • 문자열 알고리즘의 다양한 응용 사례
    • 문자열 검색의 필요성
  • 문자열 검색 알고리즘의 개요
    • 패턴 매칭 문제 정의
    • 다양한 문자열 검색 알고리즘 소개
• 실습:
  • 간단한 문자열 검색 예제

# 간단한 문자열 검색 예제
def naive_search(pattern, text):
    M = len(pattern)
    N = len(text)

    for i in range(N - M + 1):
        j = 0
        while j < M and text[i + j] == pattern[j]:
            j += 1
        if j == M:
            print("패턴 발견: 인덱스", i)

# 예제 실행
text = "AABAACAADAABAABA"
pattern = "AABA"
naive_search(pattern, text)

 

Day 2: KMP 알고리즘 (Knuth-Morris-Pratt Algorithm)

• 강의 내용:
  • KMP 알고리즘의 개념
    • KMP 알고리즘이란 무엇인가?
    • KMP 알고리즘의 동작 원리
  • KMP 알고리즘의 시간 복잡도
    • 시간 복잡도: O(N + M) (N: 텍스트 길이, M: 패턴 길이)
  • KMP 알고리즘의 주요 개념
    • 접두사 함수 (Prefix Function)
• 실습:
  • 파이썬을 사용한 KMP 알고리즘 구현 및 예제

# KMP 알고리즘 구현
def kmp_search(pattern, text):
    def compute_lps(pattern):
        lps = [0] * len(pattern)
        length = 0
        i = 1

        while i < len(pattern):
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        return lps

    M = len(pattern)
    N = len(text)
    lps = compute_lps(pattern)
    i = 0
    j = 0

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

        if j == M:
            print("패턴 발견: 인덱스", i - j)
            j = lps[j - 1]
        elif i < N and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

# 예제 실행
text = "AABAACAADAABAABA"
pattern = "AABA"
kmp_search(pattern, text)

 

Day 3: 보이어-무어 알고리즘 (Boyer-Moore Algorithm)

• 강의 내용:
  • 보이어-무어 알고리즘의 개념
    • 보이어-무어 알고리즘이란 무엇인가?
    • 보이어-무어 알고리즘의 동작 원리
  • 보이어-무어 알고리즘의 시간 복잡도
    • 평균 시간 복잡도: O(N/M)
    • 최악의 시간 복잡도: O(NM)
  • 보이어-무어 알고리즘의 주요 개념
    • 불일치 이동 규칙 (Mismatch Heuristic)
    • 좋은 접미사 이동 규칙 (Good Suffix Heuristic)
• 실습:
  • 파이썬을 사용한 보이어-무어 알고리즘 구현 및 예제

# 보이어-무어 알고리즘 구현
def boyer_moore_search(pattern, text):
    def bad_char_heuristic(pattern):
        bad_char = [-1] * 256
        for i in range(len(pattern)):
            bad_char[ord(pattern[i])] = i
        return bad_char

    def good_suffix_heuristic(pattern):
        M = len(pattern)
        good_suffix = [0] * M
        border = [0] * (M + 1)
        i = M
        j = M + 1
        border[i] = j
        while i > 0:
            while j <= M and pattern[i - 1] != pattern[j - 1]:
                if good_suffix[j] == 0:
                    good_suffix[j] = j - i
                j = border[j]
            i -= 1
            j -= 1
            border[i] = j
        j = border[0]
        for i in range(M + 1):
            if good_suffix[i] == 0:
                good_suffix[i] = j
            if i == j:
                j = border[j]
        return good_suffix

    bad_char = bad_char_heuristic(pattern)
    good_suffix = good_suffix_heuristic(pattern)
    M = len(pattern)
    N = len(text)
    s = 0

    while s <= N - M:
        j = M - 1
        while j >= 0 and pattern[j] == text[s + j]:
            j -= 1
        if j < 0:
            print("패턴 발견: 인덱스", s)
            s += good_suffix[0]
        else:
            s += max(good_suffix[j + 1], j - bad_char[ord(text[s + j])])

# 예제 실행
text = "ABAAABCD"
pattern = "ABC"
boyer_moore_search(pattern, text)

 

Day 4: 라빈-카프 알고리즘 (Rabin-Karp Algorithm)

• 강의 내용:
  • 라빈-카프 알고리즘의 개념
    • 라빈-카프 알고리즘이란 무엇인가?
    • 라빈-카프 알고리즘의 동작 원리
  • 라빈-카프 알고리즘의 시간 복잡도
    • 평균 시간 복잡도: O(N + M)
    • 최악의 시간 복잡도: O(NM)
  • 라빈-카프 알고리즘의 주요 개념
    • 해싱 (Hashing)과 롤링 해시 (Rolling Hash)
• 실습:
  • 파이썬을 사용한 라빈-카프 알고리즘 구현 및 예제

# 라빈-카프 알고리즘 구현
def rabin_karp_search(pattern, text, q):
    d = 256
    M = len(pattern)
    N = len(text)
    p = 0
    t = 0
    h = 1

    for i in range(M - 1):
        h = (h * d) % q

    for i in range(M):
        p = (d * p + ord(pattern[i])) % q
        t = (d * t + ord(text[i])) % q

    for i in range(N - M + 1):
        if p == t:
            match = True
            for j in range(M):
                if text[i + j] != pattern[j]:
                    match = False
                    break
            if match:
                print("패턴 발견: 인덱스", i)
        if i < N - M:
            t = (d * (t - ord(text[i]) * h) + ord(text[i + M])) % q
            if t < 0:
                t = t + q

# 예제 실행
text = "GEEKS FOR GEEKS"
pattern = "GEEK"
q = 101  # 해시 함수로 사용할 소수
rabin_karp_search(pattern, text, q)

 

Day 5: 고급 문자열 알고리즘 종합 연습

• 강의 내용:
  • 종합 연습 문제 풀이
    • KMP, 보이어-무어, 라빈-카프 알고리즘을 활용한 종합 문제
  • 고급 문자열 알고리즘의 응용
    • 다양한 실생활 문제에서의 응용 사례
• 실습:
  • 종합 연습 문제 해결 및 결과 분석

### 종합 연습 문제 예시
1. 주어진 텍스트에서 KMP 알고리즘을 사용하여 패턴을 검색하세요.
2. 주어진 텍스트에서 보이어-무어 알고리즘을 사용하여 패턴을 검색하세요.
3. 주어진 텍스트에서 라빈-카프 알고리즘을 사용하여 패턴을 검색하세요.

 

Day 6: 프로젝트 준비

• 강의 내용:
  • 프로젝트 주제 선정 및 요구사항 분석
    • 프로젝트 주제 및 요구사항 확정
    • 프로젝트 설계 및 계획 수립
  • 프로젝트 구현 준비
    • 데이터 구조 및 알고리즘 설계
    • 프로젝트 팀 구성 및 역할 분담
• 실습:
  • 프로젝트 주제 및 요구사항 분석
  • 프로젝트 설계 및 계획 수립

### 프로젝트 주제 예시
1. 대규모 텍스트 데이터 검색 엔진 개발
2. 실시간 텍스트 패턴 매칭 시스템

### 프로젝트 요구사항 예시
1. 대규모 텍스트 데이터 검색 엔진:
   - 대규모 텍스트 데이터셋 입력 및 저장
   - 고급 문자열 알고리즘을 통한 패턴 매칭
   - 검색 결과 출력 및 성능 분석

### 프로젝트 설계 및 계획 예시
1. 데이터 입력 모듈 구현
2. 고급 문자열 알고리즘 구현 (KMP, 보이어-무어, 라빈-카프 등)
3. 데이터 출력 및 성능 분석 모듈 구현

 

이 강의는 파이썬의 고급 문자열 알고리즘, 특히 문자열 검색 알고리즘 (KMP, 보이어-무어, 라빈-카프)의 기본 개념과 구현을 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!