3장에서는 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 검색 알고리즘에 대해 알아보자.
검색 알고리즘
검색과 키
어떠한 검색 조건이 주어졌을 때, 그 검색조건이 주목하는 항목을 키(Key)라고 한다. 국적을 검색할 때는 국적이 키이고, 나이를 검색할 때는 나이가 키이다.
국적이 한국인 사람을 찾습니다.
나이가 21세 이상 27세 미만인 사람을 찾습니다.
데이터가 정수값과 같이 단일값이면 데이터값이 그대로 키값이 되지만 대부분의 경우에서 키는 데이터의 '일부'이다. 위의 검색 과정을 살펴보면 키값을 다음과 같이 지정하고 있다.
키값과 일치하도록 지정한다(한국).
키값의 구간을 지정한다(21세 이상 27세 미만).
검색의 종류
검색은 어떤 조건을 만족하는 데이터를 찾아내는 것이다.
이 중에서 이번에 알아볼 내용은 배열에서 검색이며, 아래와 같은 알고리즘을 활용한다.
1. 선형 검색 : 무작위로 늘어서 있는 데이터 모임에서 검색을 수행한다.
2. 이진 검색 : 일정한 규칙으로 늘어서 있는 데이터 모임에서 아주 빠른 검색을 수행한다.
3. 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행한다.
- 체인법 : 같은 해시값의 데이터를 선형 리스트로 연결하는 방법
- 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시하는 방법
해시법은 데이터 검색뿐만 아니라 추가나 삭제 등을 효율적으로 수행할 수 있는 종합적인 방법이다.
데이터 집합이 있을 때 '검색만 하면 되지!'라고 생각한다면 검색에 사용할 알고리즘은 계산 시간이 짧은 것을 선택하면 된다. 그러나 데이터 집합에서 검색뿐만 아니라 데이터를 추가하거나 삭제하는 작업을 자주한다면 검색 이외의 작업에 소요되는 비용을 종합적으로 평가하여 알고리즘을 선택해야 한다. 예를 들어 데이터 추가를 자주한다면 검색이 빠르더라도 데이터의 추가 비용이 많이 들어가는 알고리즘은 피해야 한다. 따라서 어떤 목적을 이루기 위해 선택할 수 있는 알고리즘이 여러 가지라면 용도나 목적, 실행 속도, 자료구조 등을 고려해야 한다.
배열에서 검색
1. 선형 검색(linear search) = 순차 검색(sequential search)
요소가 직선 모양으로 늘어선 배열에서 검색은 원하는 키값을 갖는 요소를 만날 때 까지 맨앞부터 순서대로 요소를 검색하면 된다. 이것이 선형 검색(linear search) 또는 순차 검색(sequential search)이라는 알고리즘이다.
선형 검색은 요소가 정렬되지 않은 배열에서 검색할 때 사용하는 유일한 방법이다.
선형 검색에서 배열 검색의 종료 조건은 2가지이다. 다음 조건 중 하나라도 성립하면 검색을 종료한다.
1. 종료 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 → 검색 실패
2. 종료 검색할 값과 같은 요소를 발견한 경우 → 검색 성공
💗 선형 검색 코드
import java.util.Scanner;
public class SeqSearch {
//요소수가 n인 배열 a에서 key와 값이 같은 요소를 선형 검색
static int seqSearch(int[] a, int n, int key) {
int i = 0;
while (true) {
if (i == n)
return -1; //종료조건 1: 검색 실패(-1을 반환)
if (a[i] == key)
return i; //종료조건 2: 검색 성공(인덱스를 반환)
i++;
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.print("요소수: ");
int num = scan.nextInt();
int[] x = new int[num]; //요소수가 num인 배열
for (int i = 0; i < num; i++) {
System.out.printf("x[%d]: ", i);
x[i] = scan.nextInt();
}
System.out.print("검색할 값: "); //키값을 입력받음
int ky = scan.nextInt();
int idx = seqSearch(x, num, ky); //배열 x에서 값이 ky인 요소를 검색
if (idx == -1)
System.out.println("그 값의 요소가 없습니다");
else
System.out.printf("그 값은 x[%d]에 있습니다.", idx);
}
}
메서드 seqSearch 는 배열 a의 처음부터 끝까지 n개인 요소를 대상으로 값이 key인 요소를 선행 검색하고 검색한 요소의 인덱스를 반환한다. 만약 값이 key인 요소가 여러 개 존재하면 검색 과정에서 처음 발견한 요소의 인덱스를 반환한다. 값이 key인 요소가 존재하지 않으면 -1을 반환한다.
무한 루프의 구현
무한으로 반복하는 구조는 break 문이나 return 문을 사용하여 루프에서 빠져나올 수 있다. 무한 루프는 아래와 같이 여러 방식으로 구현할 수 있다.
//1.
while (true) {
}
//2.
for ( ; true ; ) {
}
//3.
do {
} while (true);
for 문은 반복을 계속할지를 판단하는 제어식 true를 생략할 수 있다. 제어식을 생략하면 true가 지정된 것으로 본다. 코드는 보통 위에서 아래로 읽는다. 그래서 while 문과 for 문은 첫 번째 행만 읽어도 무한 루프인지 알 수 있다. 반면에 do 문은 끝까지 읽지 않으면 무한 루프인지 아닌지 알 수 없기 때문에 do 문으로 무한 루프를 구현하는 것은 권장하지 않는다.
for 문으로 구현
배열 검색을 while 문이 아니라 for 문으로 구현하면 프로그램은 짧고 간결해 진다. 아래 코드는 선형 검색 코드의 while 문을 for 문으로 수정한 코드이다.
//요소수가 n인 배열 a에서 key와 값이 같은 요소를 선형 검색
static int seqSearch(int[] a, int n, int key) {
for (int i=0; i<n; i++)
if (a[i] == key)
return i; //검색 성공(인덱스를 반환)
return -1; //검색 실패(-1을 반환)
}
보초법으로 선형 검색 구현하기
선형 검색은 반복할 때마다 다음의 종료 조건 1과 2를 모두 판단한다. 단순한 판단이라고 생각할 수 있지만 '티끌 모아 태산'이라는 말이 있듯이 종료 조건을 검사하는 비용은 결코 무시할 수 없다.
1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
2. 검색할 값과 같은 요소를 발견한 경우
이 비용을 반(50%)으로 줄이는 방법이 보초법(sentinel)이다.
배열 요소 a[0]~a[6]은 초기에 준비해 놓은 데이터이다. 맨 끝 요소 a[7]은 검색하기 전에 값을 저장하는 보초(sentinel)이다. 보초에는 다음과 같이 검색하고자 하는 키값을 저장한다.
a : 2를 검색하기 위해 보초로 a[7]에 2를 저장한다.
b : 5를 검색하기 위해 보초로 a[7]에 5를 저장한다.
b처럼 원하는 값이 원래 데이터에 존재하지 않아도 보초인 a[7]까지 검색하면 종료 조건 2가 성립된다. 이렇게 하면 원하는 키값을 찾지 못했을 때를 판단하는 종료 조건 1이 없어도 된다. 보초는 반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 한다. 아래 코드는 이런 보초법을 적용하여 선형 검색 코드를 수정한 코드이다.
💗 선형 검색 보초법 코드
import java.util.Scanner;
public class SeqSearchSen {
//요소수가 n인 배열 a에서 key와 값이 같은 요소를 보초법으로 선형 검색
static int seqSearch(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 scan = new Scanner(System.in);
System.out.print("요소수: ");
int num = scan.nextInt();
int[] x = new int[num + 1]; //요소수 = 원래 배열의 크기 + 보초의 자리
for (int i = 0; i < num; i++) {
System.out.printf("x[%d]: ", i);
x[i] = scan.nextInt();
}
System.out.print("검색할 값: "); //키값을 입력받음
int ky = scan.nextInt();
int idx = seqSearch(x, num, ky); //배열 x에서 값이 ky인 요소를 검색
if (idx == -1)
System.out.println("그 값의 요소가 없습니다");
else
System.out.printf("그 값은 x[%d]에 있습니다.", idx);
}
}
메서드 seqSearch 는
1. 검색할 값 key를 보초로 a[n]에 대입한다.
2. 배열 요소를 순서대로 스캔한다. 메서드 seqSearch 는 선형 검색 코드의 while 문에는 다음과 같이 if 문이 2개 있다.
if (i == n) //종료 조건1 ← 보초법에서는 필요하지 않음
if (a[i] == key) //종료 조건2
선형 검색 보초법 코드에서는 종료 조건1이 필요하지 않으므로 하나의 if 문만 사용했다. 따라서 반복 종료에 대한 판단 횟수가 절반으로 줄어든다.
3. while 문에 의한 반복이 완료되면 찾은 값이 배열의 원래 데이터인지 아니면 보초인지 판단해야 한다. 변수 i값이 n이면 찾은 값이 보초이므로 검색 실패임을 나타내는 -1을 반환한다. 변수 i값이 n이 아니면 찾은 값이 원래 데이터이므로 i값을 반환한다.
2. 이진 검색(binary search)
이진 검색(binary search)은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다. 이진 검색은 선형 검색보다 좀 더 빠르게 검색할 수 있다는 장점이 있다.
아래 그림과 같이 오름차순으로 정렬된 데이터에서 39를 검색하는 과정을 생각해보자. 먼저 배열의 중앙에 위치한 요소인 a[5]의 31부터 검색을 시작한다.
검색하려는 값인 39는 중앙 요소(a[5])보다 크다. 그러므로 검색 대상을 뒤쪽의 5개(a[6]~a[10])로 줄인다. 그리고 다음 검색 범위의 중앙에 위치한 요소인 a[8](68)을 선택한다.
검색할 값인 39는 중앙 요소(a[8])보다 작다. 그러므로 검색 대상을 앞쪽의 2개(a[6]~a[7])로 좁힌다. 두 요소의 중앙 요소로 앞쪽의 값 a[6](39)를 선택하여 원하는 값인지 확인한다.
☑ 두 인덱스 6과 7의 중앙값은 (6+7)/2로 계산하여 6이 되기 때문이다. 정수의 나눗셈은 나머지를 버린다.
39는 원하는 키값과 일치하므로 검색 성공이다.
검색 범위의 맨 앞 인덱스를 pl, 맨 끝 인덱스를 pr, 중앙 인덱스를 pc라고 지정한다. 검색을 시작할 때 pl은 0, pr은 n-1, pc는 (n-1)/2이다.
검색 대상의 범위는 안의 요소이고, 검색 대상에서 제외되는 범위는 안의 요소이다. 여기서 주목할 점은 이진 검색을 한 단계씩 진행할 때마다 검색 범위가 (거의) 반으로 좁혀진다는 것이다. 그리고 선택 요소를 한 번에 한 칸 씩 이동하는 선형검색과 달리 이진 검색은 ●로 표시한 선택 요소 a[pc]를 단숨에 여러칸 이동한다.
c처럼 a[pc]와 key를 비교하여 값이 같으면 검색 성공이다.
이진 검색 알고리즘의 종료 조건은 다음 종료 조건 1, 2 중 어느 한쪽이 성립하면 된다.
1. a[pc]와 key가 일치한다.
2. 검색 범위가 더 이상 없다.
💗 이진 검색 코드
import java.util.Scanner;
public class BinSearch {
//요소수가 n개인 배열 a에서 key와 같은 요소를 이진 검색
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 scan = new Scanner(System.in);
System.out.print("요소수: ");
int num = scan.nextInt();
int[] x = new int[num]; //요소수가 num인 배열
System.out.println("오름차순으로 입력하세요.");
System.out.print("x[0]: "); //첫 요소 입력받음
x[0] = scan.nextInt();
for (int i = 1; i < num; i++) {
do {
System.out.print("x[" + i + "]: ");
x[i] = scan.nextInt();
} while (x[i] < x[i - 1]); //바로 앞의 요소보다 작으면 다시 입력받음
}
System.out.print("검색할 값: "); //키값을 입력받음
int ky = scan.nextInt();
int idx = binSearch(x, num, ky); //배열 x에서 값이 key인 요소를 검색
if (idx == -1)
System.out.println("그 값의 요소가 없습니다");
else
System.out.println("그 값은 x[" + idx + "]에 있습니다.");
}
}