[자료구조]CH10. 검색

참조 : C로 배우는 쉬운 자료구조(이지영 저)

공부 날짜 : 21.04.04

 

 

<Section 1> 검색의 이해

 

자료를 만들고 저장하고 정렬하는 것은 자료를 사용하기 위함이고, 사용하려면 자료 중에서도 원하는 항목을 찾아야 하는데 이것이 바로 검색(Search)이다.

 

저장한 자료는 그 자료를 구별하여 인식할 수 있는 키를 가지고 있는데, 이것을 탐색키(Search Key)라고 한다.

자료를 검색하는 것은 원하는 탐색키를 가진 항목을 찾는 것이다.

원하는 항목을 찾으면 검색 성공(Hit), 못 찾으면 검색 실패(Miss)라고 한다.

 

검색은 메모리 내에서 수행하는 내부 검색과 메모리 외부에 있는 보조 기억 장치에서 진행하는 외부 검색,

검색 대상의 키를 비교하여 검색하는 비교 검색과 계수적인 성질을 이용한 계산으로 검색하는 계산 검색으로 분류한다.

 

 

<Section 2> 순차 검색

 

1. 순차 검색(Sequential Search)

 

 일렬로 나열된 자료를 처음부터 마지막까지 순서대로 검색하는 방법으로 선형 검색(Linear Search)이라고도 한다.

자료의 양에 따라 효율이 달라지지만 알고리즘이 단순하여 구현이 쉽다.

 

 1) 정렬되지 않은 자료를 순차 검색

 

 첫째 원소부터 마지막 원소까지 순서대로 키값이 일치하는 원소가 있는지 비교하여 찾는다. 

키 값이 일치하는 원소를 찾으면 그 원소가 몇 번째 원소인지 반환한다.

일치하는 원소가 없으면 검색 실패가 된다.

 

n개의 자료에 대해 필요한 메모리 공간은 n이며 시간 복잡도는 O(n)이다.

 

 

* 정렬되지 않은 자료의 순차 검색 알고리즘

 

 sequentialSearch1(a[] , n , key) //배열과 배열의 크기, 찾으려는 값 파라미터로 넘김

     i ← 0; //0 인덱스부터

     while (i < n and a[i] != key) do { //처음부터 끝까지 찾으려는 값과 일치하는지 비교

          i ← i + 1;

     }

     if (i < n) then return i; //n보다 작은 수라면 검색 성공하여 자리 반환

     else return -1; //아니면 검색 실패하여 -1 반환

 end sequentialSearch1() 

 

 

 2) 정렬된 자료를 순차 검색

 

 정렬된 자료를 순차 검색할 때는 원소의 키 값이 찾는 키 값보다 크면 찾는 원소가 없는 것이 되므로 더 이상 검색을 진행하지 않아도 실패를 알 수 있다.

 

 

* 정렬된 자료의 순차 검색 알고리즘

 

 sequentialSearch2(a[] , n , key)

      i ← 0;

      while (a[i] < key) do {

           i ← i + 1;

      }

      if (a[i] = key) then return i; //검색성공하면 자리 반환

      else return -1;

 end sequentialSearch2()

 

 

2. 색인 순차 검색(Index Sequential Search)

 

 인덱스 순차 검색이라고도 한다.

인덱스 테이블을 사용하여 탐색의 범위를 줄임으로써 검색 효율을 높인 방법이다.

정렬된 자료일 때만 사용이 가능하다.

 

① 배열의 크기가 n이고, 인덱스 테이블의 크기가 m일 때 배열에서 n/m 간격으로 떨어져 있는 원소와 원소의 인덱스를 인데스 테이블에 저장한다. 

 

② 찾고자 하는 키 값을 인덱스 테이블에서 검색하여 indexTable[i].key<=key<indexTable[i+1].key 를 만족하는 i를 찾아 검색번위를 정한다.

 

③ 해당 번위에서 순차 검색을 수행한다.

 

 

* 정렬된 자료의 색인 순차 검색 알고리즘

 

 indexSearch(a[] , n , key)

     for (i ← 0 ; i < m ; i ← i+1)do

         if ((indexTable[i].key <= key) and (indexTable[i+1].key > key)) then { //인덱스 테이블에서 범위를 찾음

             begin ← indexTable[i].index;

             end ← indexTable[i+1].index;

             break;

     }

     sequentialSearch2(a[],begin,end,key); //범위 내에서 정렬된 자료를 순차 검색한다.

 end indexSearch()

 

 

* 인덱스 테이블 알고리즘

 

 makeIndexTable(a[] , size , key)

       n ← size / m; //배열a의 크기를 인덱스 테이블 크기로 나눠 한 범위에 들어갈 원소의 개수 구함

       if (size mod m > 0) then n ← n + 1;

       for (i ← 0 ; i < m ; i ← i + 1) do { //인덱스 테이블에 삽입

           indexTable[i].index ← i * n; //해당 인덱스 값 삽입 

           indexTable[i].key ← a[i*n]; //해당 원소값 삽입

       }

 end makeIndexTable() 

 

 

<Section 3> 이진 검색

 

 이진 검색(Binary Search)은 자료 가운데 있는 항목을 키 값과 비교하여 키 값이 더 크면 오른쪽 부분, 키 값이 더 작으면 왼쪽 부분을 검색하는 방법이다.

이분 검색, 보간 검색이라고도 하며 시간 복잡도는 O(log2(지수)n)이다.

 

 

* 이진 검색의 알고리즘

 

 binarySearch(a[] , begin , end , key)

     middle ← (begin + end) / 2; //배열의 가운데 인덱스

     if (key = a[middle]) then return 1; //가운데 원소와 키값이 같으면 1 반환

     else if (key < a[middle]) then binarySearch(a[] , begin , middle-1 , key);

     //키 값이 더 작으면 왼쪽 부분에서 이진 검색 

     else if (key > a[middle]) then binarySearch(a[] , middle+1 , end , key);

     //키 값이 더 크면 오른쪽 부분에서 이진 검색

     else return -1; //검색 실패시 -1 반환

 end binarySearch()

 

 

<Section 4> 이진 트리 검색

 

 이진 트리 검색(Binary Tree Search)은 이진 탐색 트리를 사용하여 검색하는 방법이다.

[자료구조]CH7. 트리(이진 탐색 트리)

이진 탐색 트리의 특성을 이용하여 검색이 쉽지만, 원소 삭제나 삽입에 대해 재구성이 일어나므로 오버헤드가 발생한다.

 

 

<Section 5> 해싱

 

1. 해싱의 개념

 

 해싱(Hashing)은 산술적인 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색 방식이다.

키 값을 원소 위치로 변환하는 함수를 해시 함수(Hash Function)이라고 하고.

해시 함수에 의해 계산된 주소 위치에 항목을 저장한 표를 해시 테이블(Hash Table)이라고 한다.

 

키 값에 대해 해시 함수로 주소를 구하고, 구한 주소에 해당하는 해시 테이블로 이동하여 항목을 찾는 것이다.

해시 함수에 의해 계산된 주소가 버킷의 주소가 된다.

 

2. 해싱 관련 용어

 

 1) 동거자

  키 값의 수만큼 버킷을 만들면 메모리 낭비이므로 버킷 안에 슬롯을 여러 개 두어 해시 함수로 만든 주소가 같은 키 값들을 같은 버킷에 담는다. 이렇게 서로 다른 값을 가지지만 해시 함수에 의해 같은 버킷에 저장된 키 값을 동거자(Synonym)라고 한다.

 

 2) 충돌

  키 값이 다른데도 해시 함수에 의해 주어진 버킷 주소가 같은 경우를 충돌(Collision)이라고 한다.

만약 충돌이 일어났을 때 비어있는 슬롯이 없다면 더이상 저장될 공간이 없으므로 오버플로우가 일어난다.

 

 3) 키값 밀도와 적재 밀도

  키값 밀도 = 실제 사용 중인 키 값의 개수 / 사용 가능한 키 값의 개수

  적재 밀도 = 실제 사용 중인 키 값의 개수 / 해시 테이블에 저장 가능한 전체 키 값의 개수

               = 실제 사용 중인 키 값의 개수 / (버킷 개수 * 슬롯 개수)

 

3. 해시 함수

 키 값의 위치를 계산하는 함수이다.

 

좋은 해시 함수의 조건은

① 계산이 쉬워야 한다.

② 충돌이 적어야 한다.

③ 해시 테이블에 고르게 분포할 수 있도록 주소를 만들어야 한다. 

 

 1) 중간 제곱 함수

 키 값을 제곱한 결과값에서 중간에 있는 적당한 비트를 주소로 사용하는 방법이다.

 버킷 수에 따라 필요한 최소 비트 수가 달라진다.

 만약 256개의 버킷이 있다면 256=2^8 이므로 8비트를 주소로 사용한다.

 

 2) 제산 함수

 나머지 연산자 mod를 사용하는 방법이다.

 

 3) 승산 함수

  키 값과 정해진 실수 알파를 곱한 결과에서 소수점 이하 부분만을 테이블 크기와 곱하여 그 정수값을 주소로 사용한다.

 

 4) 접지 함수 

  키 값을 테이블 인덱스의 비트 수와 같은 크기로 분할한 후 분할된 부분을 모두 더하여 해시 주소를 만드는 방법이다.

 이동 접지 함수와 경계 접지 함수가 있다.

 

 5) 숫자 분석 함수

  가장 고르게 분포된 자릿수부터 해시 테이블의 주소를 자릿수만큼 차례로 뽑아서 만든 수를 역순으로 바꾸어 주소로  사용된다.

 

 6) 진법 변환 함수

  키값이 10진수가 아닐 때 10진수로 변환하고, 해시 테이블 주소로 필요한 자릿수만큼만 하위 자리의 수를 사용한다.

 

 7) 비트 추출 함수

  해시 테이블의 크기가 2^k일 때, 키 값을 이진 비트로 놓고 임의의 위치에 있는 비트들을 추출하여 주소로 사용한다.

 

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

 1) 선형 개방 주소법

  선형 조사법이라고도 한다. 

 해시함수로 구한 버킷에 빈 슬롯이 없어서 오버플로가 발생하면 그 다음 버킷에 빈 슬롯이 있는지 조사한다.

 

 2) 체이닝

  해시 테이블의 구조를 변경하여 각 버킷에 하나 이상의 키 값을 저장할 수 있도록 하는 방법이다. 

 연결 리스트를 사용하여 값을 저장하고 삭제하는 것이다.