데이터 집합에서 원하는 값을 가진 요소를 찾아내는 검색 알고리즘을 살펴보자.
검색과 키 살펴보기
주소록을 검색한다고 가정하자. 검색은 다음과 같이 다양한 방법으로 이루어진다.
- 국정이 한국인 사람을 찾는다.
- 나이가 21세 이상, 27세 미만인 사람을 찾는다.
- 찾으려는 이름과 가장 비슷한 이름을 가진 사람을 찾는다.
이러한 검색은 특정 항목에 주목한다는 공통점이 있다. 이 때 주목하는 항목을 키(key)라한다. 국적을 검색할 때에는 국적이 키가되고, 나이를 검색할 때에는 나이가 키가 된다. 데이터가 정숫값처럼 단일값이면 데이터값이 그대로 키값이 되지만 대부분의 경우에서는 키는 데이터의 일부이다.
위 검색 과정을 살펴보면 키값을 다음과 같이 지정한다.
- 키값과 일치하도록 지정한다. 키 = 한국
- 키값의 구간을 지정한다. 21세 <= 키값범위 < 27세
- 키값과 비슷하도록 지정한다. 발음이 가장 비슷한 이름
물론 조건은 하나만 지정하기도 하지만 논리곱이나 논리합을 사용해 여러 조건을 복합해 서 지정하기도 한다.
세 가지 검색 예시
검색에는 여러 검색 예시가 있지만 책에는 3가지 검색을 예시로 들고있다.
배열에서 검색하기, 선형 리스트에서 검색하기, 이진트리에서 검색하기이다.
이 글에서는 배열에서 검색하기만 포스트한다.
배열에서 검색하기
배열에서 검색은 다음 알고리즘을 활용한다.
- 선형 검색: 무작위로 늘어서 있는 데이터 모임에서 검색을 수행한다.
- 이진 검색: 일정한 규칙으로 늘어서 있는 데이터 모임에서 아주 빠른 검색을 수행한다.
- 해시법: 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행한다.
체인법: 같은 해시값의 데이터를 선형 리스트로 연결하는 방법
오픈 주소법: 데이터를 위한 해시값이 충돌할 때 재해시하는 방법
해시법은 데이터 검색뿐만 아니라, 추가나 삭제 등을 효율적으로 수행할 수 있는 종합적인 방법이다.
데이터 집합이 추가 / 삭제가 잘 일어나지 않는 구조라면 검색만 빠르게 일어나면 된다. 하지만 데이터 집합이 추가 / 삭제가 잘 일어나는 구조라면 검색 이외의 작업에 소요되는 비용과 종합적으로 평가를 하여 알고리즘을 선택해야 한다.
검색이 매우 빨리 끝나 봐야 추가 / 삭제 하는데 오래 걸리는 자료구조를 실시간으로 변하는 데이터 집합에 사용한다면 굉장히 비효율 적일것이다. 따라서 목적을 이루기 위해 선택할 수 있는 알고리즘이 여러 가지라면, 용도나 목적, 실행속도, 자료구조 등을 고려해야 한다.
데이터 추가 비용은 어떤 경우에 더 많이 들까?
학생의 번호 순서대로 키(height)값을 넣은 배열이 있다고 가정하면, 학생의 번호만 알면 바로 킷값을 알 수 있다. 하지만 새로운 학생이 전학와 중간에 데이터를 끼워 넣어야 한다면 이후 학생들은 모두 뒤로 밀어내는 작업을 해야 한다. 바로 이런 경우에 '배열을 빠르게 검색할 수 있지만 데이터를 추가하는데 비용이 많이 든다'라고 한다.
거의 모든 자료구조는 검색성능 - 데이터 변경성능 사이가 반비례한다. 따라서 개발자 스스로 어떤 자료구조가 사용되면 좋을까? 라는 생각을 하면서 자료구조/알고리즘을 선택해야 한다.
선형 검색
배열을 검색하는 방법중 가장 기본적인 선형 검색이라는 알고리즘을 살펴보자.
요소가 직선 모양으로 늘어선 배열에서 검색은 원하는 키값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하면 된다. 이것이 '선형 검색(linear search)' 또는 '순차 검색(sequential search)'이라는 알고리즘이다.
배열은 메모리 상에 연속적으로 데이터가 존재한다. 따라서 얻고자하는 인덱스(키값)만 있으면 해당 메모리로 바로 들어가 검색을 할 수 있다. 하지만 얻고자하는 인덱스가 없을시에는 원하는 값이 나올때 까지 처음부터 끝까지 조회할 수 있다.
int[] intA = {6,4,3,2,1,2,8};위와 같은 배열이 있다고 하자. 여기서 2를 찾고싶다면 아래처럼 진행된다.
- 0번째 인덱스를 조회. 결과는 6으로 넘어감.
- 1번째 인덱스를 조회. 결과는 4로 넘어감
- 2번째 인덱스를 조회. 결과는 3으로 넘어감.
- 3번째 인덱스를 조회. 결과는 2로 검색 성공.
참 간단하다. 하지만 여기서 9를 검색하면 모든 인덱스를 다 둘러보고도 9를 발견할 수 없어 검색에 실패할것이다.
따라서 선형 검색에서 배열 검색의 종료 조건은 2개이다. 다음 조건중 하나라도 성립하면 검색을 종료하게 된다.
종료조건1: 종료 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 -> 검색 실패
종료조건2: 종료 검색할 값과 같은 요소를 발견한 경우 -> 검색 성공
배열의 요솟수가 n개일 때 종료 조건 1,2를 판단하는 횟수는 평균 n / 2회 이다.
요솟수가 n인 배열 a에서 값이 key인 요소를 검색하는 코드는 다음과 같다.
for(int i = 0; i < n; i++) {
if(a[i] == key)
return a[i];
// return i // 인덱스값만 반환
}
return -1; // 검색 실패배열의 모든 요소를 검색했으나 a[i] == key가 성립하지 않은 경우 - 종료 조건1
배열의 요소를 하나씩 검색하여 a[i] == key를 성립시켰을 경우 - 종료조건 2
이것이 바로 배열의 기본적인 검색입니다. 이 간단한 선형 검색은 배열에 원하는 key값이 2개 이상이라면 제일 처음 일치하는 요소를 반환합니다.
보초법으로 선형 검색 구현하기
선형 검색은 반복할 때마다 위에서 배운 종료조건 1,2를 모두 판단한다. 단순한 판단이지만, 종료 조건을 검사하는 비용은 결코 무시할 수 없다.
이 비용을 반(1/2)로 줄이는 방법이 보초법(sentinel method)이다.
int[] intA = {6,4,3,2,1,2,8};위와 같은 배열이 있다고 치자. 여기서 5를 검색하는데 보초법을 활용한다고 하면, 마지막 요소인8 뒤에 5를 하나 추가한다음, 이를 검색한다.
int[] intA = {6,4,3,2,1,2,8,5(보초)};
// 5가 원래 데이터에는 없었지만 검색 실패를 막기 위해 추가됨.이렇게 되면 종료 조건1은 필요가 없다. 무조건 종료 조건2(검색 성공)를 성립하기 때문이다.
보초는 반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 하게 된다.
보초법 예제
public class 보초법 {
static int seqSearchSen(int[] a, int n, int key) {
int i = 0;
a[n] = key; // 보초를 추가
while (true) {
if (a[i] == key)
break;
i++;
}
return i == n ? -1 : i;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("요솟수 :");
int num = sc.nextInt();
int[] x = new int[num + 1]; // 보초를 위해 요솟수가 num + 1인 배열
for (int i = 0; i < num; i++) {
System.out.print("x[" + i + "]: ");
x[i] = sc.nextInt();
}
System.out.print("검색할 값: ");
int ky = sc.nextInt();
int idx = seqSearchSen(x, num, ky);
if(idx == -1)
System.out.println("그 값의 요소가 없다.");
else System.out.println("그 값은 x[" + idx + "]에 있다.");
}
}- 검색할 값 key를 보초로 a[n]에 대입한다.
- 배열 요소를 순서대로 스캔한다. 예제에서는 while을 사용했기에 if문이 2개필요하지만, 보초법을 사용한 while문은 if문이 한개로 줄어든다.
if (i == n) // 종료 조건1 보초법에서는 필요가 없어진다.
if(a[i] == key) // 종료 조건2- 마지막에만 i == n을 비교하여 -1혹은 인덱스 정보를 반환한다.
궁금증..
근데 이건 while문을 사용할때만 해당하는 이야기 아닌가? for문을 사용하면 될 것 같은데 싶어서 고민을 해 봤는데, while문 + 보초를 사용한 경우가 더 빠를것 같다고 결론 지었다. for문이 좀 더 간단해 보이지만 for문 자체에 조건식이 있는것과는 달리 while문은 true를 박아놓고 돌리기 때문에 큰 자료에서는 상당한 성능 차이가 발생할 것 같았다. 그래서 이를 테스트 해 본 코드가 아래이다.
※ 객체지향은 개나 줘버린 테스트 코드이다. 이해하려고 하지 말자
import java.util.Arrays;
import java.util.Calendar;
public class Test {
public static void main(String[] args) {
int[] arr = new int[400000000]; // 최대한 부하주기 위해 4억번
Arrays.fill(arr, 9);
int[] whileArr = new int[400000001]; // 보초를 위해 +1
Arrays.fill(whileArr, 9);
whileArr[400000000] = 5; // 보초칸에 5저장. 5만 조회할것임
Calendar d1 = Calendar.getInstance();
long start = d1.getTimeInMillis();
// 여기 부분을 바꾸면서 테스트해야함. 하나는 for문 사용 메서드, 하나는 while문 사용 메서드
System.out.println(forFind(arr, 5));
// System.out.println(forWhileSen(whileArr, 5));
Calendar d2 = Calendar.getInstance();
long finish = d2.getTimeInMillis();
System.out.println("\n걸린시간 : " + (finish - start) + "ms");
}
static int forFind(int[] arr, int find) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] == find) {
return i;
}
}
return -1;
}
static int forWhileSen(int[] whileArr, int find) {
int i = 0;
while(true) {
if(whileArr[i] == find)
break;
i++;
}
return i == 400000000 ? -1 : i;
}
}결론
결과는 아래와 같았다.
for : 125, 133, 121, 119, 130
보초while : 124, 124, 125, 127, 125
보초없는while : 253, 216, 238, 217, 216
성능 차이가 거의 없었다. 분명 for문은 조건식이 2개, 보초while문은 1개인데 왜 없는가 모르겠어서 gpt한테 물어본 결과
for 루프의 조건식 검사와 if 문의 조건식 검사는 매우 빠른 연산이므로 이들 사이의 성능 차이는 무시할 수 있을 정도입니다. 실제 성능 차이는 주로 데이터 구조의 크기(즉, 배열의 길이)와 데이터 구조에 대한 연산의 복잡성에 따라 달라집니다. 따라서 두 메서드 모두 배열의 모든 요소를 검사하므로 성능 차이는 없습니다. 이는 두 메서드가 동일한 알고리즘을 사용하기 때문입니다. 이 알고리즘은 배열의 모든 요소를 검사하므로, 배열의 크기에 비례하는 시간이 걸립니다. 이것이 선형 검색 알고리즘의 특성입니다. 따라서 두 메서드 간에 성능 차이가 없는 것은 예상되는 결과입니다.
라고 한다. ㅎㅎ
이진 검색
이번엔 이진 검색법을 살펴보자, 이 알고리즘을 적용하는 전제 조건은 데이터가 키값으로 이미 정렬(sort)돼 있다는 것이다. 이진 검색은 선형 검색보다 좀 더 빠르게 검색할 수 있는 장점이 있다.
이진 검색(binary search)은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다.
다음처럼 오름차순으로 정렬된 데이터에서 39를 검색하는 과정을 생각해 보자
int[] a = {5,7,15,28,29,31,39,58,68,70,95};
//index 0,1, 2, 3, 4, 5, 6, 7, 8, 9,10위 배열은 숫자가 오름차순으로 정렬돼있기에 중간값인 a[5]인 31부터 검색을 시작한다. 우리가 찾을 값인 39는 a[5]인 31 보다 크기 떄문에 검색 대상을 뒤쪽 5개(a[6] ~ a[10])로 좁힐 수 있게 된다. 그리고 다음 검색 범위(a[6] ~ a[10])의 중앙 요소인 a[8]을 선택한다. 이번에 a[8]은 68인데 39는 이보다 작다. 이말은 a[8]의 앞에 39가 존재한다는 뜻이고 a[6], a[7] 이렇게 두 요소만 남는다. 이렇게 짝수개로 남을 경우 중앙에서 앞쪽의 값을 선택하는데, a[6]가 선택되어 39랑 비교하게 되고, 39가 맞다면 그대로 a[6]를 반환하고, 아니라면 a[7]을 반환하게 된다.
이진 검색 알고리즘의 종료 조건은 다음과 같다
종료 조건1: a[중앙인덱스]와 key가 일치한다
종료 조건2: 검색 범위가 더이상 없다.
위의 과정에서 a[6], a[7]이 둘다 39가 아니었으면 종료 조건2가 성립하면서 검색을 종료한다.
이진 검색은 검색을 반복할 때마다 검색 범위가 절반이하가 되므로 검색에 필요한 비교 횟수의 평균값은 log n이다.
예제
import java.util.Scanner;
public class 이진검색 {
static int binSearch(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 (pl <= pr);
return -1; // 검색 실패!
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("요솟수: ");
int num = sc.nextInt();
int[] x = new int[num]; // 요솟수가 num인 배열
System.out.println("오름차순으로 입력하세요.");
System.out.print("x[0]: "); // 첫 요소 입력받음
x[0] = sc.nextInt();
for (int i = 1; i < num; i++) {
do {
System.out.print("x[" + i + "]: ");
x[i] = sc.nextInt();
} while (x[i] < x[i - 1]); // 바로 앞의 요소보다 작으면 다시 입력받음
}
System.out.print("검색할 값: "); // 키값을 입력받음
int ky = sc.nextInt();
int idx = binSearch(x, num, ky); // 배열 x에서 값이 ky인 요소를 검색
if(idx == -1)
System.out.println("그 값의 요소가 없습니다.");
else
System.out.println("그 값은 x[" + idx + "]에 있습니다.");
}
}