[python] 손흥민을 찾아라! 선형탐색과 이분탐색 (Search)

TV조선뉴스

??? : 훠훠.. 손흉미니 어디가쒀 ..

문쌤이 찾으시는 손흥민이 어디있는지 찾아봅시다. 선수들이 일렬로 서있을때, 등번호순으로 서있다면 No.7 손흥민선수는 비교적 금방 찾을수있을겁니다. 이번엔 선수들을 섞어봅시다. 포지션별로 골키퍼-수비수-미드필더-공격수 순으로 서있다면? 공격수인 손흥민선수는 뒤쪽에 있겠죠. 제일 앞에서부터 한명씩 확인하기엔, 등번호 순대로 서있을때보다 오래걸릴겁니다.  이제는 선수들을 무작위로 섞어봅시다. 손흥민선수가 앞쪽에있다면 빨리 찾을수있을것이고, 뒤쪽에있다면 늦게찾을겁니다. 

 

오늘은 탐색의 기초. 선형탐색(Linear Search)과 이분탐색(Binary Search)에 대해 알아봅시다.

탐색은 말그대로, 많은 데이터가있는 자료에서 우리가 필요한 데이터를 찾는겁니다. 예를들어, 무작위 정수의 집합(리스트)에서 숫자 7을 탐색할때, 7이 리스트내에 있다면 해당 인덱스를 반환합니다. 만약 리스트안에 7이 없다면 -1을 출력합니다. 그럼 7이 중복된경우는? 가장 처음에 나타난 7의 인덱스를 반환합니다.. 요런느낌

 

선형탐색(Linear Search)는 위에서 손흥민선수를 찾았던것처럼, 앞에서부터 끝까지 검사합니다. 리스트의 처음부터 끝까지 target value가 나타날때까지 search를 하는겁니다. 무식해보여도 가장 확실한방법이죠. 컴퓨터의 속도를 고려했을때 충분히 해볼만한 방법입니다.

선형탐색 알고리즘을 그림으로 표현하면 위와같습니다. 코드구현은 리스트의 0번부터 target value와 일치하는지 검사합니다. 일치하지 않는다면 다음요소로, 일치한다면 루프를 빠져나오며 해당 인덱스값을 반환합니다. for혹은 while Loop을 이용하면 되겠네요

def linear_search(L_list,target_value):
    i=0
    
    while i<len(L_list) and L_list[i]!=target_value:
        i+=1

        if i==len(L_list):
            return -1

        elif L_list[i]==target_value:           
            return i
        
            break

while Loop를 이용해 구현한 선형탐색 알고리즘입니다. 함수의 head는 선수들의 정렬 list와 우리가 찾는 등번호 target_value를 변수로 설정합니다. while문은 리스트내 위치 i를 0부터 1씩키우며 탐색하는데 i가 리스트끝까지 가기전 혹은 target_value를 찾기전까지 동작합니다. 

 

똑같이 while Loop를 사용하지만 시간을 좀더 단축시키는 방법이 있습니다.

def linear_search(L_list,target_value):
    i=0
    L_list.append(target_value)
    
    while L[i]!=target_value:
        i+=1

        if i==len(L_list):
            return -1

        elif L_list[i]==target_value:           
            return i
        
            break
            
	L_list.pop()

while문 조건중 리스트의 끝을 제한하는 조건이 사라졌습니다. 리스트의 끝을 제한하는동작이 필요한이유는  'target value가 리스트안에 없는경우' 때문입니다. target value가 있는경우 while문은 동작을 멈추지만 없는경우에는 끝을모르고 계속 동작합니다. 

위의 개선된(?) while문의 경우 처음 시작할때 리스트의 맨 끝에 target value를 추가합니다. 이걸 Sentinel이라고합니다.

암튼 리스트에는 무조건 target value가 있는거고, target value를 찾을때까지 while문은 동작하죠. 만약 i의 위치가 리스트 끝이라면, 기존에 있던 리스트에는 target value가 없다는 얘기겠죠. 이땐 -1을 반환합니다.

while Loop가 끝나면 pop을 이용해 임의로 넣은 Sentinel을 빼줍시다. (리스트를 임의로 건드는것은 꽤나 위험한행동입니다.)

def linear_search(L_list,target_value):
	for i in range(len(L_list)-1):
    	if L[i]==target_value:
        	return i
            
    return -1

for문을 이용하면 다음과같이 구현할수있습니다. while문보다는 훨씬 간단하죠? 범위에 대한 조건자체를 for문이 담고있기에 간결합니다.

 

실행시켜서 시간을 재봅시다. while문 for문 시간비교하려는게 아니라, linear search의 약점을 설명하기위해 시간을 재봤읍니다.

import time

t_start=time.perf_counter()

def linear_search(L_list,target_value):
    i=0
    
    while i<len(L_list) and L_list[i]!=target_value:
        i+=1

        if i==len(L_list):
            return -1

        elif L_list[i]==target_value:
            return i

            break
            


lineup_list=[1,5,2,13,18,7,92,13]
num=7

k=linear_search(lineup_list,num)

print('손흥민선수는 %d번째에 있습니다'%k)
    
t_end=time.perf_counter()

print(t_end-t_start)

시간재는건 이전에 백준 수열의합 글에 설명해놨읍니다. 위 리스트에서 No.7 손흥민선수의 위치를 찾는겁니다.

lineup_list에서 7번 위치는 5번째가 맞죠. 실행시간은 위와같습니다. 

"이정도면 괜찮은데요?" -> 이건 근데 리스트가 매우 짧은예시이고.. 리스트를 좀더 늘여서 7번을 뒤에 위치시켜봅시다

손흥민선수 앞에 85명의 선수들을 추가시켜봤습니다. 실행시간이 꽤나 길어졌습니다. 

이제 실행시간이 눈에띄게 길어졌습니다. 

 

linear search의 단점이보이죠? 논리와 구현이 간단하지만, 리스트의 길이, target value의 리스트 내 위치의 영향을 크게받는다는겁니다. 리스트 내 value가 많을수록 linear search를 사용하긴 힘들어집니다.

 

다른 탐색방식을 도입해봅시다. 이번에 써볼건 이분탐색(binary search)입니다. 그러나 이분탐색을 하기위해선 먼저 선행 요구조건이 있습니다. 바로 정렬(Sort)입니다. 이분탐색은 정렬된 자료에서만 사용할수있습니다.

정렬은 별건아니고, 리스트 내 value가 오름차순 혹은 내림차순으로 정리하는 행위입니다. 예를들어 이전에 풀었던 백준문제중 binary search를 사용했던 경우를 생각해보면 .. 1072번 '게임' 문제가있네요. 이 문제에서 탐색할 자료형도 n번째 판 게임에서 임계점에 도달한다.. n을찾아라.. 이런느낌의 문제인데 이 문제의 경우 8번째판, 9번째판, 10번째판..... 1판씩 올려가며 탐색을합니다. 오름차순으로 정렬된 자료이죠. 이때 이분탐색을 쓸수있는겁니다.

예를들어 이런 리스트가 있다고칩시다. 축구선수 등번호가 음수인경우는 없지만... No.7 손흥민선수를 좀 뒤쪽에 모시기위해 설정한 리스트입니다. value가 오름차순으로 정렬되어있으므로 binary search를 쓸수있습니다.

이분탐색(binary search)의 동작구조를 그림으로 그려봤읍니다. 탐색대상 리스트가 계속 반씩 줄어듭니다. 리스트의 가장 앞 인덱스인start와 가장 뒤 인덱스end를 파악해 리스트의 정가운데 mid를 구합니다. mid의 value와 target value를 대소비교해서 만약 mid value가 target value보다 클경우, target value는 mid보다 앞쪽에 있을거라 생각하고 (이 판단때문에 이분탐색은 정렬된 자료에서 쓸수있는거 ㅇㅇ..) mid를 포함하는 절반 뒤쪽리스트는 날려버립니다. 이 행동을 반복하다 start>=end가 되면 종료합니다. 해당지점이 target value의 인덱스입니다.

def binary_search(L_list,target_value):

    start,end = 0,len(L_list) - 1

    while start < end:
        mid = (start + end) // 2

        if L_list[mid] < target_value:
            start = mid + 1
        else:
            end = mid -1

    if L_list[start]==target_value:
        return start

    elif L_list[end]==target_value:
        return end

    else:
        return -1

이분탐색을 코드로 구현하면 위와같습니다. 처음 start와 end를 리스트의 맨처음과 끝으로 설정해두고 mid와 target value를 비교하며 mid가 target value보다 큰경우 end를 mid-1로 잡아 리스트를 반으로 줄일수있습니다. 위의 그림을 상상하면서 코드를 봅시다.

 

선형탐색과 이분탐색의 시간복잡도를 빅 오 표기법으로 생각해봅시다. 리스트의 길이를 n이라할때 선형탐색에선 n을 모두 봐야했습니다. 빅 오 표기법으로 나타낸 선형탐색의 시간복잡도는 n입니다. 이분탐색의 경우 한번 탐색을 할때마다 탐색대상 리스트가 절반으로 계속 줄어듭니다. 1/2 지수 스케일로 작아지므로 log(n)으로 표기할수있겠네요

 

"그럼 이분탐색쓰는게 무조건 이득아님?" 그러나.. 이분탐색에는 앞서말했듯 선행조건이 있습니다. Sorted data에서만 이분탐색을 쓸수있는데 이 Sorted data는 자연발생일수도 있지만 많은경우 Sort를 직접해줘야합니다.

그럼 Sort는 꽁짜인가? -> 사실.. Search보다 Sort가 더 어렵습니다. Sort에 대한 정리는 후에 해보겠읍니다.