검색(Search, 탐색)
01. 검색의 종류
1) 검색
1. 검색의 개념
- 대량의 자료 중에서 원하는 자료를 찾는 작업
- 검색은 검색에 이용하는 기억 장치에 따라 내부 검색과 외부 검색으로 나눌 수 있음
- 외부 검색은 검색할 자료들이 많을 때 사용하는 방법으로 보조 기억 장치에 대량의 자료를 보관하고, 부분적으로 주기억 장치에 적재하여 검색하는 방법
| 비교 내용 |
내부 검색 |
외부 검색 |
| 검색 위치 |
주기억 장치 |
주기억 장치, 보조 기억 장치 |
| 자료 크기 |
검색 대상의 자료가 적을 때 |
검색 대상의 자료가 많을 때 |
| 검색 시간 |
빠름 |
느림 |
2. 검색의 종류
| 검색 종류 |
설명 |
| 선형 검색 |
처음부터 차례로 검색하는 방법 |
| 제어 검색 |
이분 검색, 보간 검색 등이 있음 |
| 블록 검색 |
검색 대상의 자료를 그룹별로 블록화시킴 |
| 이진 트리 검색 |
이진 트리 구조를 이용하여 검색 |
| 해싱 검색 |
검색 대상의 자료를 키 변환 작업을 통해 검색 |
2) 시간 복잡도
1. 시간 복잡도
- 특정 알고리즘의 실행 시간은 하드웨어, 운영체제 등의 실행 환경에 따라 달라짐
- 실행 시간을 측정하는 대신 알고리즘의 연산 횟수(비교 횟수, 자료의 바꿈 횟수)를 세어서 판단
- 검색이나 정렬 알고리즘을 이루고 있는 연산들이 몇 번 수행되는지 숫자로 표시하여 효율적인 알고리즘을 선택하기 위해 사용
- 정확한 의미로 복잡한 연산 횟수를 계산하기 위해서 정확하지는 않지만 연산 횟수를 대략 확인한다는 것
2. 시간 복잡도의 종류
- O(n)은 수학의 함수 f(x)와 같은 의미로 시간 복잡도 함수를 표시
- 일반적인 알고리즘에서 시간 복잡도는 O(log2n)이 가장 빠르고 O(n!)이 가장 느림
- 입력 자료의 개수가 무한히 크다고 가정하는 경우, 시간 복잡도를 비교해 보면 O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) 으로 O(log2n)은 다른 알고리즘에 비해 효율성이 좋다고 할 수 있음
- 속도 빠르기는 아래와 같으며, 아래로 진행할수록 느려짐
- O(1)
- 알고리즘 수행시간이 입력 데이터 수와 관계없이 일정함
- NULL인지 검사하는 알고리즘에 해당
- O(log2n)
- 로그형으로 이분 검색, 이진 트리 검색에 해당
- O(n)
- 선형으로 n만큼 시간이 소모됨
- 수열이나 선행(순차)검색에 해당
- O(nlog2n)
- 로그 선형으로 퀵 정렬, 힙 정렬, 합병 정렬 시 비교 횟수에 해당
- O(n2)
- 2차형으로 선택 정렬, 버블 정렬 시 자료 비교 횟수에 해당
- O(n3)
- O(nk)
- O(2n)
- O(n!)
3. 입력 자료 수에 따른 시간 복잡도
- 입력 자료 수 = n
- 입력 자료가 32개이면, 선형 검색의 시간 복잡도는 O(n) = O(32)이므로 32번 비교하는 것
- 이분 검색 알고리즘에서 입력 자료가 128개이면, O(log2n) = O(log2128) = O(log227) = O(7)이므로 7번 정도를 비교하게 된다는 의미
| 구분 |
1 |
2 |
4 |
8 |
16 |
32 |
| O(1) |
1 |
1 |
1 |
1 |
1 |
1 |
| O(log2n) |
0 |
1 |
2 |
3 |
4 |
5 |
| O(n) |
1 |
2 |
4 |
8 |
16 |
32 |
| O(nlog2n) |
0 |
2 |
8 |
24 |
64 |
160 |
| O(n2) |
1 |
4 |
16 |
64 |
256 |
1024 |
| O(n3) |
1 |
8 |
64 |
512 |
4096 |
32768 |
| O(2n) |
2 |
4 |
16 |
256 |
65536 |
4 x 1010 |
| O(n!) |
1 |
2 |
24 |
40326 |
2 x 1013 |
2 x 1037 |
02. 선형 검색(Linear Search)
1) 선형 검색
- 검색 대상의 자료를 처음부터 하나씩 비교하여 검색
- 검색 대상 자료가 순서적으로 정렬되어 있지 않아도 검색 가능
- 검색 대상 자료들의 수를 알지 못할 때 사용
- 단순하고 검색 속도가 느림으로 자료가 적을 때 유리함
- 검색 대상의 전체 자료 수가 n개 있을 때 최악의 경우 n번을 검색할 수도 있음
- 시간 복잡도는 O(n)
2) 자료가 n개 있을 때 평균 비교 횟수
평균 비교 횟수 = (n + 1) / 2
03. 이분(이진) 검색(Binary Search)
1) 이분 검색
- 검색 대상의 전체 자료를 이등분하면서 검색하는 방법
- 이분 검색을 하려면 검색 대상의 전체 자료의 수를 알고 있어야 함
- 이분 검색을 하려면 검색 대상의 자료들이 정렬되어 있어야 함
2) 이분 검색 알고리즘
- 자료의 수가 15개이며, 오름차순으로 정렬되어 있는 경우
- 이분 검색은 범위를 절반씩 축소시켜 나가면서 자료를 찾는 방법으로 46을 찾기 위해서는 다음과 같은 순서로 검색을 진행
- 이분 검색의 시간 복잡도는 O(log2n)으로 O(log215) = O(3.906..)이므로 대략 3번에서 4번 만에 찾음
| 1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
| 14 |
15 |
27 |
39 |
46 |
47 |
57 |
61 |
65 |
70 |
77 |
79 |
87 |
91 |
99 |
- 전체 범위를 지정하기 위해 low = 1, high = 15로 설정하고 가운데 있는 위치의 값과 비교
- 첫 번째 (low + high) / 2 = 8이므로 8번째에 있는 61과 찾고자 하는 값 46을 최초로 비교하여 찾고자 하는 자료가 작으므로 high 값을 현재 비교한 위치인 8보다 하나 작은 값으로 변환
- 범위가 1번째부터 7번째 사이로 좁혀졌으므로 low = 1, high = 7로 설정하고 가운데 위치의 값과 비교
- 두 번째 (low + high) / 2 = 4이므로 4번째 있는 값 39와 찾고자 하는 값 46을 비교하여 찾고자 하는 자료가 크므로 low 값을 현재 비교한 위치인 4보다 하나 큰 값으로 변환
- 범위가 5번째부터 7번째 사이로 좁혀졌으므로 low = 5, high = 7로 설정하고 가운데 위치의 값과 비교
- 세 번째 (low + high) / 2 = 6이므로 6번째 있는 값 47과 찾고자 하는 값 46을 비교하여 찾고자 하는 자료가 작으므로 high 값을 현재 비교한 위치인 6보다 하나 작은 값으로 변환
- 범위가 5번째부터 5번째 사이로 좁혀졌으므로 low = 5, high = 5로 설정하고 가운데 위치의 값과 비교
- 네 번째 (low + high) / 2 = 5이므로 5번째 있는 값 46과 찾고자 하는 값 46을 비교하여 원하는 값을 찾음
04. 보간 검색(Interpolation Search)
1) 보간 검색
- 찾고자 하는 자료가 있음 직한 부분을 검색하는 방법
- 찾고자 하는 자료의 위치 값을 계산해야 함
- 사전식 검색이라고도 함
- 사전이나 전화번호부를 탐색하는 방법과 같이 탐색키가 존재할 위치를 예측하여 탐색하는 방법
- 찾고자 하는 자료가 일정한 규칙을 갖고 있을 때 유리한 방법
- 보간 검색을 하려면 검색 대상의 전체 자료의 수를 알고 있어야 함
- 보간 검색을 하려면 검색 대상의 자료들은 정렬되어 있어야 함
- 순차 검색을 이용
- 블록 검색보다 빠른 검색 방법
2) 보간 검색 공식과 알고리즘
- 자료의 수가 15개이며, 오름차순으로 정렬되어 있는 경우
- 자료의 특성에 따라 여러 가지가 존재하지만 주로 사용하는 보간 공식은 다음과 같음
(검색할 자료 - 검색 자료의 최솟값) / (검색 자료의 최댓값 - 검색 자료의 최솟값) x 검색 자료의 수
| 1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
| 14 |
15 |
27 |
39 |
46 |
47 |
57 |
61 |
65 |
70 |
77 |
79 |
87 |
91 |
99 |
- 검색할 자료가 46, 검색 자료의 최솟값 14, 검색 자료의 최댓값 99, 전체 자료 수 15개이므로 공식에 대입
- (46 - 14) / (99 - 14) x 15 = 5.647...
- 소수점 이하를 버리면 5이므로 5번째 위치가 46임을 알 수 있음
- 만약 첫 번째로 찾지 못할 경우에는 앞과 뒤로 임의의 수만큼 확장해서 순차적으로 검색
05. 블록 검색(Block Search)
1) 블록 검색
- 찾고자 하는 대량의 자료들을 그룹별로 블록화하고, 블록들을 인덱스로 만들어 검색하는 방법
- 블록끼리는 정렬이 되어 있어야 하지만 블록 내부는 정렬되어 있지 않아도 됨
- 순차 검색을 이용
2) 가장 이상적인 블록의 개수
가장 이상적인 블록의 개수 = √n
- 검색 대상의 자료 수가 16개이면 √n = √16 = 4개가 됨
- 검색 대상의 자료 수가 12개이면 √n = √12 = 2√3 이므로 2 x 1.732.. = 3.464... ≒ 3이 됨
- 자료의 개수는 정수개이므로 블록의 개수도 항상 정수개가 되어야 함
3) 블록 검색 알고리즘
- 검색 대상의 자료 수가 12개인 경우
- √n = √12 = 2√3 = 3.46...이 되며 소수점 이하를 버리면 3이 되므로 블록의 개수는 3일 때 가장 이상적
| 1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
| 4 |
9 |
2 |
7 |
18 |
16 |
13 |
15 |
23 |
28 |
22 |
21 |
- 12개의 검색 대상 자료를 3개로 블록화하면 다음과 같음
- 블록 내부는 정렬되어 있지 않아도 되지만 블록끼리는 정렬되어 있어야 함
- 3개의 블록에서 가장 큰 값을 다음과 같이 인덱스로 만듦
- 1블록에서 가장 큰 값은 9, 2블록에서 가장 큰 값은 18, 3블록에서 가장 큰 값은 28
- 찾고자 하는 자료가 13이라고 한다면 13은 인덱스의 9보다 크고 18보다 작으므로 인덱스 18에 해당하며, 이는 찾고자 하는 자료가 2번째 블록에 존재한다는 것을 의미
- 마지막으로 2번째 블록에서 첫 번째부터 순차적으로 검색하면서 2번재 블록에 3번째의 13을 찾게 됨
