파이썬 자료구조와 알고리즘(10)-탐색

업데이트: November 08, 2019

순차 검색
- 배열이 정렬되어 있거나
- 연결 리스트와 같이 입력이 동적으로 할당되는 경우
이진 검색
- 배열이 정렬되어 있는 경우
해시 테이블
- 보조 메모리 공간을 사용
- 키를 이용하면 $O(1)$에 검색 가능하다.

1. 정렬되지 않은 배열

1.1 순차 검색

최선의 경우 $O(1)$, 평균 $O(n/2)$, 최악 $O(n)$이다.

리스트에 검색 항목 없다면 모두 $O(n)$이다.

def sequential_search(seq, n):
    for item in seq:
        if item == n:
            return True
    return False

리스트가 정렬되어 있다면 검색 항목 없는 경우에도 있을때와 같은 시간 복잡도를 가진다.

def ordered_sequential_search(seq, n):
    item = 0
    for item in seq:
        if item > n:
            return False
        if item == n:
            return True
    return False

1.2 빠른 선택과 순서통계량

퀵 정렬 알고리즘을 수정하여 리스트에서 k번째로 작은 항목을 찾아보자.

이러한 숫자 k를 k번째 순서통계량이라 한다.

ex) 최솟값, 최댓값, 중앙값 등

def quick_select_cache(seq, k):
    len_seq = len(seq)
    if len_seq < 2:
        return seq[0]
    
    # 피벗을 무작위로 선택할 수 있다.
    # pivot = random.choice(seq)
    ipivot = len_seq // 2
    pivot =  seq[ipivot]

    smallerList = [x for i, x in enumerate(seq) if x <= pivot and i != ipivot]
    largerList = [x for i, x in enumerate(seq) if x > pivot and i != ipivot]

    m = len(smallerList)
    if k == m:
        return pivot
    elif k < m:
        return quick_select_cache(smallerList, k)
    else:
        return quick_select_cache(largerList, k-m-1)

2. 정렬된 배열

2.1. 이진 검색

정렬된 배열 내에서 값을 찾는다. $O(\log{n})$

def binary_search_rec(seq, target, low, high):
    if low > high:
        return None
    mid = (low+high)//2
    if seq[mid] == target:
        return mid
    elif seq[mid] < target:
        return binary_search_rec(seq, target, mid+1, high)
    else:
        return binary_search_rec(seq, target, low, mid-1)

def binary_search_iter(seq, target):
    '''
    반복문
    '''
    high, low = len(seq), 0
    while low < high:
        mid = (low+high)//2
        if seq[mid] == target:
            return mid
        elif target < seq[mid]:
            high = mid
        else:
            low = mid+1
    return None

2.2. bisect 모듈

from bisect import bisect

3.1 행렬 검색

행과 열이 정렬되어 있는 행렬 검색 코드이다.

시간복잡도 $O(n+m)$

def find_elem_matrix_bool(m1, value):
    found = False
    row = 0
    col = len(m1[0]) - 1
    while row < len(m1) and col >= 0:
        if m1[row][col] == value:
            found = True
            break
        elif m1[row][col] > value:
            col -= 1
        else:
            row += 1
    return found

한 행의 마지막 수가 다음 행의 첫 번쨰 숫자보다 작은 행렬은

정렬된 1차원 배열로 볼 수 있다. 즉 $O(\log{mn})$ 에 검색 가능하다

def searching_in_a_matrix(m1, value):
    rows = len(m1)
    cols = len(m1[0])
    lo = 0
    hi = rows*cols
    while lo < hi:
        mid = (lo+hi)//2
        row = mid // cols
        col = mid % cols
        v = m1[row][col]
        if v == value:
            return True
        elif v > value:
            hi = mid
        else:
            lo = mid+1
    return False

3.2. 단봉형 배열

이진 탐색을 이용해 최댓값 찾는다.

def find_max_unimodal_array(A):
    if len(A) <= 2:
        return None
    left = 0
    right = len(A)-1
    while right > left+1:
        mid = (left+right)//2
        if A[mid] > A[mid-1] and A[mid] > A[mid+1]:
            return A[mid]
        elif A[mid] > A[mid-1] and A[mid] < A[mid+1]>:
            left = mid
        else:
            right = mid
    return None

3.3. 제곱근 계산하기

3.4. 빈도 계산하기

3.5. 교집합 구하기

set을 사용하면 순서를 보장하지 않는다.

남궁찬