Python Algorithm 3. 검색

# 정렬이 되어 있는 배열
# 순차검색, 이진검색
# 순차 검색 : 정렬이 되어 있지 않는 배열을 검색할때
# 연결리스트와 같이 입력이 동적할당 되는 경우에 사용합니다.

# 이진 검색 : 배열이 정렬은 되어 있고
# 해시 테이블이용하면 보조 메모리 공간을 사용하고
# 키를 이용해서 원하는 값을 찾을 수 있다.

# 순차 검색


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

def test():
    seq = [1, 5, 6, 8, 3]
    n1 = 5
    n2 = 7
    assert(sequential_sort(seq, n1) is True)
    assert(sequential_sort(seq, n2) is False)
    
    print("테통!")
    
if __name__ == "__main__":
    test()
    
    >>>테통!

# 정렬이 되어있는리스트를 검색할때 
# 사용할 순차검색을 만들어 보세요.

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

def test():
    seq = [1, 2, 4, 5, 6, 8, 10]
    n1 = 10
    n2 = 7
    assert(sequential_sort(seq, n1) is True)
    assert(sequential_sort(seq, n2) is False)
    print("굳")
    
if __name__ == "__main__":
    test()
    
    
>>> 굳

# 이진 검색
# 정렬된 배열 내에서 지정된 입력값의 위치(ㅋㅣ)를 찾습니다.
# 이진검색은 입력값과 배열의 중간요소를 비교합니다.
# 입력값과 중간요소가 일치한다면 배열의 위치가 반환
# 입력값이 중간요소보다 작다면 중간 요소의 왼쪽 하위 배열에서
# 검색과정을 반복합니다.
# 큰경우 중간 요ㅕ소의 오른쪽 하위 요소가 반봅ㄱ합니다.

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

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

seq = [1, 2, 5, 6, 7, 10, 12, 12, 14, 15]
target = 10
binary_search_iter(seq, target)

# def test():
#     seq = [1, 2, 5, 6, 7, 10, 12, 12, 14, 15]
#     target = 6
#     assert(binary_search_rec(seq, target, 0, len(seq)) == 3)
#     assert(binary_search_iter(seq, target) == 3)
    
# if __name__ == "__main__":
#     test()

>>>
target = 10
seq[mid] =  10
high =  10
low = 0
5

# bisect 모듈 -> 이진검색이 가능한 모듈
from bisect import bisect

l = [0, 3, 4, 5]

bisect(l, 5)

# 빈리스트 혹은 값이 없는 예외의 경우에는
bisect([], 1)

>>> 0

# 다차원이 배열이 있습니다.
# 각 행과 열이 정렬되어 있는 행렬에서 한 항목을 검색합니다.
# 모든 행은 왼쪽에서 오른쪽으로 , 모든 열은 위에서 아래로 정렬(오름차순)

# list_a = [[1, 2, 8, 9],
          # [2, 4, 9, 12],
          # [4, 7, 10, 13],
          # [6, 8, 11, 15]]
# 8을 찾아라! -> True
# 3을 찾아라! -> False

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

def test():
    m1 = [[1, 2, 8, 9],[2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]]
    assert(find_elem_matrix(m1, 13) is True)
    
    print("잘 만든 알고리즘 입니다.")
    
if __name__ == "__main__":
    test()
    
>>> 잘 만든 알고리즘 입니다.

# 한행의 마지막 숫자가 다음 행의 첫번재 숫자보다 작습니다.
# 모든 행이 오름차순으로 되어 있습니ㅣ다.
# 이 행렬에서 어떤 숫자를 무차별로 검색한다면 어떤 검색 알고리즘을 사용해야 할까요?
# 이진 검색

# a = [[1,3, 5], [7, 9, 11], [13, 15, 17]]
# import numpy
# b = numpy.array([(1, 2), (3, 4)])
# assert(알고리즘(a, 13))is True)
# assert(알고리즘(b, 3)is True)

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

def test():
    a = [[1,3, 5], [7, 9, 11], [13, 15, 17]]
    import numpy
    b = numpy.array([(1, 2), (3, 4)])
    assert(searching_in_matrix(a, 13)is True)
    assert(searching_in_matrix(b, 3)is True)
    print("알고리즘 굳")
if __name__ == "__main__":
    test()
    
>>> 알고리즘 굳

# 메모이제이션
# 메모 -> 딕셔너리 형식으로 값을 넣어준다음에
# 이전 값을 메모리에 저장해서 동일한 계산의 반복 수행을 하지 않는것
# 피보나치 수열


def memo(func):
    cache = {}
    
    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap


def fib(n):
    if n < 2:
        return 1
    else:
        return fib(n-1) + fib(n-2)

>>>