[Algorithms] 브루트 포스법(Brute Force Method)

깃허브: https://github.com/PSLeon24/DataStructure/blob/main/bruteForce.ipynb

브루트 포스법(Brute Force Method)

본 포스팅에서는 가장 기초적인 문자열 검색 알고리즘인 브루트 포스법을 알아보고자 한다.

브루트 포스법은 선형 검색을 단순하게 확장한 알고리즘이라서 '단순 비교 문자열 매칭 알고리즘'이라고도 한다.

 

예시를 통해 알아보기

A

B

A

B

C

D

E

F

G

H

자, "ABABCDEFGH"라는 문자열이 있다고 가정하자. 이때 우리가 찾고자 하는 문자열인 패턴은 "ABC"이다.

브루트 포스법에서는 어떻게 해당 문자열을 찾을까?

정답은 패턴 문자열의 첫문자부터 끝문자까지 반복하며 텍스트의 문자들과 각각 비교한다. 풀이를 통해 살펴보자.

 

Step 1. 텍스트와 패턴이 모두 일치하는지 비교한다.

- 일치한다면 O, 일치하지 않는다면 X

A	B	A	B	C	D	E	F	G	H
A(O)	B(O)	C(X)

이 경우, 'A'와 'B'는 일치하지만 마지막 'C'가 일치하지 않으므로 패턴을 오른쪽으로 1칸 밀어 다음 Step을 진행한다.

 

Step 2. 텍스트와 패턴이 모두 일치하는지 비교한다.

A	B	A	B	C	D	E	F	G	H
	A(X)	B	C

이 경우, 패턴의 첫 문자 'A'와 텍스트의 문자인 'B'가 일치하지 않으므로 패턴을 오른쪽으로 1칸 밀어 다음 Step을 진행한다.

 

Step 3. 텍스트와 패턴이 모두 일치하는지 비교한다.

A	B	A	B	C	D	E	F	G	H
		A(O)	B(O)	C(O)

패턴의 문자 'A', 'B', 'C'와 텍스트의 문자 'A', 'B', 'C'가 모두 일치하므로 검색에 성공한다.

 

따라서, 브루트 포스법을 진행하면 위와 같은 스텝(step)을 거치며 문자열을 검색함을 확인할 수 있다.

이제 위 과정을 더 잘게 쪼개서 면밀히 알아보자.

 

Step 1. 텍스트와 패턴이 모두 일치하는지 비교한다.

A	B	A	B	C	D	E	F	G	H
A	B	C
A(O)
	B(O)
		C(X)

Step1에서는 텍스트와 패턴의 첫 문자를 위아래로 나란히 놓고 첫 문자부터 차례로 검사한다. 문자가 일치하면 차례로 검사한다. 하지만 텍스트의 3번째 문자인 'A'와 패턴의 3번째 문자인 'C'가 일치하지 않으므로 더 이상 검사가 불필요하다고 판단하고 다음 Step을 진행한다.

 

Step 2. 텍스트와 패턴이 모두 일치하는지 비교한다.

A	B	A	B	C	D	E	F	G	H
	A	B	C
	A(X)
		B
			C

Step2에서는 패턴을 검사하는 시작 위치를 오른쪽으로 1칸 이동 시킨다. 그러고 나서 위의 과정과 같이 검사를 진행하는데 텍스트의 문자인 'B'와 패턴의 첫 문자인 'A'가 일치하지 않으므로 검사에 실패하고 다음 Step을 진행한다.

 

Step 3. 텍스트와 패턴이 모두 일치하는지 비교한다.

A	B	A	B	C	D	E	F	G	H
		A	B	C
		A(O)
			B(O)
				C(O)

Step3에서도 패턴을 검사하는 시작 위치를 오른쪽으로 1칸 이동 시킨다. 그러고 나서 위의 과정과 같이 차례대로 검사하면 패턴의 모든 문자가 텍스트와 일치한다. 따라서 검색에 성공한다.

 

이런 과정을 살펴보면 한 가지 문제점이 발생한다. 무엇일까?

Step1를 진행하고 나면 3번째 문자인 'A'까지는 패턴과 동일한 텍스트가 아님을 알 수 있지만, Step2를 진행할 때는 두 번째 문자부터 다시 검사하게 된다. 이렇게 이미 검사한 위치를 기억하지 못하는 브루트 포스법의 경우 텍스트의 길이가 m, 패턴의 길이가 n일 때, 시간 복잡도가 O(mn)으로, 비효율적이다. 따라서 이를 개선하기 위해 다음 포스팅에서 학습하게 될 'KMP법'과 같은 다른 문자열 검색 알고리즘이 등장하게 되었다.

 

파이썬으로 실습하기

실습 코드

출력 결과