검색 (Search)

검색의 이해

• 검색 (Search)
  • 필요한 자료를 찾는 행동
• 탐색 키 (Search Key)
  • 저장한 자료를 구별하여 인식할 수 있는 키
  • 자료를 검색한다는 것은 원하는 탐색키를 가진 항목을 찾는다는 뜻이다.
• 검색 성공 (Hit)
  • 자료 속에서 원하는 항목을 찾은 경우
• 검색 실패 (Miss)
  • 자료 속에서 원하는 항목을 찾지 못한 경우
• 검색 연산은 삽입 연산과 삭제 연산을 할 때도 필요하다.
  • 삽입 또는 삭제를 위해서는 먼저 그 위치를 찾아야 하기 떄문이다.
• 검색 방법의 효율성은 사용하는 자료구조와 자료의 배열 상태에 따라 달라진다.
  • 해결해야 하는 문제와 상황에 따라 최적의 검색 방법을 사용해야 한다.
• 종류
  • 수행되는 위치
    • 내부 검색 (Internal Search)
      • 메모리 내에서 수행한다.
    • 외부 검색 (External Search)
      • 메모리 외부의 보조 기억장치에서 수행된다.
  • 검색 방법
    • 비교 검색 (Comparison Search)
      • 검색 대상의 키를 비교하여 검색한다.
      • 순차 검색, 이진 탐색, 트리 검색이 해당한다.
    • 계산 검색 (Non-comparison Search)
      • 계수적인(수를 계산하여 값을 얻는) 성질을 이용한 계산으로 검색한다.
      • 해싱이 해당된다.

순차 검색 (Sequentail Search)

• 가장 쉽고 단순한 검색 방법이다.
• 종류
  • 기본 순차 검색
    • 항목을 순서대로 비교하면서 검색한다.
  • 색인 순차 검색
    • 검색의 효율을 높이기 위해 인덱스 테이블을 사용하여 검색한다.

기본 순차 검색 (Basic Sequentail Search)

• 가장 간단하고 직접적인 방법이다.
• 배열이나 연결 리스트로 구현된 선형 자료구조에서 순서대로 비교하며 원하는 항목을 찾는다.
• 검색해야 하는 자료의 양에 따라 효율이 달라진다.
• 순차 검색이라고만 하면 기본 순차 검색을 의미한다.
• 선형 검색(Linear Search)라고도 부른다.
• 시간 복잡도
  • 정렬되있지 않은 자료를 순차 검색하는 경우
    • O(n)
  • 정렬되있는 자료를 순차 검색하는 경우
    • O(n)
• 시간 복잡도가 동일한 이유는 결국 최악의 경우에는 n개의 자료 전부를 검색해야할 수도 있기 때문이다.
  • 물론 정렬되있는 경우에 비교 횟수가 많이 줄어드는 것은 사실이다.

색인 순차 검색 (Index Sequentail Search)

• 인덱스 테이블을 사용하여 탐색의 범위를 줄임으로써 검색 효율을 높인 방식
• 인덱스 테이블은 배열에 정렬되어 있는 자료 중에서 일정한 간격으로 떨어져 있는 원소들을 가지고 있다.
• 색인 순차 검색은 정렬된 자료일 때만 사용한다.
• 인덱스 순차 검색이라고도 부른다.
• 동작 원리
  1. 자료가 저장되어 있는 배열의 크기는 n이고, 인덱스 테이블의 크기는 m으로 지정한다.
  2. 배열에서 n/m 간격으로 떨어져 있는 원소와 원소의 인덱스를 인덱스 테이블에 저장한다.
  3. 찾고자 하는 키값을 인덱스 테이블에서 검색하여
     indexTable[i].key <= key < indexTable[i+1].key를 만족하는 i를 찾아서 검색 범위를 정한다.
  4. 정해진 검색 범위에 대해서만 순차 검색을 수행한다.
• 색인 순차 검색의 실행 시간 성능은 인덱스 테이블의 크기 m에 따라 달라진다.
  • 인덱스 테이블과 검색 시간의 관계를 고려하여 인덱스 테이블의 크기를 정해야 한다.
  • 인덱스 테이블의 크기 m이 작아지면 인덱스 테이블을 구성하는 배열 원소의 간격 n/m이 커지므로
    배열에서 검색해야 하는 범위가 커진만큼 순차 검색의 비교 연산도 많아진다.
  • 인덱스 테이블의 크기 m이 커지면 인덱스 테이블을 구성하는 배열 원소의 간격 n/m이 작아지므로
    배열에서의 순차 검색에 대한 비교 연산은 줄어들지만,
    그만큼 검색 범위를 찾기 위해 인덱스 테이블에서의 검색 시간이 늘어난다.
• 시간 복잡도
  • O(m + n/m)

이진 검색 (Binary Search)

• 자료 가운데 있는 항목을 키값과 비교하여 검색하는 방법
  • 키값이 더 크면 오른쪽 부분을 검색한다.
  • 키값이 더 작으면 왼쪽 부분을 검색한다.
• 키를 찾을 때까지 이진 검색을 순환적으로 반복하여 수행함으로써 검색 범위를 반으로 줄여가면서 빠르게 검색한다.
• 이진 검색은 정렬되어 있는 자료를 검색할 때만 사용할 수 있다.
• 이진 검색은 검색 범위를 반으로 분할하고 검색하는 작업을 반복하므로 분할 정복 기법을 이용한 방법이다.
  • 참고
• 가운데 있는 값을 기준으로 왼쪽과 오른쪽 두 부분으로 나누어서 검색하므로
  이분 검색 또는 보간 검색(Interpolation Search)이라고 부르기도 한다.
• 시간 복잡도 O(log₂n)

이진 트리 검색 (Binary Tree Search)

• 이진 탐색 트리를 사용하여 검색하는 방법
• 이진 탐색 트리 (Binary Search Tree)
  • 루트 노드를 기준으로 왼쪽 서브 트리는 루트 노드보다 키값이 작은 원소로 구성하고,
    오른쪽 서브 트리는 루트 노드보다 키값이 큰 원소로 구성한 이진 트리
• 이진 트리 검색은 이진 탐색 트리의 특성을 이용하여 쉽게 검색할 수 있다.
• 이진 트리 검색은 원소 삽입이나 삭제 연산에 대해
  항상 이진 탐색 트리를 재구성하여 유지해야 하기 때문에 오버헤드가 발생한다.
• 시간 복잡도
  • O(h)
  • h는 트리의 높이를 의미한다.

해싱 (Hashing)

• 산술적인 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색 방식
  • 키값을 비교하여 검색하는 방법이 아니다.
• 해시 함수 (Hash Function)
  • 키값을 원소 위치로 변환하는 함수
• 해시 테이블 (Hash Table)
  • 해시 함수에 의해 계산된 주소 위치에 항목을 저장한 표
• 동작 원리
  1. 키값에 대해서 해시 함수를 계산하여 주소를 구한다.
  2. 구한 주소에 해당하는 해시 테이블로 이동한다.
  3. 해당 해시 테이블에 찾는 항목이 있는지 찾아본다.

해싱 관련 용어

• 동거자 (Synonym)
  • 서로 다른 키값을 가지지만 해시 함수에 의해 같은 버킷에 저장된 키값
  • 키값의 개수만큼 버킷을 많이 만들면 메모리 공간이 낭비된다.
    • 버킷의 수를 줄이고 각 버킷마다 슬롯을 여러 개 두어서 해시 함수의 결과가 같은 키값끼리 모아서 저장한다.
• 충돌 (Collision)
  • 키값이 서로 다르지만 해시 함수에 의해 주어진 버킷 주소가 같은 경우
  • 해당 버킷에 비어있는 슬롯이 부족하여 동거자로 지정할 수 없을 떄는 오버플로우가 발생한다.
    • 버킷에 비어있는 슬롯이 없는 상태를 포화 버킷 상태라고 부른다.
• 키값 밀도
  • 사용 가능한 전체 키값 중에서 현재 해시 테이블에 저장되어 실제 사용되고 있는 키값의 개수
  • 키값 밀도 = 실제 사용 중인 키값의 개수 / 사용 가능한 키값의 개수
• 적재 밀도
  • 해시 테이블에 저장 가능한 키값의 개수 중에서 현재 해시 테이블에 저장되어 실제 사용되고 있는 키값의 개수
  • 적재 밀도 = 실제 사용 중인 키값의 개수 / 해시 테이블에 저장 가능한 전체 키값의 개수
  • 적재 밀도 = 실제 사용 중인 키값의 개수 / (버킷 개수 * 슬롯 개수)

해싱 함수

• 키값의 위치를 계산하는 해시 함수
• 좋은 해시 함수의 조건
  • 해시 함수는 계산이 쉬어야 한다.
  • 해시 함수는 충돌이 적어야 한다.
  • 해시 테이블에 고르게 분포할 수 있도록 주소를 만들어야 한다.
• 종류
  • 중간 제곱 함수
  • 제산 함수
  • 승산 함수
  • 접지 함수
    • 이동 접지 함수
    • 경계 접지 함수
  • 숫자 분석 함수
  • 진법 변환 함수
  • 비트 추출 함수

해싱에서 오버플로우를 처리하는 방법

선형 개방 주소법

1. 해시 함수로 구한 버킷에 빈 슬롯이 없어서 오버플로우가 발생한다.
2. 그 다음 버킷에 빈 슬롯이 있는지 조사한다.
3. 빈 슬롯 존재 여부에 따라 처리한다.
   • 빈 슬롯이 있는 경우
     • 해당 슬롯에 키값을 저장한다.
   • 빈 슬롯이 없는 경우
     • 다시 그 다음 버킷을 조사한다.
4. 과정을 반복한다.

체이닝

• 해시 테이블의 구조를 변경하여 각 버킷에 하나 이상의 키값을 저장할 수 있도록 하는 방법
• 버킷에 슬롯을 동적으로 삽입하고 삭제하기 위해 연결 리스트를 사용한다.
• 각 버킷에 대한 헤드 노드는 1차원 배열이다.
• 슬롯은 헤드 노드에 연결 리스트 형태로 이어진다.
• 버킷 내에서 원하는 슬롯을 검색하려면 연결 리스트를 선형 검색한다.