[자료구조] 보간 탐색의 이해(1)

[자료구조] 보간 탐색의 이해(1)

탐색이라 하면 원하는 데이터를 찾는 것이라 쉽게 알 수 있다.

하지만 효율적으로 데이터를 찾아내기 위해서 탐색의 방법을 개선할 수 있지만

이 방법에는 한계가 있고 탐색에 유용하도록 데이터를 저장하는 방식으로 개선할 수 있다.

즉, 어떻게 탐색할 것인가가 아니라, 탐색에 용이한 데이터의 저장방식이 무엇인가를 생각해야 한다.

이번 포스팅은 데이터의 저장방식에 대해서는 생각하지 않으나, 이번 탐색을 다루면서

이 부분이 상당히 중요한 부분을 차지 하기 때문에 들어가기에 앞서 이 주제로 포문을 열었다.

1. 이진 탐색

이진 탐색은 우리에게 널리 알려진 탐색 방법으로, 상당한 효율을 가지고 있다.

효율적인 탐색이 가능한 대표적인 자료구조는 트리이며, log2N의 탐색 성능을 가지고 있다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

위의 자료에서 2라는 데이터를 찾기 위해 이진 탐색을 사용할 경우

데이터의 중간인 10부터 시작해서 원하는 데이터를 찾을 때까지 필요없는 부분은 버려나간다.

예를 들어 5는 10보다 작기 때문에 10보다 큰 10개의 데이터는 이제 안중에도 없는 것이다.

이렇듯 점점 반으로 줄여나가기 때문에 log2N의 수행성능을 보이며, 상당히 우수한 탐색 알고리즘이다.

참고 : http://terms.naver.com/entry.nhn?docId=2270440&cid=51173&categoryId=51173

2. 보간 탐색

여기서 더욱 발전된 것이 보간 탐색이라는 것인데

중간을 찍어 점점 줄여나가는 이진 탐색과는 달리

탐색하려는 대상에 비례하여 탐색의 위치를 결정하는 것이다.

2를 찾는다 하면 10을 찍는 것 보다 3이나 4등 2에 좀 더 가까운 수를 찍어 탐색 속도를 개선하는 것이다.

이진 탐색과 보간 탐색은 모두 정렬이 완료된 데이터를 대상으로 탐색을 진행한다.

보간 탐색은 탐색에 좀 더 효율적인 위치를 찍기 위한 계산 비용이 필요한데,

이 비용을 지불하더라도 이진 탐색보다는 훤씬 좋은 알고리즘으로 평가 받는다.

이제 이 위치를 찍기 위한 비례식을 구성하는 방법을 배워볼텐데, 다음 포스팅에 진행하도록 하겠다.

마지막으로 다시 한번 말하자면 이번에 배울 내용에서 가장 중요한 내용은

효율적인 탐색을 위해서는 '어떻게 찾을까'만을 고민해서는 안 되고,

그 보다는 효율적인 탐색을 위한 저장 방법을 우선 고민해야 한다는 것이다.

다음 포스팅부터 차차 위의 내용을 이해해 보도록 하겠다.