완전탐색 - 브루트 포스
브루트 -> brute
한마디로 정리하면 무식하게 힘으로 밀어 붙인다는 소리다.
브루트 포스는 간단하다. 모든 경우를 다 직접 해 본다.
-끝-
이라고 끝내면 섭섭하니 예를 하나 보자.
10자리 텍스트가 있다고 보자.
ABABCDEFGHA
이 글자에서 패턴 ABC가 있나 찾아보자.
'ABA'BCDEFGHA
-> ABA
A'BAB'CDEFGHA
-> BAB
AB'ABC'DEFGHA
-> ABC
감이 오는가? 하나하나 일일이 다 대입해보고 찾아보는거
그게 브루트 포스이다.
근데 이렇게만 찾다보면 시간도 낭비가 되고 컴퓨터가 갈려나갈것이다.
그래서 여러 사람들이 머리를 짜내었다.
KMP법
ZABCABXACCADEF에서 패턴 ABCABD를 찾는다고 해 보자.
처음은 브루탈포스와 같다.
'ZABCAB'XACCADEF
ZABCAB
Z'ABCABX'ACCADEF
ABCABX
자, 여기서 생각을 잠시 해보자. 브루탈 포스였으면 그냥 밀고나가겠지만
우리는 조금 더 효율적인 방법을 찾고 있다.
우리가 찾고자 하는 패턴을 잘 살펴보면
ABCABD
그렇다. AB가 2번 반복되고 있다.
그리고 우리가 비교해본 글자도 살펴보자.
ABCABX
감이 오는가? 여기도 AB가 반복되고 있다.
그러니까 우리는
'뒤쪽 AB에서부터 찾아도 상관없겠네?' 라는 생각에 도달하게 된다.
즉 어차피 3번째, 4번째 글자부터 비교를 해 보아도
어차피 글자가 B,C로 시작하기 때문에 비교를 하는거 자체가 낭비라는 소리다.
그래서 뒤쪽 AB에서부터 대조를 시작하면
ZABC'ABXACC'ADEF
ABXACC
부터 대조를 하면 된다.
이후에도 위와 같이 AB로 시작되는 부분이 뒤에서 나온다면
그쪽부터 하면 된다.
추가)
알고리즘으로 구현 해 보았다. 알고리즘 카테고리에 글 하나 있을것이다.
이만큼 무시무시한놈인줄은 몰랐는데, 시간이 없다면 구현하는건 비추천한다.
보이어/무어법
이건 좀 독특하다.
일단 패턴을 한번 살펴보자.
APPLE
어떤글자가 들어있는가?
A,E,L,P가 들어있다.
여기서 한번 잠시 생각해보자.
만약에 비교해야하는 텍스트 중에
특정부분에 K라는 글자가 있다.
우리가 과연 이 K라는 글자를 비교해야될까?
그래서 우리 보이어/무어 형님들은 그냥 깔끔하게 넘겨버리기로 했다.
다시 정리를 하자면
1. 보이어/무어는 마지막 글자에 집중한다. APPLE패턴을 예로 들면 E와 대조되는 텍스트를 의미한다.
2. E와 대조되는 텍스트가 만약 패턴에 포함되지 않으면, 오른쪽으로 n만큼 민다. APPLE의 경우는 글자가 5개니까 오른쪽으로 5칸을 밀면 된다.
3. E와 대조되는 텍스트가 만약 패턴에 포함된다면, 오른쪽에서 가장 가까운 글자까지 민다.
만약 P가 E와 대조가 되었다면, 오른쪽으로 2칸 밀어 E와 가까운 P와 대조시킨다.
뭔가 복잡한거 같은데 한번 이해하면 괜찮은거 같다.
이분탐색 - binary search
정렬된 리스트에서 원하는 숫자를 찾을때 쓰는 방식이다.
정말 간단하면서도 강력한 방법이다. 무려 시간복잡도가 logn이다.
간단하게 설명하면 업다운 게임이다.
리스트가 정렬되었기 때문에 어떠한 값을 선택하더라도 이게 배열에서 어느정도 크기의 숫자인지 가늠이 가능하다.
한번 더 적어보자면 배열에서 list[0]은 가장 작은 값일것이고, list[max]는 가장 큰 값일것며 list[max/2]는 중간값일것이다.
그래서 binary search는 일단 중간을 찍고본다.
예시를 보면서 알아보자.
리스트 a[]는 7개의 값을 가지고 있다.
그럼 우리의 탐색기는 a[3]를 찍는다. 리스트의 중간이다.
그럼 값이 나온다. 50이란다. 근데 우리가 찾을려는 값보다 작네?
다음은 어디로 찍어야될까?
그렇다. 4에서 6의 중간값, 5를 찍으면 된다.
이번에는 a[5]를 찍어보자. 75가 나왔다.
근데 이번에는 이것보다는 작다네?
3보단 크고 5보다 작은 수는? -> 4밖에 없다.
a[4]를 찍어보자. 원하는 수인 60이 나왔다.
이처럼 7개의 숫자 중 어느것이든 랜덤으로 골라도
확정적으로 3번만에 정답을 찾아낼 수 있는 놀라운 방법이다.
