이 게시글은 윤성우 선생님의 자료구조 강의를 수강 후 나름대로의 내용 정리를 한 것임을 미리 밝힙니다.
스스로의 복습을 위해 작성한 글이므로 심층있는 학습을 위해서는 책의 구매 및 강의수강을 권장합니다.
Prologue
(1) 효율적인 탐색을 위해서는 어떻게 찾을까 만을 고민해서는 안된다. 그보다는 효율적인 캄색을 위한 저장방법을 우선 고민해야 한다.
(2) 효율적인 탐색이 가능한 대표적인 자료구조는 트리, 그 중 이진트리이다.
1. 보간 탐색 (Interpolation Search)
(1) 프롤로그
이진 탐색을 좀 더 개선시킨 탐색 알고리즘
예시를 들어보자.
최솟값이 10, 최댓값이 30인 정수들이 오름차순으로 정렬되어 있는 배열이 있다고 가정하자.
여기서 11의 위치를 찾는다고 할 때, 11은 분명 최솟값에 훨씬 가깝다.
즉, 왼쪽으로 치우쳐져 있는 것이다.
그러나, 이진탐색은 그렇건 말건 중간부터 탐색을 시작한다.
이에 반해 보간 탐색은 11이라는 데이터가 나오면, 10에 가깝다는 판단을 하긴 하는데
그 뿐만이 아니라 데이터가 비례해서 저장되어 있다는 가정을 하고 좀 더 근접한 위치를 찍으려는 노력을 하는 것이 보간 탐색이다.
당연히 데이터가 랜덤성을 가지면 무조건 한번에 찾는다는 확신은 절대 없지만 그럼에도 불구하고
보간 탐색은 단번에 탐색 대상을 찾을 확률이 어느 정도 존재한다.
다만 생각해야 할 것은
위치를 계산하기 위해서는 연산이 필요하다는 것이다.
(2) 보간 탐색 -> 비례식 구성 //추가적으로 설명되는 알고리즘이므로 스트레스받을 필요 X
Q/A = (S - low) / (high - low) //비례한다고 가정하고 이는 실수 연산이라 가정할 때 성립!
(S는 탐색할 위치)
S = Q * (high - low)/ A + low
이는 비례한다고 가정했을 때이기 때문에 삑사리(?)가 나지만 어느 정도 근접할 수 있다.
