배열을 이용한 검색 알고리즘
검색 알고리즘, 즉 특정 항목에 해당하는 키(key)를 찾는 알고리즘에 대해 다뤄볼 것이다.
검색 알고리즘의 세 가지 예로, 배열 검색, 선형 리스트 검색, 이진검색트리 검색이 있는데 뒤의 두 가지 알고리즘은 자료구조에 의존하는 방법이다.
알고리즘이 계산 시간이 짧다고 무조건 좋은 건 아니다.
데이터의 추가나 삭제 등을 하는 경우에 검색 이외의 작업에 소요되는 비용도 고려해야한다.
이와 같이 용도나 목적, 실행속도, 자료구조 등의 여러 비용들을 종합적으로 평가하여 가장 적합한 알고리즘을 선택해야한다.
이번 글에서는 배열 검색에 대해 다뤄보겠다.
선형 검색(linear search)
선형 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞에서 부터 순서대로 요소를 탐색하는 방법이다.
int a[6] = {1, 2, 3, 4, 5, 6};위와 같이 선언됀 배열에서 4를 찾기 위해서
a[0]부터 a[1], a[2], a[3] 하나 씩 탐색하다 a[3]에서 4를 찾으면 검색 성공으로 탐색을 중단하는 식으로 진행된다.
다른 예로 7을 찾으려한다면 앞에서부터 탐색하다 끝까지 탐색했음에도 7에 해당하는 키가 없으므로 검색 실패로 검색을 종료하게 된다.
즉 검색 종료의 조건은 아래와 같다.
- 검색한 값과 같은 요소를 발견 (성공)
- 배열의 끝을 지났음에도 검색할 값이 없는 경우 (실패)
#include <stdio.h>
#include <stdlib.h>
int search(const int a[], int n, int key){
for(int i = 0; i < n; i++){
if(a[i] == key) return i;
return -1;
}
}
위의 내용을 바탕으로 요소의 개수가 n개인 배열 a에서 key와 일치하는 요소를 선형검색하는 함수를 짜보았다.
여기서 값 key인 요소가 여러 개 존재한다면 반환값은 처음으로 발견한 요소의 인덱스가 된다.
선형 검색은 최악의 경우에 n번 다 둘러봐야 하므로 비효율적인 알고리즘이지만, 임의로 늘어놓은 배열에서 검색하는 사실상 유일한 방법이다.
보초법으로 종료 판단 횟수 줄이기
- 검색한 값과 같은 요소를 발견 (성공)
- 배열의 끝을 지났음에도 검색할 값이 없는 경우 (실패)
보초법을 사용한다면 위의 기존 종료 판단의 횟수를 줄일 수 있다.
int *x = {1, 2, 3, 4, 5, 6, NULL};예를 들자면 위와 같이 n+1개의 크기로 할당한 배열의 NULL 자리에다 검색할 값을 넣음으로써
결국엔 검색 실패를 하더라도 마지막에서 찾은것과 같은 효과로 종료 판단을 줄일 수 있는 것이다.
여기서 i값이 n과 같은지 확인하여 실패여부는 반환할 수 있다.
이를 코드로 구현해보겠다.
#include <stdio.h>
#include <stdlib.h>
int search(int a[], int n, int key){ //메인 함수에서는 n+1개로 할당한 배열을 매개변수로 전달해야한다
int i = 0;
a[n] = key; //보초를 추가
while(1){
if(a[i] == key) break;
i++;
}
return i;
}
이로써 if 문의 판단횟수가 1회 줄었다. 조건이 1회 다시 늘더라도 실패 여부를 반환하려면
return i == n ? -1 : i; 을 사용할 수도 있다.이진 검색(binary search)
이진 검색은 요소가 오름차순 또는 내림차순으로 정렬되어있는 배열에서 검색하는 알고리즘으로 선형 검색보다 좀 더 빠르게 검색할 수 있다는 장점이 있다.
CS50 강의에서는 David는 전화번호부로 이진 검색을 설명한다.
'홍길동'씨의 전화번호를 찾으려고 하는 우리는 전화번호부를 대충 절반쯤 편다.
펴고보니 '마'씨의 전화번호가 있다. 가나다순으로 정렬된걸 아는 우리는 앞의 절반은 버린 채 뒤의 절반에 집중한다.
뒤의 절반 중 대충 절반쯤을 폈다. 이번엔 '조'씨의 전화번호가 있다. 우리는 '홍'씨가 '조'씨보다 뒤에 있는걸 알기에, 뒤에서 1/4의 페이지에 집중한다.
뒤에서 1/4 페이지를 이리저리 넘겨보니 '후'씨의 전화번호들이 있다. '홍'의 'ㅗ'가 'ㅜ'보다 앞에 있다는걸 아는 우리는 조금 앞페이지로 다시 넘어간다.
이와 유사하게 검색 범위를 절반 씩 줄여가며 원하는 값이 나올때까지 탐색하는 방법을 이진 검색이라고 한다.
이 이론을 요약해보겠다.
먼저 검색 범위를 좁히는 과정은 이와 같다.
- 맨 앞 인덱스를 의미하는 pl = 0, 맨 뒤 인덱스를 의미하는 pr = n-1, 중앙값인 pc =(n-1)/2로 각각 변수들을 초기화한다.
- 중앙값이 key보다 작을때 : 중앙의 다음 요소를 새로운 pl로 보고 뒤쪽으로 범위를 좁힌다.
- 중앙값이 key보다 클때 : 중앙의 이전 요소를 새로운 pr로 보고 앞쪽으로 범위를 좁힌다.
종료 조건은 아래와 같다.
- 중앙값이 key와 일치하는 경우 - 검색 성공
- 검색 범위가 더 이상 없는 경우 - 검색 실패
둘 중에 하나라도 해당될 시에 종료된다.
#include <stdio.h>
#include <stdlib.h>
int bin_Ascending(int a[], int n, int key){ //오름차순으로 정렬된 배열을 이진 검색하는 함수
int pl = 0;
int pr = n-1;
do{
int pc = (pl+pr)/2;
if(a[pc] == key){
return pc;
}else if(a[pc] < key){
pl = pc + 1;
}else{
pr = pc - 1;
}
}while(pr >= pl);
return -1; //검색 실패
}
void main(){
int nx, ky;
puts("이진 검색");
printf("요소개수 : ");
scanf("%d", &nx);
int *x = calloc(nx, sizeof(int));
printf("오름차순으로 입력하세요.\n");
printf("x[0] : ");
scanf("%d", &x[0]); //맨 앞의 값은 반복문 밖에서 받고, 반복문 내에서 입력 받을때 조건문에서 사용
for(int i = 1; i < nx; i++){
do{
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}while(x[i] < x[i-1]); //앞의 값보다 작으면 다시 입력
}
printf("검색 값 : ");
scanf("%d", &ky);
int idx = bin_Ascending(x, nx, ky);
if(idx == -1) puts("검색에 실패했습니다. ");
else printf("%d는 x[%d]에 있습니다.\n", ky, idx);
free(x);
}
-----------------------------------
실행 결과
이진 검색
요소개수 : 3
오름차순으로 입력하세요.
x[0] : 1
x[1] : 2
x[2] : 7
검색 값 : 2
2는 x[1]에 있습니다.반복문 밖에서 x[0]을 받음으로써 오름차순으로 입력하지 않을 시 while 문을 충족시키지않아 다시 입력을 받도록 하는 점을 신경썼다.
복잡도란 ?
알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도라고 한다.
- 시간 복잡도 : 실행에 필요한 시간을 평가한 것
- 공간 복잡도 : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것
복잡도의 상한을 나타내는 빅오 표기법에 대해서는 글을 작성한 적이 있다. 이때의 설명을 첨가해보겠다.
빅 오 표기법
빅 오 표기법은 알고리즘이나 함수의 시간 복잡도(시간 복잡도의 상한)를 나타내는 표기법 중 하나이다.
알고리즘의 성능을 나타내는 방법 중에서 가장 많이 사용되는 것 중 하나이며, 주어진 입력에 대한 알고리즘의 실행 시간의 상한, 즉 최악의 경우에 걸리는 시간을 나타낸다. 이때 상수항이나 낮은 차수의 항을 무시한다는 점도 알아야한다.
빅 오는 주로 다음과 같은 표기법으로 표현된다.
O(1): 상수 시간. 입력의 크기와 관계없이 일정한 실행 시간.
O(log n): 로그 시간. 입력의 로그에 비례하는 실행 시간.
O(n): 선형 시간. 입력의 크기에 비례하는 실행 시간.
O(n log n): 선형 로그 시간. 일반적인 정렬 알고리즘과 같은 알고리즘의 실행 시간.
O(n^2), O(n^3), ...: 다항 시간. 입력의 제곱, 세제곱에 비례하는 실행 시간.
O(2^n): 지수 시간. 입력의 지수에 비례하는 실행 시간.쉽게 설명해 n이 무한히 커짐에 따라 상대적으로 무시되는 상수항이나 낮은 차수의 항을 생략하여 시간 복잡도의 상한을 표기하는 방법이다.
선형 검색의 시간 복잡도 : O(n)
int search(int a[], int n, int key){
int i = 0;
a[n] = key;
while(1){
if(a[i] == key) break;
i++;
}
return i;
}반복문에서 일치하는 key값이 맨 앞에 있을 수도, 뒤에 있을 수도 있으므로 평균 실행횟수는 n/2이고, 1번만 실행되는 코드도 있다.
빅 오 표기법에서는 상한선을 나타내기에 1/2이나 1번만실행되는 코드들은 무시된 채 O(n)이 된다.
이진 검색의 시간 복잡도 : O(log n)
int bin_Ascending(int a[], int n, int key){ //오름차순으로 정렬된 배열을 이진 검색하는 함수
int pl = 0;
int pr = n-1;
do{
int pc = (pl+pr)/2;
if(a[pc] == key){
return pc;
}else if(a[pc] < key){
pl = pc + 1;
}else{
pr = pc - 1;
}
}while(pr >= pl);
return -1; //검색 실패
}코드를 실행할 수록 절반씩 탐색할 영역이 줄어드는 원리로 인해 가장 큰 실행 횟수가 log n 이므로
1번 실행되는 코드들은 무시된 채 O(log n)이 된다.
CS50 강의를 들으며 이해만 했던 내용을 직접 구현해보고 보초법이라는 개념도 알게되고 이를 정리하여 글까지 작성하니 깊이있게 이해한 것 같아서 좋다.
