(Brute Force) 브루트포스 알고리즘 - 문자열 패턴 매칭

포스팅에서 다룰 브루트 포스 Brute Force 알고리즘은 비교 대상 문자열을 처음부터 끝까지 모두 순회하면서 비교하기 때문에 고지식한 알고리즘이라고도 불리는 문자열 패턴 매칭 알고리즘입니다. Brute Force 시간 복잡도, 장단점, 알고리즘 파이썬 구현에 대해 알아보겠습니다.

 

브루트 포스란? (Brute Force)

검색 대상이 되는 원본 문자열의 처음부터 끝까지 차례대로 순회하며 문자들을 일일이 비교하는 방식의 고지식한 알고리즘입니다.

비교하고자 하는 문자열과 패턴을 한 칸씩 이동하면서 비교하여 일치 여부를 확인합니다.

 

Brute Force 비교 과정

T: 원본 문자열 / P: 찾고자 하는 문자열 패턴

 

1. T, P 모두 첫 문자부터 비교를 시작하므로 검색 인덱스를 맨 처음 인덱스로 설정합니다.
2. 각각의 검색 인덱스부터 하나씩 문자를 비교합니다.
   1. 비교 문자가 같으면 T, P의 인덱스 모두 뒤로 한 칸씩 이동합니다.
   2. 비교 문자가 다르면 T의 인덱스는 한 칸 뒤로 이동하고, P의 인덱스는 맨 처음 인덱스로 돌아갑니다.
3. 다시 2번 과정부터 검색이 끝날 때까지 반복합니다.

시간 복잡도와 장단점

• 시간 복잡도: O(mn)
• 찾으려는 문자열 패턴의 길이 m, 총 문자열 길이 n
• 장점: 구현이 쉬운 편이고, 100%의 확률로 정답을 출력합니다.
• 단점: 모든 자료를 탐색하므로 시간적으로 매우 비효율적입니다.

브루트 포스 알고리즘 파이썬 코드

•  비교 대상 문자열의 끝까지 비교하거나, 패턴을 찾을 때까지 반복해서
• 문자를 하나씩 차례로 비교합니다.
• 원본 문자열에서 패턴이 속한 시작 위치를 반환합니다.

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

pattern = "Python"
text = "Hello Python World"
print(BruteForce(pattern, text))

 

더 효율적인 알고리즘 공부하기 >>

(Boyer Moore) 보이어 무어 알고리즘 - 문자열 패턴 매칭

(Boyer Moore) 보이어 무어 알고리즘 - 문자열 패턴 매칭

---

Brute Force 브루트 포스 알고리즘 파이썬으로 구현해보고, brute force 알고리즘 시간 복잡도, 장단점, 비교 과정까지 알아보았습니다.