탐색

목차

1.탐색
2.선형탐색
3.이분(이진)검색
4.블록탐색
5.보간탐색
6.이진트리탐색
7.해시탐색

---

1.탐색 (검색, Search)

1-1. 탐색의 개념

* 많은 양의 데이터에서 원하는 데이터를 찾는 작업을 의미한다
* 탐색에 이용되는 기억장치에 따라 내부탐색, 외부탐색으로 나눌수 있다
    - 내부 탐색: 주기억장치 탐색, 적은양의 데이터를 빠르게 탐색
    - 외부 탐색: 보조기억장치도 함께 탐색, 많은 양의 데이터를 느리게 탐색

1-2. 탐색의 종류

1. 선형 탐색: 검색 대상을 데이터를 처음부터 순차적으로 비교하여 검색하는것
2. 이분(이진)탐색: 검색 대상 데이터를 절반씩 나누어 가며 검색하는것
3. 보간 탐색: 찾을 값의 위치 값을 예상하여 검색하는 사전식 탐색
4. 블록 탐색: 대량의 데이터를 그룹별로 블록화하여 인덱싱을 통해 검색하는것
5. 이진트리탐색: 검색 대상 데이터를 이진트리로 변형한 뒤에 검색하는것
6. 해싱탐색: 해싱함수를 사용하여 데이터를 검색하는것

1-3. 복잡도

1. 공간 복잡도
    * 탐색 등을 진행하는 대상 알고리즘이 연산을 수행하며 사용되는 메모리 공간의 크기를 나타내는 단위
    * 일반적인 경우 공간 복잡도가 알고리즘의 품질에 영향을 미치는 비중은 시간 복잡도에 비해 현저히 낮은 수준이다.
    * 빅데이터 처리시엔 메모리 용량을 초과할수 있으므로 상황에 맞는 적절한 처리절차가 필요하다
2. 시간 복잡도
    * 탐색 등을 진행하는 대상 알고리즘으로 인해 연산이 수행되는 횟수를 나타내는 단위
    * 하드웨어 및 운영시스템의 환경에 따라 실행시간이 달라지므로, 연산의 횟수가 보다 정확한 기준이 될수 있다
    * 데이터에 따라 연산횟수 산출 결과가 다를 때는 최악의 경우를 기준으로 산출한다
3. 빅오 표기법
    * 대문자 'O'와 괄호를 사용하여 입력 자료당 소요되는 연산 횟수를 나타낸다
    * O(1): 입력 데이터 수와 관계없이 연산횟수가 고정되는 상수형태
        - 시간 복잡도 중 가장 빠른 연산을 진행
    * O(logn): 데이터 처리에 필요한 연산 횟수가 데이터 수에 따라 일정하게 증가하는 선형
        - 이분탐색, 이진트리탐색
    * O(n): 데이터 처리에 필요한 연산 횟수가 데이터 수에 따라 일정하게 증가하는 선형
        - 수열계산, 순차탐색
    * O(nlogn): 데이터 처리에 필요한 연산 횟수가 특정요인에 의해 늘어나는 폭이 점점 커지는 선형 로그 형태
        - 퀵정렬, 힙정렬, 병합정렬
    * O(n²): 데이터 처리에 필요한 연산 횟수가 입력 데이터 수의 제곱만큼 필요한 형태
        - 선택정렬, 버블정렬
    * O(2ᴺ): 데이터 처리에 필요한 연산 횟수가 입력 데이터 수의 지수승만큼 필요한 형태
    * O(n!): 데이터 처리에 필요한 연산 횟수가 입력 데이터 수의 누승만큼 필요한 형태
        - 시간 복잡도중 가장 느린 연산을 진행

---

2.선형탐색 (Linear Search)

2-1. 선형 탐색의 개념

* 검색 대상을 데이터를 처음부터 순차적으로 비교하여 검색하는것
* 데이터가 정렬되어 있지 않거나 데이터의 수를 알지 못해도 사용가능 하다
* 데이터 수가 적어 다른 복잡한 탐색 알고리즘을 사용함으로써 얻는 이득이 크지 않을때 사용할수 있다
* 시간 복잡도는 O(n)

2-2. 선형 탐색의 평균 비교 횟수

* n 개의 데이터를 가진 자료구조의 평균 비교 횟수 = (n+1)/2

---

3.이분(이진)검색 (Binary Search)

3-1. 이분 탐색의 개념

* 검색 대상 데이터를 절반씩 나누어 가며 검색하는것
* 절반으로 나눠야 하기 때문에 데이터의 수를 파악하고 있어야 한다
* 시간 복잡도는 O(logn) 이다

---

4.블록 탐색 (Block Search)

4-1. 블록 탐색의 개념

* 대량의 데이터를 그룹별로 블록화하여 인덱싱을 통해 검색하는것
* 블록의 내부 요소들은 다음 블록의 가장 작은 값보다 작아야 한다
* 블록의 내부 요소중 가장 큰값을 이용하여 인덱스를 생성한다
* 블록 내부 요소들은 정렬하지 않으므로 순차탐색을 이용한다

4-2. 가장 이상적인 블록의 개수

* n개의 데이터를 가진 자료구조의 이상적인 블록의 개수 = √n

---

5.보간 탐색 (Block Search)

5-1. 보간 탐색의 개념

* 찾을 값의 위치값을 예상하여 검색하는 사전식 탐색이다
* 찾고자하는 자료가 일정한 규칙을 가지며 나열되어 있을때 활용
* 보간 탐색 공식을 적용하기 위해서는 전체 데이터의 수를 알고 있어야 한다
* 순차 탐색으로 진행하지만 블록 탐색보다 속도가 빠른 편이다
* 시간복잡도는 O(log(logn))

5-2. 보간 탐색 공식

* ((찾을값 - 최소값)/ (최대값 - 최소값)) * 데이터 개수
    - 연산의 결과가 실수인 경우 소수점 버림
    - 해당 위치에 값이 없을 경우, 탐색 범위를 확장

---

6.이진 트리 탐색 (Block Search)

6-1. 이진 트리 탐색의 개념

* 검색 대상 데이터를 이진 트리로 변형한 뒤에 검색하는것
* 첫 데이터를 근노드로 지정하여, 이후 데이터들을 좌우로 연결한다
* 근노드 및 부모 노드와 비교하여 작은값은 왼쪽, 큰 값은 오른쪽에 연결
* 시간 복잡도는 O(logn)

---

7.해시 탐색 (Block Search)

7-1. 해시 탐색의 개념

* 해싱 함수를 사용하여 데이터를 검색하는것
* 기존의 탐색법들과는 달리 데이터의 내용과 인덱스를 미리 연결하여 짧은 시간에 탐색이 가능하다
* 적절한 해싱 함수를 이용하여 데이터의 저장위치를 결정한다
* 결정된 저장 위치가 중복(충돌)될 때는 그에 따른 조치가 필요하다
* 시간 복잡도는 O(1) 

7-2. 해시 함수의 종류

* 제산법(Division)
    - 키(key)를 특정 값으로 나눈 나머지 값으로 저장할 위치를 결정하는 방법
* 폴딩법(Folding)
    - 키를 여러 부분으로 나누어 부분별 숫자의 합연산이나 XOR연산의 결과로 위치를 결정하는 방법
* 제곱법(Square)
    - 키를 제곱한 결과의 일부분으로 위치를 결정하는 방법
* 숫자 분석법(Digit Analysis)
    - 키의 숫자 분포를 파악하여 분포가 고른 부분을 이용하여 위치를 결정하는 방법
* 기수 변환법(Radix Conversion)
    - 키의 값을 다른 진법으로 변환하여 얻은 결과값으로 위치를 결정하는 방법
* 의사 무작위법(Pseudo Random)
    - 난수를 이용하여 위치를 결정하는 방법 

7-3. 해시 탐색에서의 용어들

1. 해시 테이블(Hash table): 해싱 함수를 통해 구해진 위치에 각 데이터를 저장한 테이블
2. 슬롯(Slot): 하나의 데이터를 저장하는 공간
3. 버킷(Bucket): 여럿의 슬롯이 모인 공간
4. 동의어(Synonym): 같은 버킷에 저장된 서로 다른 값들을 의미
5. 충돌(Collision): 서로 다른 데이터가 같은 키를 가지는 현상
6. 오버플로우(Overflow): 한 버킷 내에 더 이상의 데이터를 저장할 슬롯이 없는 상태에서 추가 데이터를 저장하는 경우 발생하는 오류상태

7-4. 해싱함수의 조건

* 충돌을 최소화할 수 있어야 한다
* 계산이 너무 복잡하지 않고 빠르게 처리될수 있어야 한다

참고자료 : 이기적 환상콤비 정보처리기사