탐색 알고리즘

탐색 알고리즘

 

 우리가 자료구조를 사용하는 이유는 근본적으로는 효율적으로 데이터(정보)를 저장하기 위함이지만,

결국 저장한 정보를 다시 탐색해서 찾아 쓰기 위함이다.

따라서 자료구조의 설계 또는 선택에는 저장 효율도 중요하지만, 이에 못지않게 탐색 효율도 고려해야 한다.

 

 

        키 와 레코드

 자료구조가 저장하는 데이터 하나의 단위를 레코드라고 한다면, 키는 레코드의 서브필드에 해당한다.

키는 자료구조의 내부 레코드들 간의 정렬, 또는 탐색에 활용되는 정보이다.

    cf) 서브필드(subfield) - 개념이 정해진 정보 단위를 수록하는 필드의 부분.

 

 

이진탐색 (Binary Search)

 이진탐색은 이미 정렬되어있는 데이터를 기반으로 한다.

한 번의 탐색이 가해질 때 마다 문제의 크기를 반으로 줄임으로 써, 탐색의 범위를 절반으로

줄여 나간다. 따라서 이진탐색의 효율은  이다.

 

다음은 자료구조가 배열 기반일 경우, 재귀적으로 구현한 이진탐색트리의 의사코드이다.

template<typename T> int BinarySearch(T _pArr[], int _iFirst, int _iLast, T _Key)        int iMid = (_iFirst + _iLast) / 2;        // 키 값이 iMid 인덱스에 있는 값과 같다면      if (_Key == _pArr[iMid])          return iMid; // 해당 인덱스를 반환(재귀 탈출조건)        // 키 값이 iMid 인덱스에 있는 값보다 작다면, 왼쪽범위에서 찾는다.      else if (_Key < _pArr[iMid])         return BinarySearch(_pArr, _iFirst, iMid - 1, _Key);        // 키 값이 iMid 인덱스에 있는 값보다 크다면, 오른쪽 범위에서 찾는다.      else          return BinarySearch(_pArr, iMid, _iLast, _Key);

 

 

 

보간탐색 (Interpolation Search)

  보간탐색 역시 정렬되어있는 레코드를 기반으로 한다.

보간탐색은 찾고자 하는 데이터가 대략적으로 어느 위치에 있을지 예측하는 탐색방법이다.

다음과 같은 정렬된 데이터에서 킷값이 130인 레코드를 찾는다고 하자.

 

인덱스	0	1	2	3	4	5	6	7	8	9	10
키	15	22	46	55	64	73	89	98	111	130	156

 

찾아야 할 인덱스가 9이며, 이진탐색이었다면 중간 인덱스인 6부터 찾아나갈 것이다.

하지만 보간탐색의 탐색 식은 다음과 같다.

 

 

따라서 결과값은 8.15 다.

 

다음은 보간탐색 의사코드 이다.  

 

template<typename T> int InterpolationSearch(T _pArr[], int _iFirst, int _iLast, T _Key)      // 키값이 없었다    if (_iFirst >= _iLast)      return -1;      int iMid = _iFirst + (_iLast - _iFirst) * (_Key - _pArr[_iFirst]) / (_pArr[_iLast] - _pArr[_iFirst]);      // 키값이 iMid 인덱스에 있는 값과 같다면    if (_Key == _pArr[iMid])      return iMid; // 해당 인덱스를 반환(재귀 탈출조건)      // 키값이 iMid 인덱스에 있는 값보다 작다면, 왼쪽범위에서 찾는다.    else if (_Key < _pArr[iMid])      return InterpolationSearch(_pArr, _iFirst, iMid - 1, _Key);      // 키값이 iMid 인덱스에 있는 값보다 크다면, 오른쪽 범위에서 찾는다.    else      return InterpolationSearch(_pArr, iMid + 1, _iLast, _Key);

 

기수탐색 (Radix Search)

 대부분의 탐색에 있어서 문자열은 아주 유용한 키 필드로 활용된다.

문자열을 키 로 하는 레코드들을 탐색할 때 사용되는 방법 중 하나가 바로 기수탐색이다.

 

기수탐색은 먼저 키를 분해하는 작업을 수행한다. 문자열로 된 키를 문자, 비트 단위로 분해하여 탐색트리를 구성한다. 

이 탐색트리를 구성하는 방법에 따라서 디지털 탐색트리, 기수 탐색트리 로 나뉜다.

 

디지털 탐색트리

  키 값에 대응하는 비트 값을 준다. 각 비트자리의 값에 따라 1은 오른쪽, 0 은 왼쪽을 향한다.

트리를 탐색하다가 원하는 값을 찾으면 탐색종료, 비트자리에 따라 경로를　끝까지 탐색하여도

값을 찾지 못했으면 값이 존재하지 않았음을 알 수 있다.

 

기수 탐색트리

 다른 표현으로 트라이(Trie) 라고도 한다. 탐색 또는 검색을 의미하는 Retrieval 의 가운데 스펠이다.

디지털 탐색트리의 레코드가 내부노드와 외부노드 전부 위치하는데 반해, 트라이는 모든 레코드가

외부노드에 위치한다. 따라서 트라이의 내부노드는 아무 값이 없고, 2개의 포인터로만 구성된다.

 

디지털 탐색과 트라이 모두 알고리즘 효율로서는 비슷하나, 디지털 탐색트리의 경우,

레코드를 찾기 위해서 비트 값에 따라 경로를 탐색하는 도중 지속적으로 값의 비교가 일어나는 데에

반해서 트라이는 단 한번만 값을 비교한다.

 

또한 트라이의 모습은 레코드의 입력순서와 무관하게 최종 모습이 항상 동일하다.

키 값의 비트 패턴이 자신의 위치를 이미 결정했기 때문이다.