brute_force

algorithms, brute_force

잡담

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

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

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

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

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

“길이가 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 이라는 패턴을 찾는 것이 포인트다!

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

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

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

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 알고리즘을 이용하는지는 잘 모르겠지만

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

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