알고리즘의 단골 주제 중 가장 큰 꼭지에 해당하는 "검색(Search)"에 대해 시작합니다. 검색은 데이터 집합에서 원하는 데이터를 효율적으로 찾아내는 방법을 연구하는 분야입니다. 책들이 정리되지 않은 상태로 책장에 꽂혀 있다면 원하는 책을 찾기가 매우 어려울 겁니다. 하지만 책의 제목을 기준으로 가나다 순서로 꽂혀 있다면 손쉽게 원하는 책을 찾을 수 있습니다. 이렇게 검색은 데이터 집합을 어떻게 구성해야 효율적으로 데이터를 찾을 수 있는지에 대한 연구가 주를 이룹니다. 그래서 검색은 자료구조(Data Structure)와 밀접한 연관을 가집니다.
검색은 인터넷을 하면서 일상적으로 하는 행동이기도 합니다. 약간 범주가 다르긴 하지만 검색 엔진을 통해서 원하는 정보를 찾는 건 하루에도 수십번 수백번 반복하는 행위입니다. 그만큼 이 검색은 실제 업무에서 매우 빈번하게 사용되기 때문에 그 중요성도 매우 크다고 하겠습니다.
이번 장에서는 검색 문제의 정의와 개요에 대해 살펴보고, 가장 단순한 검색 알고리즘은 순차 검색, 이분 검색, 내분 검색 등에 대해서 알아보고 구현해 봅니다.
강의 자료
강의 동영상
14.0 기본 검색 - 시작 : 정렬과 더불어 또 하나의 큰 주제인 검색(Search)에 대해 시작합니다. 이번 장에서는 검색 문제의 정의와 기본적인 검색 알고리즘들에 대해 알아봅니다.
14.1 검색의 개요 : 검색은 말 그대로 데이터 집합에서 원하는 데이터를 빨리 찾고자 하는 문제입니다. 검색 알고리즘은 조건에 따라 그 해결 방법이 다릅니다. 1차원 단일 키 검색으로 한정하여 다양한 검색 알고리즘들을 살펴 봅니다.
14.2 검색을 위한 Map 클래스 : 현대적인 언어에서 검색 알고리즘은 Map이라는 형태로 제공됩니다. 다양한 검색 알고리즘에 대해 동일한 인터페이스를 제공하기 위해 이 Map 클래스를 정의합니다.
14.3 순차 검색 : 순차 검색은 가장 단순한 검색법입니다. 임의의 순서로 배치된 데이터 집합에서 처음부터 자료를 찾을 때까지 순차적으로 비교하여 나갑니다. 그리고 실제로 순차 검색을 구현해 봅니다.
14.4 순차 검색을 연결리스트로 구현 : 앞서 순차 검색을 배열에서 구현해 보았는데, 데이터의 추가/삭제시 비용이 많이 발생하는 문제가 있었습니다. 이를 개선하기 위해 연결리스트를 이용하여 순차 검색을 구현해 봅니다.
14.5 이분 검색의 개념 : 이분 검색(Binary Search)은 현업에서 많이 쓰이는 검색 알고리즘으로 데이터 집합이 순서대로 배열되어 있다면 매우 효율적으로 검색할 수 있는 방법입니다. 이분 검색의 개념에 대해서 알아봅니다.
14.6 이분 검색의 구현 : 앞서 배운 이분 검색을 코드로 구현해 봅니다. 이분 검색은 정렬된 집합을 유지해야 하기 때문에 삽입과 삭제의 비용이 다소 높습니다. 하지만 검색은 매우 효율적입니다. 그래서 삽입/삭제가 빈번하지 않은 경우에 적절합니다.
14.7 내분 검색 : 내분 검색(Interpolation Search)은 이분 검색을 개선한 것으로 매우 비슷합니다. 다만 검색 구간을 나눌 때 중간을 택하는 것이 아니라, 데이터 집합의 범위와 키값의 비율로 계산하여 대상 데이터의 위치를 더 빨리 예측하는 알고리즘입니다. 내분 검색에 대해 알아봅니다.
14.8 검색 성능 분석 : 지금까지 배워 본 순차 검색, 이분 검색, 내분 검색에 대해 실제 데이터를 놓고 수행 속도를 알아봅니다. 검색, 삽입, 삭제에 대해 모두 평가를 합니다. 어떤 자료구조를 사용했느냐에 따라 성능이 확연히 구분됩니다.
14.9 기본 검색 - 결론 : 이번 장에서는 검색 문제의 정의와 기본적인 검색 알고리즘에 세가지에 대해 알아 보았습니다. 기본 검색 알고리즘은 구현이 간단하기 때문에 작은 데이터 집합에 대해서는 여전히 많이 쓰이고 있습니다.
관련글 |
- C++로 배우는 알고리즘
- 13장 : 기수 정렬 (Radix Sort)
- 15장 : 이진트리 검색 (Binary Tree Search)
댓글 없음:
댓글 쓰기