완전탐색(Exhaustive Search), 이분탐색(Binary Search)

완전탐색(Exhaustive Search)

brute force로 밖에 풀 수 없는 문제로 유명한 knapsack algorithm (출처 : https://en.wikipedia.org/wiki/Knapsack_problem)

완전 탐색은 어떠한 문제를 풀기위해 사용하는 검색 알고리즘을 말하는데 이 방법은 주어진 모든 데이터를 하나하나 살펴보며 목표값을 찾아내는 알고리즘이다. 방법이 무식하기도하고 단순하여 'Brute Force'라고도 하기도 한다. 

이러한 완전탐색을 하는데 사용하는 방법은 5가지로 주로 알려져 있다.

1. Brute Force
2. 순열(Permutation)
3. 재귀(Recursion)
4. 비트마스크(Bit Mask)
5. 넓이탐색과 깊이탐색(BFS, DFS)

장점:

장점이라고 본다면 모든 데이터를 확인하는 것이기 때문에 "충분한 시간만 주어진다면" 못 푸는 문제가 없다는 것이다.

예를 들어 비밀번호가 6자리인 금고를 여는 문제를 brute force를 이용하여 해결할 때, 이 방법을 사용하면 000000부터 시작해서 999999까지 하나하나 확인하고 기여코 비밀번호를 알아낼 것이다.

단점:

단점은 바로 이런 문제를 해결 하는데 있어 '시간'이 너무 오래 걸린다는 것이다. 만약 N개의 정수로 이루어진 배열이 있고, 그 배열안에서 두개의 숫자를 더했을 때, 최대값이 무엇이 나오는 지 알아내는 문제를 풀게 될경우에 위의 방법을 통해 하나의 정수를 그 외 모든 정수와 일일이 더해보는 방법을 사용하게 된다면 시간복잡도가 O(n^2)가 된다. 이는 데이터의 양이 많아질 수록 걸리는 시간이 제곱만큼 늘어나므로 결코 좋은 알고리즘이라고는 볼 수 없다. 

 

---

이분탐색(Binary Search)

(출처 : https://realpython.com/binary-search-python/)

이분탐색은 배열에서 하나의 데이터를 찾기위해 사용하는 탐색기법으로 배열의 가운데 데이터를 참조하여 찾고자 하는 값이 해당 데이터보다 크거나 작음에 따라 왼쪽, 오른쪽으로 가서 그 부분의 절반에서 같은 방법으로 비교함으로써 접근해가는 검색기법이다. 이 이진탐색을 사용하기 위해서는 먼저 배열은 정렬되어 있어야 한다.

예를 들어 정렬되어 있는 정수들이 저장된 배열 X가 

[0, 2, 7, 10, 15, 16, 18, 21, 22, 28, 34, 50, 94, 133]

이렇게 있다고 하고 우리는 34를 찾고자 한다면 먼저 우리는 배열길이 14의 절반인 7번째 배열값을 참조한다.

X의 7번째 값은 21이 된다. 이때 21은 34보다 작으므로 우리는 21를 포함해 왼쪽은 없다고 생각하고 같은 방법을 계속한다.

22, 28, 34, 50, 94, 133]

이때 우리는 가운데 값 50을 가지고 34와 비교하게 되고, 50이 더 크므로 50의 왼쪽에서 탐색을 계속한다. 

22, 28, 34

28은 34보다 작으므로 오른쪽에서 다시 찾게 되며

34

우리가 원했던 값인 34를 찾게 되는 것이다.

 

이 방법을 쓰는 이유:

물론 평범하게 값을 0번부터 찾아갈 수도 있다. 하지만 그럴때의 시간 복잡도는 O(n)이 나오는 데 이렇게 된다면 만약 100만개의 값 사이에서 하나의 값을 찾으려고 하는데 또 하필 찾고자 하는 값이 배열의 마지막에 있다면 우리는 100만번의 연산을 시행할 수 밖에 없다.

하지만 이 이분탐색을 통해서 한 연산이 이루어 질 때마다 탐색범위의 절반을 날릴 수 있기 때문에 만약 똑같이 가장 뒤에 찾게 된다하더라도 20번의 연산도 걸리지 않게 된다. 참고로 이분탐색의 시간복잡도는 O(log n)이다.