탐색 알고리즘

- 알고리즘

재귀함수(Recursion), 탐색(Searching), 정렬(Sorting)

 

탐색 알고리즘 : 데이터 구조에서 특정 값을 찾는 방법

 

선형 탐색(Linear Search)

가장 간단한 형태의 알고리즘이며, 리스트의 처음부터 끝까지 원하는 요소를 찾을 때까지 하나하나 확인한다.
시간 복잡도가 최선의 경우 O(1), 최악의 경우 O(n) 이다. 여기서 n은 리스트의 길이를 나타낸다.
정렬에 대한 의미가 없다.

 

이진 탐색(Binary Search)

이진 탐색은 정렬된 배열에서 특정 값을 찾는데 사용되는 효율적인 알고리즘
중간 값과 찾으려는 값을 비교해서 검색 범위를 절반으로 줄여나간다.
매 단계 검사해야할 요소가 절반으로 줄어들기 때문에 시간 복잡도는 O(log N)이다.

 

# 이진 탐색

def binary_search(array, target, low=None, high=None):
    if low is None:
        low = 0
    if high is None:
        high = len(array) - 1

    if high < low:
        return False
    
    mid = (low+high) // 2
    print(array[mid], end=' ')

    if target == array[mid]:
        return True
    elif target < array[mid]:
        return binary_search(array, target, low, mid-1)
    else :
        return binary_search(array, target, mid+1, high)

lst = [1,3,4,9,10,13,17,24,28,30]
print(binary_search(lst, 4))
print(binary_search(lst, 30))
print(binary_search(lst, 38))

# 정렬

# 선택 정렬

lst = [11,3,24,9,40,33,7,2,8,30]

# min_num = lst[0]
# lst_sort = []

# for i in range(len(lst)):
#     for j in lst:
#         if j < min_num:
#             min_num = j
#     lst_sort.append(min_num)

# print(lst_sort) <- 실패작..... ㅠㅠㅠㅠ

def selection_sort(arr):

    for i in range(len(arr)):
        min_index = i

        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j

        arr[i], arr[min_index] = arr[min_index], arr[i]

    return arr

lst = [11,3,24,9,40,33,7,2,8,30]
print(selection_sort(lst))

print("=====================================")

# 삽입 정렬

# [29, 10, 14, 37, 13]
# [  , 29, 14, 37, 13] - 10
# [10, 29, 14, 37, 13]
# [10,   , 29, 37, 13] - 14
# [10, 14, 29, 37, 13]
# [10, 14, 29,   , 37] - 13
# [10, 14,   , 29, 37] - 13
# [10,   , 14, 29, 37] - 13
# [10, 13, 14, 29, 37]

def insertion_sort(arr):

    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j>=0 and key<arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key

    return arr

lst = [11,3,24,9,40,33,7,2,8,30]
print(insertion_sort(lst))

 

알고리즘 복잡도

+ 시간 복잡도 : 알고리즘이 문제를 해결하는데 얼마나 많은 시간이 필요한지 측정
    입력 크기에 따른 연산 횟수로 표현하며 이 연산횟수가 증가하는 속도를 나타내는 것이 중요하다.

+ 공간 복잡도 : 알고리즘이 문제를 해결하는데 얼마나 많은 메모리가 필요한지 측정
    입력 데이터 외에 추가적으로 필요한 공간

 

Big O notation 은 시간 및 공간 복잡도를 표현하기 위한 수학 표기법
O()은 최악의 경우 (worst case scenario)에서 알고리즘의 성능을 의미하며,
입력 크기 n에 대한 함수의 상한선(upper bound)를 제공한다.

1. O(1) : 상수 시간(constant time) : 입력 크기와 무관하게 항상 동일한 시간이 걸린다.
2. O(n) : 선형 시간(linear time) : 입력 크기에 비례해서 처리 시간이 증가한다.
3. O(n^2) : 제곱 시간(quadratic time) : 입력 크기의 제곱에 비례해서 처리 시간이 증가한다.
4. O(log n) : 로그 시간(logarithmic time) : 로그 함수와 같이 초기에 빠르게 감소하다가 점차 감소 속도가 줄어든다.
5. O(n log n) : 선형 로그 시간(linear logarithmic time) : 선형 시간과 로그 시간의 곱만큼 처리 시간이 증가한다.

효율적인 순서
O(1) -> O(log n) -> O(n) -> O(n log n) -> O(n^2) -> O(2^n)
1번       10번     100번     1000번      10000번