1. 레코드, 키의 정의 및 탐색 트리
① 탐색
- 기억 공간에 보관 중인 데이터 중에서 원하는 정보를 찾아내는 작업
- 순차 탐색, 이진 탐색 등이 있다.
- 적절한 자료구조와 알고리즘의 사용은 효율적인 데이터의 저장과 탐색에서 매우 중요함.
- 배열의 경우 데이터가 들어오는 순서대로 쌓아서 저장은 쉽지만, 검색이 번거로움.
② 레코드, 키, 탐색트리
- 레코드 : 개체에 대해 수집된 모든 정보를 포함하고 있는 저장 단위 (행 전체)
- 필드 : 레코드에서 각각의 정보를 나타내는 부분(열)
- 키 : 다른 레코드와 중복되지 않도록 각 레코드를 대표할 수 있는 필드(ex. 사원번)
키는 필드 하나로 구성할 수도 있고, 두 개 이상의 필드로 구성할 수 있음.
- 탐색 트리 : 각 노드 가 규칙에 맞도록 하나씩 키를 가지고 있는데 이를 통해서 해당 레코드가 저장된
위치를 알 수 있다.
★내부 탐색 트리 - 탐색 트리가 메인 메모리내에 존재
★부 탐색 트리 - 탐색 트리가 외부에 존재(보조기억자치),
메인메모리 내에서 키를 수용할 수 없을 정도로 클때
2. 순차탐색
① 순차탐색 - 선형탐색
- 원하는 데이터를 찾을 때까지 키를 하나씩 비교해가는 방법 (비효율적)
- 파일이 크면 탐색 시간 증가
② 자기구성 순차탐색 (순차탐색 개선)
- 자주 사용되는 항목을 앞쪽에 배치해서 효율 높이는 것
- 전진 이동법, 전위법, 빈도 계수
▶전진 이동법 - 어느 항목이 한 번 탐색되고 나면 그 항목을 데이터 집합의 가장 앞에 위치시키는 방
▶전위법 - 탐색 항목을 바로 이전 항목과 교환, 자주 사용될수록 점진적으로 앞쪽으로 옮겨
▶빈도 계수 - 탐색된 횟수를 별도의 공간에 저장해 두고 탐색된 횟수가 높은 순으로 데이터 집합 재구성
3. 이진 탐색
① 이진탐색
- 정렬된 데이터 집합을 이분화하면서 탐색하는 방법
- 찾고자 하는 키값을 파일의 중간 레코드 키값과 비교하며 검색
> 파일의 탐색시간을 1/2씩 줄여가며 검색하므로 효율적
'CS공부 > 학점은행_알고리즘' 카테고리의 다른 글
| 4-2 관계 (0) | 2023.07.12 |
|---|---|
| 4-2 이진 탐색 트리 (0) | 2023.07.12 |
| 3주 2차 특수한 정렬 알고리즘 (0) | 2023.07.05 |
| 3주 1차 효율적인 정렬 알고리즘 (0) | 2023.07.05 |
| 2주 2차 기본적인 정렬 알고리즘 (0) | 2023.06.28 |