순차 탐색
순서대로 무식하게 찾는 방식입니다. 단순합니다.
조금 더 효율적인 방식을 위해 자기 구성 순차탐색이라는 방식이 존재합니다.
자기 구성 순차 탐색
자기 구성법은 자주 사용되는 항목을 데이터 집합의 앞쪽에 배치함으로써 순차 탐색의 검색 효율을 끌어올리는 방법입니다.
아래 세가지 방식으로 구분됩니다.
- 전진 이동법(Move To Front)
- 전위법(Transpose)
- 빈도 계수법(Frequency Count)
전진 이동법
전진 이동법은 어느 항목이 한번 탐색되고 나면, 그 항목을 데이터 집합의 가장 앞 (링크드 리스트에서는 헤드)에 위치시키는 방법입니다. 이렇게 할 경우 한번 찾은 항목을 연이어 또 찾을 때 단번에 탐색을 완료 할 수 있습니다. MS 워드의 '최근 문서' 기능과 같은 원리로 동작 한다고 생각하면 이해하기 쉽습니다.
전위법
탐색된 항목을 바로 이전 항목과 교환한다는 것 말고는 기본적으로 전진 이동법과 같은 전략을 취하는 알고리즘 입니다.
전진 이동법은 무조건 앞으로 옮기나 전위법은 '자주' 탐색된 항목을 앞으로 옮기기 때문에 많은 선택을 받는 데이터를 빠르게 확인 할 수 있는 꽤 민주적인 알고리즘 입니다.
계수법
계수법은 데이터 집합 내의 각 요소들이 탐색된 횟수를 별도의 공간에 저장 해 두고 탐색된 횟수가 높은 순으로 데이터 집합을 재구성하는 전략의 알고리즘 입니다.
대신 계수결과를 저장하는 별도의 공간이 필요하며 데이터 집합을 재배치 하는 등 비용이 더 많이 소요되기는 합니다.
이진탐색
이진 탐색은 정렬된 데이터 집합에서 사용할 수 있는 '고속' 탐색 알고리즘입니다. 이 알고리즘의 핵심이 탐색범위를 1/2씩 줄여나가는 방식에 있기 때문에 붙여진 것입니다.
1. 데이터 집합의 중앙에 있는 요소를 고릅니다.
2. 중앙 요소의 값과 찾고자 하는 목표 값을 비교합니다.
3. 목표 값이 중앙 요소의 값보다 작다면 중앙을 기준으로 데이터 집합의 왼편에 대해 새로 검색을 수행하고 크다면 오른편에 대해 이진 탐색을 새로이 수행합니다.
4. 찾고자 하는 값을 찾을 때 까지 1~3 과정을 반복합니다.