Brute-Force 알고리즘

요즘 이슈인 "이세돌 vs AlphaGo"에 관한 기사를 찾아 보다가 아래와 같은 기사를 보았다.

"모든 경우의 수를 다 탐색하는 알고리즘인 브루트 포스(Brute force)를 일종의 '훈수꾼'으로 사용해 100% 승리할 수밖에 없다."

(출처 : http://www.huffingtonpost.kr/)

보다보니깐 브루트 포스 알고리즘이 무얼까 궁금해서 한번 찾아봤다.

요 알고리즘은 어떻게 돌아갈까?

짜잔. 정의는 아래와 같다.

"길이가 n인 텍스트 T에서 길이가 m인 패턴 P를 찾는 간단한 방법"

그럼 이게 무슨 말일까?

예를 보자. 이게 과연 예일까?

T는 아래와 같은 문자열을 포함한 텍스트다.

0 0 0 1 0 0 1 0 1 1 1 0 1  ... 0 0 1

P의 패턴이 1 0 1 이라고 하면

T에서 1 0 1 이라는 패턴을 찾는 것이 포인트다!

정의를 그저 길게 쓴 느낌인데?

얘는 이렇게 동작한다고 한다.

1. P의 시작 패턴을  T에서 순차적으로 검색

2. 일치하는 패턴이 나오면 T의 연속된 다음 텍스트와 P의 다음 패턴을 비교

3. 일치하는 패턴이 안나오면 T의 연속된 다음 텍스트와 P의 첫 번째 패턴을 비교

4. 2번, 3번 반복

왠지 알고리즘 수업시간에 본 것 같은 알고리즘이다.

바로... sequential search!!

O(n)인 아주 단순한 알고리즘이다.

패턴이라는 것만 빼면 같은데??

그럼 Brute-Force 알고리즘의 복잡도는 어떻게 될까?

복잡도 계산법은 알고리즘 수업 시험을 봄과 동시에 머리에서 GC되서 기억이 안난다...

이런 경우가 최악이라고 한다.

T: 0 0 0 0 0 ... 0 0 0 1 일 때

P: 0 0 0 1 일 경우

즉, O(nm) 이 된다.

AlphaGo가 정말 Brute-Force 알고리즘을 이용하는지는 잘 모르겠지만

오늘 새로운 알고리즘을 하나 알게되서 신난다.

구현은 각자 좋아하는 언어로 해보는게 좋겠다.

(참고 : http://glocalit.skhu.ac.kr/~mckim1/Lecture/DS/dna/class12/class12_02.html#Top)