10-2. 검색 연습문제 (Searching Examples): 파이썬 자료구조와 알고리즘

행렬 검색

각 행과 열이 정렬되어 있는 행렬에서 한 항목을 검색한다고 해보자. 즉 모든 행은 왼쪽에서 오른쪽으로, 모든 열은 위에서 아래로 첫 번째 항목을 기준으로 정렬 (오름차순) 되어 있다. 예제 리스트는 아래와 같다.

 

m1 = [
    [1, 2, 8, 9],
    [2, 4, 9, 12],
    [4, 7, 10, 13],
    [6, 8, 11, 15]
]

 

책의 정답:

 

matrix = [
    [1, 2, 8, 9],
    [2, 4, 9, 12],
    [4, 7, 10, 13],
    [6, 8, 11, 15]
]

def search_matrix(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

print(search_matrix(matrix, 10))

 

결과

 

PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/10. 검색/search_entry_matrix.py"
True

 

획기적인 정답이 있을 줄 알았으나 책의 정답도 각 행을 순회하며 값을 찾는 방식이었다.

 

다음 예제의 행렬은 한 행의 마지막 숫자가 다음 행의 첫 번째 숫자보다 작다. 즉 모든 행이 오름차순으로 정렬되어 있다. 이 행렬에서 어떤 숫자를 무차별 (브루트 포스) 로 검색한다면 시간 복잡도는 O(mn)이지만 이 행렬은 모든 행이 정렬되어 있어 1차원 배열로 볼 수도 있기 때문에, O(log mn)의 이진 검색 알고리즘이 사용 가능하다.

 

책의 정답:

 

def search_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

matrix = [[1,3,5], [7,9,11], [13,15,17]]

print(search_in_a_matrix(matrix, 2))
print(search_in_a_matrix(matrix, 3))

 

결과 =

 

PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/10. 검색/eg_search_in_a_matrix.py"
False
True

 

단봉형 배열

배열 요소들의 산포도를 그렸을 때 값이 증가했다가 다시 감소하는 곡선인 경우 이 배열을 단봉형 (unimodal) 이라고 한다. 단봉형 배열에서 이진 검색을 사용하여 최댓값을 찾아보자.

 

내 정답

 

def find_max_unimodal_array(l):
    len_l = len(l)
    mid = len_l // 2

    if l[mid] > l[mid+1] and l[mid] > l[mid-1]:
        return l[mid]
    elif l[mid] > l[mid+1] and l[mid] < l[mid-1]:
        return find_max_unimodal_array(l[:mid])
    else:
        return find_max_unimodal_array(l[mid+1:])

ll = [1,2,3,4,5,6,8,7,5,4,3,2,1]

print(find_max_unimodal_array(ll))

 

책의 정답

 

def find_max_unimodal_book_answer(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

 

결과

 

PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/10. 검색/eg_find_max_unimodal_array.py"
8

 

내 정답은 조금 불안정할 수 있다. 책의 정답이 조금 더 안정적이고 더 많은 케이스들을 커버할 수 있다.

 

제곱근 계산하기

이진 검색을 사용하여 제곱근을 구할 수도 있다.

 

내 정답

 

def find_sqrt_binary_search(n, error=0.001):
    if n == 1:
        return 1
    low = n < 1 and n or 1
    high = n < 1 and 1 or n

    mid = (low + high) / 2
    while abs(mid**2 - n) > error:
        mid = (low + high) / 2
        if mid**2 > n:
            high = mid
        elif mid**2 < n:
            low = mid
    
    return mid

print(find_sqrt_binary_search(2))
print(find_sqrt_binary_search(9))

 

책의 정답

 

def find_sqrt_book_answer(n, error=0.001):
    lower = n < 1 and n or 1
    upper = n < 1 and 1 or n
    mid = lower + (upper - lower) / 2.0
    square = mid * mid
    while abs(square - n) > error:
        if square < n:
            lower = mid
        else:
            upper = mid
        mid = lower + (upper - lower) / 2.0
        square = mid * mid
    return mid

 

결과

 

PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/10. 검색/eg_find_sqrt_binary_search.py"
1.4140625
3.0

 

정답이 거의 같다. 기본적인 힌트를 얻고 시작했기 때문인 것 같다.

 

빈도 계산하기

정렬된 리스트에서 요소 n이 나타나는 횟수를 구해보자.

 

내 정답

 

from binary_search import binary_search_iter

def find_occurrence(l, n):
    i = binary_search_iter(l, n)
    while l[i] == l[i-1]:
        i -= 1
    count = 1
    while l[i] == l[i+1]:
        i += 1
        count += 1
    return count


l1 = [1,2,3,3,3,3,3,3,5,6,7,8]
print(find_occurrence(l1, 3))

 

책의 정답

 

def find_occurrence_book_answer(seq, k):
    index_some_k = binary_search_iter(seq, k)
    count = 1
    sizet = len(seq)
    for i in range(index_some_k+1, sizet):
        if seq[i] == k:
            count += 1
        else:
            break
    for i in range(index_some_k-1, -1, -1):
        if seq[i] == k:
            count += 1
        else:
            break
    return count

 

결과

 

PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/10. 검색/eg_find_occurrence.py"
6

 

책의 정답은 해당 항목 앞 뒤에 같은 숫자를 가진 수들을 찾는다. 내 정답은 해당 수가 처음 등장하는 인덱스까지 갔다가 해당 수가 마지막으로 등장하는 인덱스까지 가면서 카운트를 세는 방식이다. 책의 정답이 더 작은 시간 복잡도를 갖고 있을 것이다.

 

출처

파이썬 자료구조와 알고리즘 - 한빛 미디어, 미아 스타인