Search, Sort 비전공자 문돌이가 설명하는 파이썬(Python) 기본 문법 (4)

검색(Search)이란?

1. Linear Search: 정직하게 처음만 찾자!

순차 검색 알고리즘은 말 그대로 찾고자 하는 값을 순차적으로 탐색합니다. 처음부터 차근차근 해당 값을 찾고, 똑같은 값이 이후에 존재하더라도 처음 찾은 것만 리턴하게 됩니다.  

주의할 점은 찾고자 하는 값이 없을 경우 디폴트 값으로 -1을 리턴합니다. 

알고리즘(Algorithm) vs 프로그래밍(Programming)

알고리즘은 컴퓨터가 수행할 수 있는 로직(logic)이며 사람이 손으로도 작성 가능합니다. 반면, 프로그래밍은 이 로직을 직접 구현하도록 컴퓨터가 이해할 수 있는 언어로 구성된 명령어 모음입니다. 알고리즘은 하나인데, 프로그래밍은 여러 개가 될 수 있죠. 아래 예시를 보며 자세하기 이해해보록 합시다.

# While Loop을 사용한 Linear search 구현
def linear_search_while(L: list, value: Any) -> int:
    i = 0
    while i < len(L) and L[i] != value:
        i += 1
    if i == len(L):
        return -1
    else:
        return i

# Sentinel(감시자)과 While Loop을 활용 Linear search 구현
def linear_search_while(L: list, value: Any) -> int:
    L.append(value)
    i = 0
    while L[i] != value:
        i += 1
    L.pop()
    
    if i == len(L):
        return -1
    else:
        return i

# For Loop을 사용한 Linear search 구현
def linear_search_for(L: list, value: Any) -> int:
    for i in range(len(L)):
        if L[i] == value:
            return i
    return -1

아래는 프로그래밍 방법에 따른 알고리즘 구현 시간을 구해보는 코드입니다. 예시로 for loop을 활용해보았습니다.

import time
import random

def linear_search_for(L: list, value: int) -> int:
    for i in range(len(L)):
        if L[i] == value:
            return i
    return -1

input_list = list(range(1000000))
random.shuffle(input_list)

t_start = time.perf_counter()
linear_search_for(input_list, 1)
t_end = time.perf_counter()

duration = (t_end - t_start) * 1000.0 # 단위는 milliseconds
duration

2. Binary Search: 반으로 쪼개자!

Linear Search는 정직하기 때문에 만약 원래 자료가 크기 순으로 정렬되어 있다면 큰 숫자를 찾을수록 불리해집니다. 끝까지 찾아야 해서 시간이 오래 걸리는 것이죠. 하지만 정렬된 자료를 잘 사용하는 방법이 있는데, 바로 이진 검색 알고리즘입니다. 

아래와 같이 크기 순으로 정렬되어 있는 자료에서 숫자 9를 찾는다고 가정해봅시다. 이진 검색 알고리즘은 전체를 우선 반으로 쪼개기 위해 중간값을 찾아냅니다. 이때 찾는 값보다 클 경우, 중간값 이전의 값들은 신경쓰지 않고, 중간값 이후의 값들만 신경씁니다. 아래의 경우, 진한 초록색으로 표시된 부분들이 검색 대상에서 제외되는 것이죠.

참고: 중간값은 시작점과 끝점의 인덱스를 더하고 2로 나눈 몫에 해당하는 인덱스의 value입니다. 

알고리즘은 다시 인덱스 6번에서 타겟을 찾기 시작합니다. 이때 다시 중간값을 찾고, 12는 찾는 값 9보다 크기 때문에 이번엔 오른쪽 반(진한 초록색 표시)이 검색 대상에서 제외됩니다.  

이후에 알고리즘은 다시 인덱스 6번에서 찾기 시작하고, 중간값은 인덱스 6번이 됩니다. 이때 인덱스 6번의 값은 8로 찾는 값 9보다 작기 때문에 6번 인덱스를 검색 대상에서 제외하고 인덱스 7번에서 검색을 시작합니다. 

인덱스 7번 역시 중간 인덱스가 자기 자신이 되는데, 인덱스 값이 타겟과 같을 경우 끝점을 하나 줄입니다. 즉 시작점이 인덱스 7번이 되고, 끝점이 인덱스 6번이 되며 이 경우에는 코드가 멈추도록 구현되어 있습니다. 그리고 타겟값의 인덱스(List[타겟값])를 리턴하는 것이죠.

Stopping condition: 시작점과 끝점 모두 인덱스 7번입니다. 인덱스 7번 값은 타겟값과 똑같고, 이때 끝점은 인덱스 6번이 됩니다. 이때 코드를 종료하고 L[시작점]을 타겟값으로 판단하여 출력합니다. 

def binary_search(L: list, v: Any) -> int:
    start, end = 0, len(L) - 1
    while start != end + 1:
        mid = (start + end)//2
        if L[mid] < v:
            start = mid + 1
        else:
            end = mid - 1
     
     if start < len(L) and L[start] == v:
         return start
     else:
         return -1

이진 검색 알고리즘은 순차 검색 알고리즘보다 구현 속도가 훨씬 빠릅니다. 찾고자 하는 값이 작든, 크든 모두 상관없이 말이죠. 

	Linear search	Binary search
Time delay	$len(L)$	$log_2^{len(L)}$

정렬(Sort)이란?

1. Selection Sort: 나와 자리를 바꾸자!

단도직입적으로 말해, 전체 리스트에서 최솟값을 찾고 인덱스 0번과 위치를 바꿉니다. 

아래 그림과 같이 0번 인덱스가 가장 작은 값을 가지게 되고, 초록색 선을 기준으로 왼쪽은 이미 정렬된 부분, 오른쪽은 정렬되지 않은 부분이 됩니다. 정렬되지 않은 부분에서 최솟값을 찾고 정렬되지 않은 부분의 가장 왼쪽 인덱스, 즉 인덱스 1번과 위치를 바꿉니다. 이를 계속 반복해서 완료하면 정렬된 리스트를 얻게 됩니다. 

def selection_sort(L: list) -> None:
    for i in range(len(L)):
        min_val = i # 최초의 최솟값은 시작점 값
        for j in range(i + 1, len(L)): # 최초 최솟값 오른쪽에 존재하는 값 탐색
            if L[j] < L[min_val]:
                min_val = j
        L[i], L[min_val] = L[min_val], L[i] # 위치 바꾸기

Selection sort의 시간 복잡도는 다음과 같습니다. 인덱스 길이를 N이라 한다면, 처음엔 모든 인덱스를 봐야 하기 때문에 N개를 탐색합니다. 이후 인덱스 0번은 정렬된 것이므로 N-1개의 인덱스를 봅니다. 이를 남은 인덱스가 1개일 때까지 계속 반복하는 것입니다. 

N + (N-1) + (N-2) + ... + 1 = N(N+1)/2

2. Insertion Sort: 비교해서 끼워넣자!

전체 리스트 값을 비교하지 말고 가장 왼쪽에 위치한 인덱스 값을 정렬된 버전이라고 "가정"하고, 오른쪽에 있는 인덱스 값과 비교합니다. 이후 둘 중 더 작은 인덱스 값을 맨 왼쪽에 위치시킵니다. 

-3과 7 중 -3이 더 작기 때문에 원래 인덱스 0번이었던 7이 인덱스 1로 옮겨졌습니다. 

이 작업을 계속해주며 왼쪽을 정렬된 버전으로 만드는 것입니다. 즉 정렬되지 않은 오른쪽 부분의 첫 번째 인덱스 값이 정렬된 왼쪽 부분의 인덱스와 하나하나 비교해갑니다. 예를 들어, 아래에선 인덱스 4번 값 3은 1) 인덱스 3번 값 40과 비교 -> 2) 인덱스 2번 값 10과 비교 -> 3) 인덱스 1번 값 10과 비교 -> 4) 인덱스 0번 값 -3과 비교합니다. 

def insert_test(L: list) -> None:
    for i in range(1, len(L)):
        for j in range(i, 0, -1): # 뒤에서부터 비교
            if L[j-1] > L[j]:
                L[j-1], L[j] = L[j], L[j-1]
        else:
            break

Insertion sort의 시간 복잡도는 다음과 같습니다. 먼저 가장 좋은 시나리오는 딱 1번만 비교하는 것이며, 최악의 시나리오는 맨 왼쪽의 인덱스 값까지 즉 i 번 비교하는 것이죠. 따라서 이의 평균인 (i+1)/2 번 비교한다고 합시다. 이는 for j in range(i, 0, -1)에 해당하는 것이구요.

for i in range(1, len(L))까지 계산하려면 i=1~len(L) 일 때, 1 + 1.5 + 2 + 2.5 +... + (N-1)/2 + N/2 입니다. 

(1 + 2 + 3 +... + (N-1) + N)/2 - 1/2 = N(N+1)/4 - 1/2

참고로 Insertion sort는 데이터가 정렬되어 있을 때, 그 효과가 배가 됩니다. 반대로, Selection sort는 정렬이 되어 있든, 되어 있지 않든 관계 없이 타임 복잡도는 변화가 없습니다.