오늘 살펴볼 예제는 가장 중요하고 핵심적인 알고리즘 중에 하나인 검색(Search) 알고리즘입니다. 가장 간단하게 Linear Search와 Binary Search에 대해서 살펴보려고 합니다.
Linear Search는 우리가 생각할 수 있는 가장 쉬운 검색 방법입니다. 바로 처음부터 끝까지 쭈욱 비교하면서 검색하고자 하는 원소가 있는지 찾아보는 것이지요. 가장 구현하기 쉽고, 또한 명확한 결과를 낼 수 있는 쉬운 방법이지만, 역시 성능은 기대에 미치지 못합니다. 이 알고리즘의 complexity는 이 됩니다.
#A에서 n을 찾으면 가장 처음 등장하는 index를 리턴
#못찾으면 -1을 리턴
def linearSearch(A, n):
for i in range(len(A)):
if A[i] == n:
return i
return -1
>>> linearSearch([1,2,3,4,5], 4)
3
>>> linearSearch([1,2,3,4,5], 6)
-1
>>> linearSearch([1,2,4,5], 3)
-1결과가 잘 나옴을 확인할 수 있죠? ^^ 이제 조금 더 향상된 방법의 검색에 대해서 알아봅시다. 이는 Binary Search 방법인데요, 가장 중요한 전제조건은 반드시 검색하고자 하는 List가 정렬된 상태여야 한다는 점입니다!! 정렬이 되어있지 않다면 사실상 이 방식은 적용할 수가 없게 됩니다. 또는 linear search와 다를 바가 없습니다.
알고리즘은 처음부터 찾는 것이 아니라, 가운데들을 찾아나가는 방식입니다. 예를 들어, [1,2,3,4,5] 의 집합에서 찾는다고 가정을 할 때, 처음에 3과 비교를 하여 맞는지 확인을 하고, 찾으려는 수가 3보다 작으면 [1,2]에서 다시 찾아보고, 3보다 크면 [4,5]에서 다시 찾아보는 방식입니다. 이렇게 하면 complexity가 으로 확 줄어드는 것을 확인할 수 있죠?
# A는 반드시 오름차순으로 정렬 되어 있어야 합니다.
# A가 오름차순으로 되어있다고 가정하고 짭니다.
def binarySearch(A, n):
if n < A[0] or n > A[-1]:
return -1
left, right = 0, len(A)-1
while left <= right:
middle = (left + right) / 2
if A[middle] == n:
return middle
elif A[middle] > n:
right = middle-1
else:
left = middle+1
return -1
>>> binarySearch([1,2,3,4,5], 4)
3
>>> binarySearch([1,2,3,4,5], 6)
-1
>>> binarySearch([1,2,4,5], 3)
-1이제 실제로 binary search 방식이 효율적인지를 확인해 봅시다.
>>> from time import time
>>> t0 = time()
>>> print linearSearch(range(1000000), 500000.5)
>>> print "걸린시간 : %.2e" % (time()-t0)
-1
걸린시간 : 1.51e-01
>>> t0 = time()
>>> print binarySearch(range(1000000), 500000.5)
>>> print "걸린시간 : %.2e" % (time()-t0)
-1
걸린시간 : 1.67e-02크기가 큰 집합일수록 binary search 방식의 효율성은 증가되겠죠? 굉장히 기본적이고 중요한 개념이니 한번씩 구현해 보시면 좋을 것 같습니다 :)