13.1 탐색이란?
● 탐색: 탐색키와 데이터로 이루어진 여러 개의 항목 중에서 원하는 탐색키를 가지고 있는 항목을 찾는 것
- 탐색을 위해 사용되는 자료구조: 배열, 연결 리스트, 트리, 그래프 등
- 탐색 성능 향상을 위해 이진 탐색 트리와 같은 보다 진보된 방법으로 자료를 저장 및 탐색
항목: 탐색의 단위 (ex. 숫자, 구조체 ..)
탐색키: 항목과 항목을 구별시켜 주는 키
13.2 정렬되지 않은 배열에서의 탐색
● 순차 탐색(sequential search): 하아목의 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법
- 탐색 방법 중 가장 간단하고 직접적임
- 탐색의 범위는 low에서 high까지 함수의 매개변수로 주어짐
- 탐색에 성공하면 그 항목이 발견된 위치의 인덱스를 반환하고 실패하면 -1을 반환
int seq_search(int key, int low, int high){
int i;
for(i=low;i<=high;i++){
if(list[i]==key){
return i;
}
}
return -1;
}
● 개선된 순차 탐색
기존 코드 i <=high에서 리스트의 끝을 테스트하는 비교 연산을 줄이기 위해
리스트의 끝에 찾고자 하는 키 값을 저장하고 반복문의 탈출 조건을 키 값을 찾을 때까지로 설정
int seq_search2(int key, int low, int high){
int i;
list[high+1] = key;
for(i=low;list[i] != key;i++);
if(i ==(high+1)) return -1;
else return i;
}for문을 list[i]!=key 일 때까지만 돌리고 일치하면 반복문을 탈출하여 그때의 i를 return 해주면
i가 매번 리스트의 끝에 도달하였는 지를 비교하지 않아도 된다.
● 순차 탐색의 시간 복잡도
- 탐색 성공 시: 리스트에 있는 키의 위치에 따라 비교 횟수 결정.
(1+2+3+...+n) / n = (n+1)/2
- 탐색 실패 시: n번
∴ O(n)
13.3 정렬된 배열에서의 탐색
배열의 항목이 많은 경우 순차 탐색보다 배열을 정렬한 후 효율적인 탐색 알고리즘을 채택하는 것이 효율적
● 정렬된 배열에서의 이진 탐색
이진탐색: 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어
탐색의 범위를 반으로 줄이며 탐색하는 것
- 배열이 반드시 정렬되어 있어야 함
- 데이터의 삽입이나 삭제 빈번할 때보다 주로 고정된 데이터에 대한 탐색에 적합
● 이진 탐색 구현(순환 호출 버전)
- 탐색할 범위는 매개변수로 받은 low에서 high까지이다.
- 시작은 low=0, high = n-1이다.
- 순환 호출을 끝내기 위해서는 더 이상 탐색할 항목이 없을 때, 즉 탐색 범위가 1보다 작을 때 -1을 반환하여 끝낸다.
int binary_search(int key, int low, int high){
int middle;
if(low<high){
middle = (low+high) /2;
if(key == list[middle]){
return middle;
}
else if(key <list[middle]){
return binary_search(key, low, middle-1);
}
else{
return binary_search(key,middle+1,high);
}
}
return -1;
}
● 이진 탐색 구현(반복적인 버전)
- 효율성 측면에서 순환호출 버전보다 우수하다.
int binary_search_itr(int key, int low, int high){
int middle;
while(low<high){
middle = (low+high)/2;
if(key == list[middle]){
return middle;
}
else if(key<list[middle]){
high = middle -1;
}
else{
low = middle +1;
}
}
return -1;
}
● 이진 탐색의 시간복잡도
- 이진 탐색은 탐색을 반복할 때마다 탐색 범위를 반으로 줄인다.
- 탐색 범위가 더 이상 줄일 수 없는 1이 될 때의 탐색 횟수를 k라 하면 탐색 범위는
횟수=0 일 때 n, 횟수=1 일 때 n/2, ... 횟수=k 일 때 n/2^k 이며
n/2^k =1 이므로 k = log2n 이다.
∴ O(log2n)
● 정렬된 배열에서의 색인 순차 탐색
색인 순차 탐색(indexed sequential search): 인덱스라 불리는 테이블을 사용하여 탐색의 효율을 높이는 방법
인덱스 테이블: 주 자료 리스트에서 일정 간격으로 발췌한 테이블
인덱스 테이블의 항목 수 = m, 주 자료 리스트의 데이터 수 = n 이면
각 인덱스 항목은 주 자료 리스트의 각 n/m번째 데이터를 가지고 있다.
- 인덱스 테이블에서 index[i] < key < index[i+1]을 만족하는 항목을 찾는 알고리즘
- 위 조건을 만족하는 항목으로부터 주 자료 리스트에서 순차 탐색 수행
typedef struct{
int key;
int index;
}itable;
itable index_list[INDEX_SIZE];위와 같은 구조체를 통해 인덱스 테이블을 구현하며, 탐색이 성공하면 해당 키의 인덱스를 반환한다.
int index_search(int key,int n){
int i,low,high;
if(key<list[0] || key>list[n-1]) return -1;
for(i=0; i<INDEX_SIZE; i++){
if(index_list[i].key <=key && index_list[i].key>key) break;
}
if(i == INDEX_SIZE){
low = index_list[i-1].index;
high = n;
}
else{
low = index_list[i].index;
high = index_list[i+1].index;
}
return seq_search(key,low,high);
}
● 색인 순차 탐색 알고리즘의 성능
인덱스 테이블의 크기 감소 = 주 자료 리스트에서의 탐색 시간 증가
인덱스 테이블의 크기 증가 = 인덱스 테이블의 탐색 시간 증가
인덱스 테이블의 크기 m, 주자료 리스트의 크기 n
∴ O(m+n/m)
1차 인덱스 테이블의 크기가 너무 커지게 되면 2차 인덱스 테이블을 두어서
2차 인덱스 테이블이 1차 인덱스 테이블의 인덱스를 가리키도록 한다.
● 보간 탐색
보간 탐색: 탐색키가 존재할 위치를 예측하여 탐색하는 방법
위의 그림을 보고 비례식을 세워보면
(list[high] - list[low]) : (key - list[low]) = (high - low) : (탐색 위치 - low)
탐색 위치 = (key -list[low]) / (list[high] - list[low]) * (high - low) + low
- 값은 일반적으로 실수이며 소수점 이하를 버려서 탐색 위치를 채택
- 탐색 위치의 리스트 값보다 키 값이 클 경우 (탐색 위치 + 1)의 리스트 값을,
탐색 위치의 리스트 값보다 키 값이 작을 경우 (탐색위치 - 1)의 리스트 값을 key값과 비교
- 위의 각각 케이스에서 비교했을 때 탐색에 성공하면 해당위치를, 탐색 실패하면 -1을 반환
int interpol_search(int key, int n){
int low, high, j;
low = 0;
high = n-1;
while((list[high]>key)&&(key>list[low])){
j = (float)(key-list[low])/(list[high]-list[low])*(high-low) + low;
if(key > list[j]) low = j+1;
else if( key< list[j]) low =j -1;
else low = j;
}
if(list[low] ==key) return low;
else return -1;
}
♠ 508p Quiz
01
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 1 | 2 | 3 | 5 | 6 | 8 | 9 | 10 | 4 |
| 1 | 2 | 3 | 5 | 6 | 8 | 9 | 10 | 4 |
| 1 | 2 | 3 | 5 | 6 | 8 | 9 | 10 | 4 |
| 1 | 2 | 3 | 5 | 6 | 8 | 9 | 10 | 4 |
| 1 | 2 | 3 | 5 | 6 | 8 | 9 | 10 | 4 |
| 1 | 2 | 3 | 5 | 6 | 8 | 9 | 10 | 4 |
| 1 | 2 | 3 | 5 | 6 | 8 | 9 | 10 | 4 |
| 1 | 2 | 3 | 5 | 6 | 8 | 9 | 10 | 4 |
| 1 | 2 | 3 | 5 | 6 | 8 | 9 | 10 | 4 |
9번
02
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 2 | 3 | 4 | 6 | 7 | 8 | 9 |
| 1 | 2 | 3 | 4 | 6 | 7 | 8 | 9 |
| 1 | 2 | 3 | 4 | 6 | 7 | 8 | 9 |
3번
03
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 2 | 4 | 5 | 7 | 8 | 9 | 10 |
| 1 | 2 | 4 | 5 | 7 | 8 | 9 | 10 |
2
'CS > Data Structure' 카테고리의 다른 글
| [C언어로 쉽게 풀어쓴 자료구조] 연습문제 13강 (0) | 2024.01.20 |
|---|---|
| [C언어로 쉽게 풀어쓴 자료구조] Chapter13. 탐색 (2) (2) | 2024.01.13 |
| [C언어로 쉽게 풀어쓴 자료구조] 연습문제 12강 (1) | 2024.01.07 |
| [C언어로 쉽게 풀어쓴 자료구조] Chapter12. 정렬 (2) (0) | 2024.01.04 |
| [C언어로 쉽게 풀어쓴 자료구조] Chapter12. 정렬 (1) (1) | 2023.12.19 |
13.1 탐색이란?
● 탐색: 탐색키와 데이터로 이루어진 여러 개의 항목 중에서 원하는 탐색키를 가지고 있는 항목을 찾는 것
- 탐색을 위해 사용되는 자료구조: 배열, 연결 리스트, 트리, 그래프 등
- 탐색 성능 향상을 위해 이진 탐색 트리와 같은 보다 진보된 방법으로 자료를 저장 및 탐색
항목: 탐색의 단위 (ex. 숫자, 구조체 ..)
탐색키: 항목과 항목을 구별시켜 주는 키
13.2 정렬되지 않은 배열에서의 탐색
● 순차 탐색(sequential search): 하아목의 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법
- 탐색 방법 중 가장 간단하고 직접적임
- 탐색의 범위는 low에서 high까지 함수의 매개변수로 주어짐
- 탐색에 성공하면 그 항목이 발견된 위치의 인덱스를 반환하고 실패하면 -1을 반환
int seq_search(int key, int low, int high){
int i;
for(i=low;i<=high;i++){
if(list[i]==key){
return i;
}
}
return -1;
}
● 개선된 순차 탐색
기존 코드 i <=high에서 리스트의 끝을 테스트하는 비교 연산을 줄이기 위해
리스트의 끝에 찾고자 하는 키 값을 저장하고 반복문의 탈출 조건을 키 값을 찾을 때까지로 설정
int seq_search2(int key, int low, int high){
int i;
list[high+1] = key;
for(i=low;list[i] != key;i++);
if(i ==(high+1)) return -1;
else return i;
}for문을 list[i]!=key 일 때까지만 돌리고 일치하면 반복문을 탈출하여 그때의 i를 return 해주면
i가 매번 리스트의 끝에 도달하였는 지를 비교하지 않아도 된다.
● 순차 탐색의 시간 복잡도
- 탐색 성공 시: 리스트에 있는 키의 위치에 따라 비교 횟수 결정.
(1+2+3+...+n) / n = (n+1)/2
- 탐색 실패 시: n번
∴ O(n)
13.3 정렬된 배열에서의 탐색
배열의 항목이 많은 경우 순차 탐색보다 배열을 정렬한 후 효율적인 탐색 알고리즘을 채택하는 것이 효율적
● 정렬된 배열에서의 이진 탐색
이진탐색: 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어
탐색의 범위를 반으로 줄이며 탐색하는 것
- 배열이 반드시 정렬되어 있어야 함
- 데이터의 삽입이나 삭제 빈번할 때보다 주로 고정된 데이터에 대한 탐색에 적합
● 이진 탐색 구현(순환 호출 버전)
- 탐색할 범위는 매개변수로 받은 low에서 high까지이다.
- 시작은 low=0, high = n-1이다.
- 순환 호출을 끝내기 위해서는 더 이상 탐색할 항목이 없을 때, 즉 탐색 범위가 1보다 작을 때 -1을 반환하여 끝낸다.
int binary_search(int key, int low, int high){
int middle;
if(low<high){
middle = (low+high) /2;
if(key == list[middle]){
return middle;
}
else if(key <list[middle]){
return binary_search(key, low, middle-1);
}
else{
return binary_search(key,middle+1,high);
}
}
return -1;
}
● 이진 탐색 구현(반복적인 버전)
- 효율성 측면에서 순환호출 버전보다 우수하다.
int binary_search_itr(int key, int low, int high){
int middle;
while(low<high){
middle = (low+high)/2;
if(key == list[middle]){
return middle;
}
else if(key<list[middle]){
high = middle -1;
}
else{
low = middle +1;
}
}
return -1;
}
● 이진 탐색의 시간복잡도
- 이진 탐색은 탐색을 반복할 때마다 탐색 범위를 반으로 줄인다.
- 탐색 범위가 더 이상 줄일 수 없는 1이 될 때의 탐색 횟수를 k라 하면 탐색 범위는
횟수=0 일 때 n, 횟수=1 일 때 n/2, ... 횟수=k 일 때 n/2^k 이며
n/2^k =1 이므로 k = log2n 이다.
∴ O(log2n)
● 정렬된 배열에서의 색인 순차 탐색
색인 순차 탐색(indexed sequential search): 인덱스라 불리는 테이블을 사용하여 탐색의 효율을 높이는 방법
인덱스 테이블: 주 자료 리스트에서 일정 간격으로 발췌한 테이블
인덱스 테이블의 항목 수 = m, 주 자료 리스트의 데이터 수 = n 이면
각 인덱스 항목은 주 자료 리스트의 각 n/m번째 데이터를 가지고 있다.
- 인덱스 테이블에서 index[i] < key < index[i+1]을 만족하는 항목을 찾는 알고리즘
- 위 조건을 만족하는 항목으로부터 주 자료 리스트에서 순차 탐색 수행
typedef struct{
int key;
int index;
}itable;
itable index_list[INDEX_SIZE];위와 같은 구조체를 통해 인덱스 테이블을 구현하며, 탐색이 성공하면 해당 키의 인덱스를 반환한다.
int index_search(int key,int n){
int i,low,high;
if(key<list[0] || key>list[n-1]) return -1;
for(i=0; i<INDEX_SIZE; i++){
if(index_list[i].key <=key && index_list[i].key>key) break;
}
if(i == INDEX_SIZE){
low = index_list[i-1].index;
high = n;
}
else{
low = index_list[i].index;
high = index_list[i+1].index;
}
return seq_search(key,low,high);
}
● 색인 순차 탐색 알고리즘의 성능
인덱스 테이블의 크기 감소 = 주 자료 리스트에서의 탐색 시간 증가
인덱스 테이블의 크기 증가 = 인덱스 테이블의 탐색 시간 증가
인덱스 테이블의 크기 m, 주자료 리스트의 크기 n
∴ O(m+n/m)
1차 인덱스 테이블의 크기가 너무 커지게 되면 2차 인덱스 테이블을 두어서
2차 인덱스 테이블이 1차 인덱스 테이블의 인덱스를 가리키도록 한다.
● 보간 탐색
보간 탐색: 탐색키가 존재할 위치를 예측하여 탐색하는 방법
위의 그림을 보고 비례식을 세워보면
(list[high] - list[low]) : (key - list[low]) = (high - low) : (탐색 위치 - low)
탐색 위치 = (key -list[low]) / (list[high] - list[low]) * (high - low) + low
- 값은 일반적으로 실수이며 소수점 이하를 버려서 탐색 위치를 채택
- 탐색 위치의 리스트 값보다 키 값이 클 경우 (탐색 위치 + 1)의 리스트 값을,
탐색 위치의 리스트 값보다 키 값이 작을 경우 (탐색위치 - 1)의 리스트 값을 key값과 비교
- 위의 각각 케이스에서 비교했을 때 탐색에 성공하면 해당위치를, 탐색 실패하면 -1을 반환
int interpol_search(int key, int n){
int low, high, j;
low = 0;
high = n-1;
while((list[high]>key)&&(key>list[low])){
j = (float)(key-list[low])/(list[high]-list[low])*(high-low) + low;
if(key > list[j]) low = j+1;
else if( key< list[j]) low =j -1;
else low = j;
}
if(list[low] ==key) return low;
else return -1;
}
♠ 508p Quiz
01
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 1 | 2 | 3 | 5 | 6 | 8 | 9 | 10 | 4 |
| 1 | 2 | 3 | 5 | 6 | 8 | 9 | 10 | 4 |
| 1 | 2 | 3 | 5 | 6 | 8 | 9 | 10 | 4 |
| 1 | 2 | 3 | 5 | 6 | 8 | 9 | 10 | 4 |
| 1 | 2 | 3 | 5 | 6 | 8 | 9 | 10 | 4 |
| 1 | 2 | 3 | 5 | 6 | 8 | 9 | 10 | 4 |
| 1 | 2 | 3 | 5 | 6 | 8 | 9 | 10 | 4 |
| 1 | 2 | 3 | 5 | 6 | 8 | 9 | 10 | 4 |
| 1 | 2 | 3 | 5 | 6 | 8 | 9 | 10 | 4 |
9번
02
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 2 | 3 | 4 | 6 | 7 | 8 | 9 |
| 1 | 2 | 3 | 4 | 6 | 7 | 8 | 9 |
| 1 | 2 | 3 | 4 | 6 | 7 | 8 | 9 |
3번
03
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 2 | 4 | 5 | 7 | 8 | 9 | 10 |
| 1 | 2 | 4 | 5 | 7 | 8 | 9 | 10 |
2
'CS > Data Structure' 카테고리의 다른 글
| [C언어로 쉽게 풀어쓴 자료구조] 연습문제 13강 (0) | 2024.01.20 |
|---|---|
| [C언어로 쉽게 풀어쓴 자료구조] Chapter13. 탐색 (2) (2) | 2024.01.13 |
| [C언어로 쉽게 풀어쓴 자료구조] 연습문제 12강 (1) | 2024.01.07 |
| [C언어로 쉽게 풀어쓴 자료구조] Chapter12. 정렬 (2) (0) | 2024.01.04 |
| [C언어로 쉽게 풀어쓴 자료구조] Chapter12. 정렬 (1) (1) | 2023.12.19 |
