[개념] 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))