Python-12.Search

2022-03-03 20:06

안녕하세요 묵호입니다.
이번엔 검색에 대해 알아보겠습니다.

검색

10개의 데이터가 저장되어 있는 리스트에 내가 찾는 데이터가 있는지 어떻게 찾을 수 있을까요? 제일 간단한 방법으로는 리스트의 맨 앞부터 맨 끝까지 순차적으로 확인해보는 것이 있습니다. 이것이 검색입니다. 반복문을 통한 검색 알고리즘 코드입니다.

lst = [1, 3, 5, 7, 9, 2, 4, 6, 8, 10]
target = 2 # 내가 찾고 싶은 숫자
idx = -1 # 보통의 검색 알고리즘은 찾으면 해당 위치의 index를, 찾지 못하면 -1을 반환합니다.

for i in range(len(lst)):
    if target == lst[i]:
        idx = i
        break # 찾았으므로 더 이상 반복할 필요가 없음

print(idx)
# 5

알고리즘을 보면 lst의 맨 앞부터 순차적으로 target이 있는지 확인하는 과정을 거치는 것을 확인할 수 있습니다. 위 알고리즘은 순차 검색 알고리즘(Sequential Search Algorithm)으로, 구현 방법이 간단하고 정렬이 필요하지 않은 방식입니다. 이 알고리즘의 시간 복잡도는 O(n)입니다.
시간 복잡도는 알고리즘의 입력값과 연산 수행 시간의 상관관계를 나타내는 것입니다. O는 big-o라 하며, 알고리즘의 시간 복잡도를 다룹니다. 알고리즘은 연산의 횟수가 많아질수록 속도가 느려집니다.
O(log n)인 검색 알고리즘이 있습니다. 검색하고 싶은 데이터들이 정렬이 되어 있어야 사용할 수 있는 이 알고리즘은 이진 탐색 알고리즘(Binary Search Algorithm)이라고 합니다. 이진 탐색 알고리즘에 대해 알고 싶으신 분들은 여기서 확인해보세요.

def BinarySearch(lst, target, low, high):
    if low > high:
        return False
    
    mid = (low + high) / 2
    if lst[mid] > value:
        return BinarySearch(lst, target, low, mid-1)
    elif lst[mid] < value:
        return BinarySearch(lst, target. mid+1, high)
    else:
        return mid

정렬

이진 탐색을 하기 위해서는 리스트를 정렬해야 한다고 했습니다. 그렇다면 리스트를 어떻게 정렬할까요? 리스트의 내장함수를 사용할 수도 있습니다.

lst = [1, 3, 5, 7, 9, 2, 4, 6, 8, 10]
lst.sort() # 오름차순 정렬
# lst.sort(reverse = True) <- 내림차순 정렬
print(lst)
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

하지만 이 정렬이 어떻게 돌아가는지 알면 더 좋겠죠? 이곳에서 다양한 종류의 알고리즘을 확인할 수 있습니다. 저는 간단한 알고리즘인 버블, 선택, 삽입, 합병 정렬에 대해서만 다뤄보겠습니다.

버블 정렬(O(n^2))
1번째와 2번째 데이터를 비교해 정렬하고 2번째와 3번째, …, n-1번째와 n번째를 정렬한 뒤, 다시 처음으로 돌아가 n-2번째와 n-1번째까지 를 최대 n(n-1)/2번 정렬하는 알고리즘이다. 보통 이중 for문으로 구현하는데, 내부 for문이 끝나면 마지막 데이터가 정렬되어 데이터들이 거품이 올라오는 것처럼 보여 Bubble Sort라고 한다. 구현하기 쉬우나, 대부분의 경우에서 비효율적인 알고리즘이기 때문에 웬만하면 사용을 피해야 한다.
```
def BubbleSort(lst):
  for i in range(len(lst)-1, -1, -1):
      for j in range(0, i):
          if lst[i] > lst[j]:
              lst[i], lst[j] = lst[j], lst[i]
```
선택 정렬(O(n^2))
버블 정렬이 비교한 후 바로 바꾸는 것을 반복한다면, 선택 정렬은 일단 1에서 n번째 데이터들을 전부 확인한 후 가장 작은 것을 맨 앞으로 보내고, 다음은 1에서 n번째를 확인해 2번째 위치로 보내는 과정을 n-1에서 n번째까지 반복하는 것이다. 버블 정렬보다 2배 가량 빠르다고 한다.
```
def SelectionSort(lst):
  for i in range(len(lst)-1):
      minIdx = i
      for j in range(i+1, len(lst)):
          if lst[j] < lst[i]:
              minIdx = j

      lst[i], lst[minIdx] = lst[minIdx], lst[i]
```
삽입 정렬(O(n^2))
k번째 원소를 1부터 k-1까지와 비교해 적절한 위치에 끼워넣고 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식이다. 평균적으로 O(n^2) 알고리즘 중 빠른 편이나, 사용한 자료구조에 따라서 데이터를 뒤로 밀어내는 데 시간이 오래 걸릴 수 있다

def InsertionSort(lst):
    for i in range(1, len(lst)):
        key = lst[i]

        for j in range(i-1, -1, -1):
            if lst[j] > key:
                lst[j+1] = lst[j]
        
        lst[j+1] = key

합병 정렬(O(n log n))
합병 정렬(Merge Sort)은 원소 개수가 1 또는 0이 될 때까지 두 부분으로 쪼개고 쪼개서 자른 순서의 역순으로 크기를 비교해 병합해 나가는 방식으로, 병합된 부분은 이미 정렬되어 있어 전부 비교하지 않아도 제 자리를 찾게할 수 있다. 대표적인 분할 정복(Divide and Conquer) 알고리즘이다.
합병 정렬은 분할-정복-결합의 단계를 거치며, 과정 중 추가적인 리스트가 필요하다.

sorted = [0] * len(lst) # 여기서 lst는 전역변수이다.
def Merge(lst, left, mid, right):
    i = left
    j = mid+1
    k = left

    # 분할 정렬된 list 합병
    while i<=mid and j<=right:
        if lst[i] <= lst[j]:
            sorted[k] = lst[i]
            i += 1
        else:
            sorted[k] = lst[j]
            j += 1
        k += 1

    # 남아 있는 값들 일괄 복사
    if i>mid:
        for l in range(j, right+1):
            sorted[k] = lst[l]
            k += 1
    else:
        for l in range(i, mid+1):
            sorted[k] = lst[l]
            k += 1

    # 임시 리스트 sorted를 lst로 복사
    for l in range(left, right+1):
        lst[l] = sorted[l]

def MergeSort(lst, left, right):
    if left < right:
        mid = int((left+right) / 2) # 중간 위치 계산->리스트 균등 분할(분할)
        MergeSort(lst, left, mid) # 리스트 앞쪽 부분 정렬(정복)
        MergeSort(lst, mid+1, right) # 리스트 뒤쪽 부분 정렬(정복)
        Merge(lst, left, mid, right) # 정렬된 2개의 부분 배열 합병(결합)

다음 시간에는 파이썬 시리즈 마지막으로, 클래스에 대해 알아보겠습니다.
그럼.. 바위^^

python

Python-12.Search

검색

정렬

Table of Contents