[2024.02.06] String 2

에라토스테네스의 체

def sieve(N):
    """
    :return: N 이하의 모든 소수를 리스트로 반환하는 함수
    """
    # 1. 2부터 시작해서 연속된 정수들 중에서 아직 소수로 판별되지 않은 가장 작은 수를 찾는다. (소수 O)
    # 2. 그 수를 소수로 판별시키고, “그 수의 배수들은 모두 소수가 아니다!” 라고 판별한다.
    # 3. 1단계와 2단계 과정을 N 범위 내에서 계속 반복하면서 모든 소수를 판별한다.
    # 소수인지를 체크해두는 리스트를 하나 만듦 is_prime
    
    is_prime = [True] * (N + 1)
    
    # 0과 1은 소수가 아님!
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(N ** 0.5) + 1):
        # 아직 소수로 판별되지 않은 가장 작은 수를 찾는다. 그 수를 소수를 판별시킨다.
        if is_prime[i] == True:   # 소수이다!
            # 해당되는 소수를 가지고 그 수의 배수들은 모두 소수가 아니다라고 판별한다.
            for j in range(i * 2, N + 1, i):
                # 2배, 3배, 4배... (N까지)
                is_prime[j] = False
                
    # 소수인 값만 리스트로 만들어주기!
    primes = []
    for i in range(2, N + 1):
        if is_prime[i]:
            primes.append(i)
    
    return primes

N = 30
primes = sieve(N)
print(primes)

패턴 매칭에 사용되는 알고리즘들

• 고지식한 패턴 검색 알고리즘

p = 'is' #찾을 패턴
t = 'This is a book~!' #전체 텍스트
M = len(p) #찾을 패턴의 길이
N = len(t) #전체 텍스트의 길이

def BruteForce(p,t):
    i = 0 #t의 인덱스
    j = 0 #p의 인덱스
    while j < M and i < N:
        if t[i] != p[j]:
            i = i - j
            j = -1
        i = i + 1
        j = j + 1
    
    if j == M:
        return i - M #검색 성공
    else:
        return -1 #검색 실패

def f(pat, txt, M, N):
    for i in range(N-M+1): #text에서 비교 시작 위치
        for j in range(M):
            if txt[i+j ]!= pat[j]: #불일치면 다음 시작 위치로
                break
        else: #패턴 매칭에 성공하면
            return 1
    #모든 위치에서 비교가 끝난 경우
    return 0

T = int(input())
for tc in range(1, T+1):
    pat = input()
    txt = input()    
    M = len(pat)
    N = len(txt)
    
print(f(pat, txt, M, N))

• 카프-라빈 알고리즘

• KMP 알고리즘

def kmp(t, p):
    N = len(t)
    M = len(p)
    lps = [0] * (M+1)
    
    #전처리
    j = 0 #일치한 개수 == 비교할 패턴 위치
    lps[0] = -1
    for i in range(1, M):
        lps[i] = j #p[i] 이전에 일치한 개수
        if p[i] == p[j]: 
            j += 1
        else:
            j = 0
        
    lps[M] = j
    
    #검색
    i = 0 #비교할 텍스트 위치
    j = 0 #비교할 패턴 위치
    while i < N and j <= M:
        if j == -1 or t[i] == p[j]: #첫글자가 불일치했거나, 일치하면
            i += 1
            j += 1
        else: #불일치
            j = lps[j]
        if j == M: #패턴을 찾을 경우
            print(i-M, end=' ') #패턴의 인덱스 출력
            j = lps[j]
    
    print()
    return

t = 'zzzabcdabcdabcefabcd'
p = 'abcdabcef'
kmp(t, p)
t = 'AABAACAADAABAABA'
p = 'AABA'
kmp(t, p)
            

• 보이어-무어 알고리즘