[117] 알고리즘 07차시 순차 탐색과 이진 탐색

1. 레코드, 키의 정의 및 탐색 트리

가. 탐색(검색)

컴퓨터에서 자료를 찾는 방법

기억 공간에 보관 중인 데이터 중에서 원하는 정보를 찾아내는 작업

컴퓨터 안에는 엄청나게 많은 자료들이 있는데 컴퓨터는 자료를 빨리 찾을 수 있도록 일정한 논리 순서에 맞추어 작업을 하는데 이때 필요한 논리 순서가 탐색 알고리즘임.

책에서 어떤 내용을 찾기 위해 페이지를 마구 뒤져야 하지만 색인(ndex)이 있으면 편리하게 책의 해당 페이지를 찾을 수 있음.

엄청난 양의 웹 문서들을 빠른 시간에 검색해주는 구글과 같은 검색 엔진이 대표적인 탐색의 응용 예

탐색의 종류로는 순차 탐색, 이진 탐색 등이 있음.

적절한 자료구조와 알고리즘의 사용은 효율적인 데이터의 저장과 탐색에서 매우 중요함.

데이터의 저장과 검색은 자료구조와 알고리즘에서 매우 중요

데이터를 저장하는 효율적 자료구조가 개발되기 전에는 데이터가 들어오는 대로 쌓는 방법 밖에 없었음.

배열에 데이터가 들어오는 순서대로 쌓는 것은 데이터를 저장하기는 쉽지만 검색은 번거로움.

이진 탐색 트리와 해시 테이블은 자료를 찾는 색인 역할을 하는 자료구조

나. 레코드, 키, 탐색트리

1) 레코드(Record)

개체에 대해 수집된 모든 정보를 포함하고 있는 저장 단위

예) 사람의 레코드라면 주민번호, 이름, 집주소, 연락처, 최종 학력, 이메일 등의 정보 포함

2) 필드(Field)

레코드에서 각각의 정보를 나타내는 부분

예) 사람의 레코드에서 각각의 정보를 나타내는 부분

3) 탐색 키(Search key) 또는 키(Key)

다른 레코드와 중복되지 않도록 각 레코드를 대표할 수 있는 필드

예) 사람 레코드의 경우 주민번호만 있으면 다른 사람 레코드와 구분될 수 있으며 해당 레코드를 대표할 수 있으므로 주민번호가 탐색 키가될 수 있음.

키는 필드 하나로 구성할 수도 있고, 두 개 이상의 필드로 구성할 수도 있음.

예) 이름과 연락처를 사용하면 두 개의 필드로 구성된 키가 될 수 있음.

4) 탐색 트리(Search Tree)

각 노드가 규칙에 맞도록 하나 씩의 키를 갖고 있음.

이를 통해 해당 레코드가 저장된 위치를 알 수 있음.

저장되는 장소에 따라 내부 탐색 트리와 외부 탐색 트리로 나뉨.

레코드, 키의 정의 및 탐색 트리

내부 탐색 트리

탐색 트리가 메인 메모리 내에 존재

메인 메모리에서 모든 키를 수용할 수 있으면 탐색 트리 전체를 메인 메모리로 한번만 탑재한 후 내부 탐색 트리로 사용할 수 있음.

외부 탐색 트리

탐색 트리가 외부(주로 디스크)에 존재

메인 메모리에서 모든 키를 수용할 수 없을 정도로 크면 디스크 공간에 저장된 상태로 탐색해야 함.

2. 순차 탐색

가.  순차 탐색(Sequential Search)

이해하기 쉽고 간단한 탐색 알고리즘

선형 탐색(Linear Search)이라고도 함

순서화되어 있지 않은 경우 사용하며 첫 번째 데이터부터 차례로 비교하여 탐색하는 방식

원하는 데이터를 찾을 때까지 키를 하나씩 비교해가는 방식

데이터가 정렬되어 있을 때도 하나씩 비교하면서 원하는 값을 찾기 때문에 비효율적

파일이 크면 탐색 시간 증가

예) 무작위로 모여진 명함 중에서 원하는 사람의 명함을 찾는 경우

시간 복잡도: O(n)

https://ko.wikipedia.org/wiki/순차_검색_알고리즘

순차 검색 알고리즘 - 위키백과, 우리 모두의 백과사전

나. 순차 탐색 방법

각 데이터를 순차적으로 순회하며 원하는 데이터를 찾으면 출력 후 탐색 종료

마지막 데이터까지 탐색 후 원하는 데이터를 찾지 못하면 탐색 실패로 종료

다. 자기 구성 순차 탐색(Self-Organizing sequential search)

자주 사용되는 항목을 데이터 집합의 앞쪽에 배치함으로써 순차 탐색의 검색 효율을 끌어올리는 방법

1) 전진 이동법(Move To Front)

어느 항목이 탐색되면 그 항목을 데이터 집합의 가장 앞에 위치시키는 방법

2) 전위법(Transpose)

어느 항목이 탐색되면 그 항목을 바로 앞 항목과 교환하는 방법

전진 이동법과는 달리 자주 사용되면 점진적으로 앞쪽으로 이동시킴.

3) 빈도 계수법(Frequency Count)

데이터 집합내의 각 요소들이 탐색된 횟수를 별도의 공간에 저장해 두고 탐색된 횟수가 높은 순으로 데이터 집합을 재구성

계수 결과를 저장하는 별도의 공간을 유지해야 하고 계수 결과에 따라 데이터 집합을 재배치해야 함.

3. 이진 탐색

가. 이진 탐색(Binary Search)

정렬된 데이터 집합을 이분화하면서 탐색하는 방법

정렬되어 있는 전체 파일을 두 개의 서브파일로 분리해가면서 키 값을 검색

예) 가나다순으로 정렬되어 있는 전화번호부에서 임의의 사람에 대한 전화번호를 찾는 경우

순차 탐색은 데이터가 정렬되어 있을 때도 데이터를 하나씩 비교하면서 원하는 값을 찾기 때문에 비효율적

찾고자 하는 키값을 파일의 중간 레코드 키값과 비교하면서 검색

시작과 끝의 인덱스를 설정하고 그 중간값을 구한 후 키와 중간값을 계속 비교하면서 검색

파일의 탐색 시간을 1/2씩 줄여가면서 탐색하므로 효율적

레코드의 수가 많을수록 효과적

시간 복잡도: O(logn)

정렬된 데이터 집합에서 사용할 수 있는 '고속' 탐색 알고리즘

https://ko.wikipedia.org/wiki/이진_검색_알고리즘

이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전

나. 이진 탐색의 작동 예

정렬된 데이터 집합에서 특정 수를 찾는 경우, 처음에는 전체의 중간값을 비교함.

중간값이 원하는 수보다 클 경우 왼쪽에서, 작을 경우 오른쪽에서 위 과정을 반복함.