Skip to content

Search.md

Latest commit

 

History

History
153 lines (119 loc) · 8.56 KB

Search.md

File metadata and controls

153 lines (119 loc) · 8.56 KB

탐색

  • 데이터의 집합에서 원하는 조건을 만족하는 데이터를 찾는 작업임
  • 레코드(record): 탐색을 위한 대상
  • 테이블(table): 레코드의 집합
  • 하나의 레코드는 여러 개의 필드로 이루어지는데, 이중에서 탐색의 기준이 되는 필드를 키(key) 또는 탐색키(search key)라고 부름
  • 결국 탐색은 테이블에서 원하는 탐색키를 가진 레코드를 찾는 작업임
  • 탐색을 위한 테이블은 여러 가지 방법으로 구성할 수 있음
    • 가장 간단한 방법은 배열을 사용하는 것임
    • 성능을 더 높이고 싶다면 이진 탐색 트리나 해싱을 사용해야 함
    • 탐색 방법을 선택할 때는 당연히 탐색 연산의 효율이 가장 중요하겠지만, 테이블에 레코드를 추가하거나 꺼내는 삽입과 삭제 연산도 마찬가지로 중요하게 고려해야 함

순차 탐색

  • 순차 탐색(sequential search) 또는 선형 탐색(linear search)은 일렬로 늘어선 자료(레코드) 중에서 원하는 키값을 가진 레코드를 찾는 알고리즘임
  • 테이블은 배열이나 연결 리스트로 구성될 수 있음
  • 테이블의 각 레코드를 처음부터 하나씩 순서대로 검사하여 원하는 레코드를 찾음
  • 순서대로 모든 레코드를 검사하므로 레코드들이 뒤죽박죽 무질서하게 섞여 있어도 항상 원하는 레코드를 찾을 수 있음

순차 탐색 알고리즘

def sequential_search(A, key, low, high):
    for i in range(low, high+1):
        if A[i] == key:
            return i
    return -1

순차 탐색은 얼마나 빠를까?

  • 순차 탐색에서 가장 운이 좋은 경우는 찾는 자료가 맨 앞에 있는 경우임
    • 이 경우, 1번의 비교만으로 탐색이 완료됨
  • 최악의 경우는 찾는 레코드가 테이블의 맨 뒤에 있거나 리스트에 없는 키를 찾는 경우임
    • 이 경우, 항상 모든 레코드를 탐색해야 하므로 탐색 범위만큼 비교가 필요함
    • 즉, 테이블의 크기가 $n$이라면 시간 복잡도는 $O(n)$임

순차 탐색의 특징

  • 탐색의 정의를 직접 사용하는 알고리즘으로 간단하고 구현하기 쉬움
  • 효율적이지 않음
    • 탐색 성능은 최선의 경우 $O(1)$ 이고, 최악이나 평균적인 경우가 $O(n)$ 인데, 최선의 경우는 큰 의미가 없음
    • 테이블이 정렬되어 있지 않다면 순차 탐색 이외에 별다른 대안은 없음

순차 탐색을 개선할 방법

  • 레코드 중에서 자주 검색되는 것들을 가능한 한 앞에 두는 것임
  • 이러한 방법을 자기 구성(self-organizing) 순차 탐색이라고 함
  • 탐색이 진행될 때마다 자주 사용되는 레코드를 앞쪽으로 옮기는 방법으로 리스트를 재구성하여 탐색의 효율을 끌어올리려는 것임
  • 이런 리스트를 자기 구성 리스트라고 함

맨 앞으로 보내기(move to front)

  • 가장 단순한 방식은, 원하는 레코드를 찾은 뒤 그 레코드를 리스트의 맨 앞으로 옮기는 것임
  • 배열로 표현한 리스트에서는 그 레코드보다 앞에 있던 원소들을 모두 한 칸씩 뒤로 밀어 빈 칸을 맨 앞에 만들고, 찾은 레코드를 그 자리에 둠
  • 연결 리스트에서는 원소를 통째로 옮기지 않고 포인터만 조정하면 됨
    • 찾은 노드를 리스트에서 분리한 다음 head가 그 노드를 가리키도록 연결하면 맨 앞으로 이동한 것과 같음

교환하기(transpose)

  • 탐색된 레코드를 맨 앞이 아니라 바로 앞의 레코드와 교환할 수도 있음
  • 자주 탐색되는 레코드는 점진적으로 앞으로 이동하고, 그렇지 않은 레코드는 점진적으로 뒤로 밀리는 효과가 있음
def sequential_search_transpose(A, key, low, high):
    for i in range(low, high+1):
        if A[i] == key:
            if i > low: # 맨 처음 요소가 아니라면
                A[i], A[i-1] = A[i-1], A[i] # 교환하기
                i = i-1 # 한 칸 앞으로 옴
            return i # 탐색에 성공하면 키값의 인덱스 반환
    return -1 # 탐색이 실패하면 -1 반환
  • 이외에도 레코드마다 탐색된 횟수를 별도의 공간에 각각 저장해 두고, 탐색된 횟수가 많은 순으로 테이블을 재구성하는 전략(frequency count method)을 사용할 수 있음
  • 이러한 방법들도 모두 지금까지 더 많이 탐색된 레코드가 앞으로도 더 많이 탐색될 가능성이 큰 응용에만 적용되어야 할 것임

이진 탐색

  • 테이블이 키값을 기준으로 정렬되어 있다면 이진 탐색(binary search)이라는 보다 효율적인 알고리즘을 사용할 수 있음
  • 이것은 한 번 비교할 때마다 탐색 범위가 절반으로 줄어들기 때문에 '이진'이라는 이름이 붙음
  • 이진 탐색은 먼저 테이블의 중앙에 있는 레코드를 탐색 키와 비교함
  • 만약 중앙 레코드의 키값이 탐색 키와 같으면 탐색은 성공한 것이고, 중앙 레코드의 위치(인덱스)를 반환하면 됨
  • 중앙 레코드가 탐색 키보다 크면 그보다 오른쪽에 있는 모든 레코드는 탐색 키보다 크므로 더는 탐색할 필요가 없음
  • 따라서 왼쪽의 레코드들만 탐색하면 됨
  • 중앙 레코드가 탐색 키보다 작으면 오른쪽만 탐색하면 됨
  • 결국 이진 탐색에서는 단계마다 검색해야 할 레코드의 수가 반으로 줄어듦

이진 탐색 알고리즘

순환 구조

def binary_search(A, key, low, high):
    if (low <= high): # 항목들이 남아 있으면(종료 조건)
        middle = (low + high) // 2 # middle 계산
        if key == A[middle]: # 탐색 성공
            return middle # 중앙 레코드의 인덱스 반환
        elif (key < A[middle]): # 왼쪽 부분 리스트 탐색 -> 순환호출
            return binary_search(A, key, low, middle-1)
        else: # 오른쪽 부분 리스트 탐색 -> 순환 호출
            return binary_search(A, key, middle+1, high)
    return -1 # 탐색 실패 -1 반환

반복 구조

def binary_search_iter(A, key, low, high):
    while low <= high: # 항목이 남아 있는 동안 반복
        middle = (low + high) // 2
        if key == A[middle]:
            return middle
        elif key > A[middle]:
            low = middle + 1
        else:
            high = middle - 1
    return -1

이진 탐색은 얼마나 빠를까?

  • 테이블의 크기를 $n = 2^k$라고 두면, 한 번 비교할 때마다 남은 탐색 구간의 길이는 대략 절반이 되므로 지수는 한 칸씩 줄어듦

$$ 2^k \rightarrow 2^{k-1} \rightarrow 2^{k-2} \rightarrow \cdots \rightarrow 2^0 = 1 $$

  • 위처럼 지수가 $k$에서 $0$까지 $k+1$개의 단계가 등장함
  • $n = 2^k$이면 $k = \log_2 n$이므로, 비교 횟수는 $\log_2 n$에 비례하는 차수임
  • 빅오 표기에서는 보통 $O(\log n)$으로 쓰고, 밑을 적으면 $O(\log_2 n)$과 같음 (밑이 달라도 상수 배 차이만 남음)
  • 예를 들어, $n \approx 10^9$인 정렬된 배열에서 순차 탐색의 평균 비교는 대략 $\dfrac{n}{2}$ 수준(약 5억 번)이지만, 이진 탐색은 $\log_2 n \approx 30$번 안팎의 비교로 끝남

이진 탐색의 특징

  • $O(\log n)$ (또는 $O(\log_2 n)$)의 매우 효율적인 탐색 방법임

  • 반드시 배열이 정렬되어 있어야 사용할 수 있음

  • 테이블이 한 번 만들어지고, 이후 변경되지 않고 탐색 연산만 처리한다면 이진 탐색이 최고의 선택 중 하나임

  • 정렬된 테이블에 레코드를 삽입하기 위해서는 $n$에 비례하는 시간, 즉 $O(n)$이 소요됨

  • 데이터의 삽입이나 삭제가 빈번한 응용에는 이진 탐색이 좋지 않음

  • 탐색은 효율적이지만 비효율적인 삽입과 삭제 연산이 더 많이 처리된다면 전체적으로는 불리할 수 있기 때문임

  • 이런 응용에서는 이진 탐색 트리와 같은 다른 방법을 사용하는 것이 좋음

  • 이진 탐색은 주로 테이블이 배열 구조인 경우에만 사용함

  • 탐색 과정에 중앙 요소를 찾아야 하는데, 배열 구조에서는 중앙 요소의 위치를 바로 계산할 수 있기 때문임

  • 이에 비해 연결된 구조에서는 시작 노드와 마지막 노드는 알고 있더라도 중앙에 있는 노드를 찾기는 쉽지 않음

  • 물론 찾을 수는 있지만 바로 알 수 없고 시간이 걸림

  • 이것은 이진 탐색 알고리즘의 장점을 상쇄시켜 버림

보간 탐색

  • 추후 작성할 예정