[자료구조] 탐색 (Search)

공부용으로 작성되는 페이지입니다. 틀린 부분이나 환경에 따라 오류가 발생할 수 있습니다. 

 

---

 

탐색이란?

기억공간에 저장된 특정 데이터를 착아내는 작업을 말한다.

1. 순차 탐색 : 순서화 되어 있지 않은 데이터를 첫 번째부터 차례대로 탐색하는 방식
2. 제어 탐색 : 반드시 순서화 되어있는 데이터를 탐색하는 방식 

비유하자면 어지럽혀진 창고에서 물건을 찾는 것이 순차 탐색, 정돈된 도서관에서 책을 찾는 것이 제어 탐색이라 볼 수 있다.

제어탐색

즉 앞서 배웠던 정렬을 토대로 한 번 순서화된 데이터에서 탐색하는 방식을 제어 탐색이라한다.

제어 탐색 방식은 아무리 빨라도 시간 복잡도가 O(logN)이라는 특징을 가진다. 

 

1. 이진 탐색 (Binary Search)
2. 피보나치 탐색 (Fibonacci Search)
3. 보간 탐색 (Interpolation Search)
4. 블록 탐색 (Block Search)
5. 이진 트리 탐색 (Binary Tree Search)

 

 

이진 탐색

전체 데이터를 두 개의 서브 데이터 세트로 분리하며 찾고자 하는 데이터를 탐색하는 방식이다.

비교 횟수를 거듭할수록 검색 대상이 되는 데이터 수가 절반으로 줄어들기 때문에 탐색 알고리즘 중 효율이 가장 좋다.

중간 데이터를 기준으로 탐색한다고 생각하면 된다. (예시의 경우엔 5가 기준)  

탐색이 반복 될 때마다

 

순차 탐색과 이진 탐색은  앞서 Big-O 표기법을 배우면서 한 번 언급했기 때문에 헷갈리면 2강을 다시 시청하자.  

피보나치 탐색 

피보나치 수열에 따라 비교할 대상을 선정하는 방식. 피보나치 수열이란 앞의 두 수의 합이 바로 뒤의 수가 되는 배열을 말한다.

 

ex) 0, 1 , 1, 2, 3, 5 

 

0+1 = 1 , 1 +1 = 2 , 2 + 3 = 5 ... 앞의 두 수의 합이 바로 뒤의 수가 되므로 피보나치 수열의 조건을 만족하는 배열이다. 

 

이런 특성상 피보나치 탐색은 가감산(+,-)만 활용하기 때문에 효율이 우수하다. 

보간 탐색

찾으려는 데이터가 있을 법한 부분의 키를 택하여 탐색하는 방식이지만, 예측을 해야하므로 프로그래밍이 불가하다.

물론, 기초 강의인만큼 생략한 것으로 보여서 추가로 공부하였다.

 

보간 탐색은 이진 탐색과 유사한 알고리즘이다.

 

정렬된 리스트에서 범위를 좁혀나가는 방식이지만, 탐색 위치를 정하는 방식에서 차이점이 발생한다.

이진 탐색의 경우 항상 탐색 위치가 중간 값인 반면 보간 탐색의 경우 검색 Key값에 따라 다른 위치로 이동하게 된다.

이 과정에서 검색한 Key값이 어디에 있을지 '판단(예측)'이 필요하기 때문에 비교적 프로그래밍하기 어려운 건 맞는 거 같다. 

 

따라서 보간 탐색은 데이터가 인덱스 값에 비례하여 분포(=선형적)되어 있을 때 탐색 효율이 좋다. 

 

블록 탐색 

여러 데이터를 Block 단위로 구성하여 저장해놓고, 어느 Block에 있는지 확인하여 탐색하는 방식이다.

정렬되어 있는 데이터를 기반으로 하는 다른 탐색과 달리 각 블록 내 데이터들이 순차적으로 저장될 필요는 없지만 

블록과 블록 사이에는 순차적인 구조로 저장되어야 한다. 

 

즉, 블록 내에서 숫자의 순서는 정렬화되어 있지 않아도 되지만 Block2 내부의 데이터들은 Block1 데이터들보다 value가 높아야한다. 

 

ex) 숫자 15를 블록 탐색으로 찾 경우 

 

Index : 3, 6, 12, 14, 17 

 

Block 1 : 9, 15, 18, 2

Block 2 : 21, 29, 34, 24

Block 3 : 45, 39, 43, 40

 

Block2는 Block1의 가장 큰 값인 18보다 큰 값들로만 구성되어야 할 것이다. 

Index의 값을 참고해보면, 3 = 18  6 = 29, 12 = 40 이다.

우리가 찾아야하는 숫자 15는 Index 3보다도 작은 15이므로 일단 Block1 내부에 있을 것이라고 알 수 있다. 

 

그러면 블록 1을 순차적으로 탐색하여서 15를 찾는 것이다. 

이진 트리 탐색 

이진 검색 트리로 구성하여 탐색하는 방식이다.

이진 트리란 왼쪽 자식 노드의 값은 부모 노드 값보다 작고, 오른쪽 자식 노드 값은 부모 노드 값보다 큰 값을 갖도록 구성한 트리이다. 

 

ex) 숫자 5를 이진 트리 탐색으로 찾아보기

 

우선 트리를 바로 왼쪽 노드만 해도 1-3-5구조로, 왼쪽 자식은 부모 노드 보다 작은 반면 오른쪽 노드는 부모보다 크다. 

이러한 이진 트리에서 이진 검색 트리로 값을 찾아보자.

 

1. 찾고자 하는 데이터를 Root Node와 비교하기 
2. 찾고자 하는 데이터가 Root Node보다 작으면 왼쪽 Sub Tree 검색 
3. 찾고자 하는 데이터가 Root Node보다 크면 오른쪽 Sub Tree 검색 
4. 같은 데이터를 찾으면 검색 종료

해당 예시에서는 우선 7과 비교한다. 5는 7(Root Node)다 작으므로 왼쪽 노드와 비교한다.

3과 비교하면 5가 큰 데이터이므로 오른쪽 노드와 비교한다. 데이터 5를 찾았으므로 검색을 종료한다. 

 

시간을 줄이는 방법 : 해싱

위에 언급한 특징대로, 제어탐색은 아무리 빨라도 시간복잡도가 O(logN)이다.

메모리를 많이 사용하더라도 시간복잡도를 더 줄일 수 있는 방법이 있는데, 이를 해싱(Hasing)이라고 부른다.

해싱에 대해서는 다음 강의에서 배워본다. 

 

 

참고자료

 

[Algorithm | Java] 보간 탐색, 삼진 탐색, 지수 탐색(Interpolation, Terenary, Exponential Search) 알고리즘