Doit자바 알고리즘 - 검색 알고리즘(선형검색)
업데이트:
검색 알고리즘
검색 알고리즘이란 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 것을 뜻한다.
검색과 키
주소록을 검색한다고 가정하자. 검색은 다음과 같은 과정으로 이루어진다.
- 국적이 한국인 사람을 찾는다.
- 나이가 21세이상 27세 미만인 사람을 찾는다.
- 찾으려는 이름과 가장 비슷한 이름의 사람을 찾는다.
어떤 검색을 하더라도 특정 항목에 주목한다는 점은 ‘검색하기’의 공통점이다. 여기서는 그 주목하는 항목을 키(key)라고 한다.
배열에서 검색하기
여기서 설명하는 세 가지 검색기법 중 몇몇은 자료구조에 의존하는 방법이다.
- 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색 수행
- 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행한다.
- 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행한다.
- 체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법
- 오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법
데이터의 집합이 있을때 ‘‘검색만 할것이다!’라고 생각한다면 사용할 알고리즘은 계산 시간이 짧은 것을 선택하면 된다. 그러나 데이터 집합에 대한 검색뿐 아니라 데이터의 추가, 삭제 등을 자주하는 경우라면 검색 이외의 작업에 소요되는 비용을 종합적으로 평가하여 알고리즘을 선택해야 한다. 예를 들어, 데이터 추가를 자주하는 경우에는 검색이 빠르더라도 데이터의 추가 비용이 많이 들어가는 알고리즘은 피해야 한다.
따라서, 어떤 목적을 이루기 위해 선택할 수 있는 알고리즘이 여러가지인 경우에는 용도나 목적, 실행속도, 자료구조 등을 고려하여 알고리즘을 선택해야 한다.
선형 검색
배열을 검색하는 방법 중 가장 기본적인 알고리즘이다.
요소가 직선 모양으로 늘어선 배열에서 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색한다. 이것이 선형검색(liner search)또는 순차 검색(sequential search)이라는 알고리즘이다.
배열검색의 종료조건은 2개이다. 다음 조건 중 하나라도 성립하면 검색을 종료한다.
- 검색할 값을 발견하지 못하고 배여르이 끝을 지나간 경우
- 검색할 값과 같은 요소를 발견한 경우
- 선형검색 구현
package com.practiceExample.Doit.chap03;
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 == 0)
return -1;
if(a[i] == key)
return i;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("요솟수 : ");
int num = scanner.nextInt();
int[] x = new int[num]; // 요솟수가 num인 배열
for(int i = 0; i < num; i++) {
System.out.println("x[" + i + "] : ");
x[i] = scanner.nextInt();
}
System.out.print("검색할 값 : "); // 키 값을 검색
int ky = scanner.nextInt();
int idx = seqSearch(x, num, ky); // 배열 x에서 키 값이 ky인 요소를 검색
if(idx == -1) {
System.out.println("그 값의 요소가 없습니다.");
} else {
System.out.println(ky + "은(는) x[" + idx + "]에 있습니다.");
}
}
}
메서드 seqSearch는 배열a의 처음부터 끝까지 n개의 요소를 대상으로 값이 key인 요소를 선형 검색하고 검색한 요소의 인덱스를 반환한다.또한 값이 key인 요소가 여러 개 존재할 경우 반환값은 처음 발견한 요소의 인덱스가 된다. 값이 key인 요소가 존재하지 않으면 -1을 반환한다.
배열의 검색 부분을 while문이 아니라 for문으로 구현하면 프로그램은 보다 짧고 간결해진다.
static int seqSearch(int[] a, int n, int key) {
int i = 0;
for(i = 0; i < n; i++) {
if(a[i] == key) {
return i;
}
}
return -1;
}
보초법
선형 검색은 반복할 때 마다 다음의 종료 조건 1과 2를 모두 판단한다. 단순한 판단이라고 생각할 수 있지만 ‘티끌 모아 태산’이 되어 종료조건을 검사하는 비용을 무시할 수 없게 된다.
- 종료조건 1 : 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
- 종료조건 2 : 검색할 값과 같은 요소를 발견한 경우
이 비용을 절반으로 줄이는 방법이 보초법(sentinel method)이다.
검색하기 전에 검색하고자 하는 키 값을 맨 끝 요소 a[7]에 저장한다. 이때 저장하는 값을 보초(sentinel)이라고 한다.
- a : 2를 검색하기 위해 보초로 a[7]에 2를 저장한다.
- b : 5를 검색하기 위해 보초로 ㅁ[7]에 5를 저장한다.
그러면 b처럼 원하는 값이 원래의 데이터에 존재하지 않아도 보초인 a[7]까지 검색하면 종료조건 2가 성립한다. 이로써 종료조건 1은 필요가 없어졌다. 보초는 반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 한다.
- 보초로 원하는 키값을 찾는 예제
package com.practiceExample.Doit.chap03;
import java.util.Scanner;
// 선형 검색(보초법)
public class SeqSearchSen {
// 요솟수가 n인 배열 a에서 key와 같은 요소를 보초법으로 선형 검색한다.
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;
// while문에 의한 반복이 완료되면 찾은 값이 배열의 원래 데이터인지 아니면 보초인지
// 판단해야 한다. 변수 i값이 n이면 찾은 값이 보초이므로 검색 실패임을 나타내는
// -1을 리턴한다.
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("요솟수 : ");
int num = scanner.nextInt();
int[] x = new int[num + 1]; //요솟수 num + 1
for(int i = 0; i < num; i++) {
System.out.print("x[" + i + "] : ");
x[i] = scanner.nextInt();
}
System.out.println("검색할 값 : "); // 키 값을 입력
int ky = scanner.nextInt();
int idx = seqSearchSen(x, num, ky); // 배열 x에서 값이 ky인 요소를 검색
if(idx == -1) {
System.out.println("그 값의 요소가 없습니다.");
} else {
System.out.println(ky + "은(는) x[" + idx + "]에 있습니다.");
}
scanner.close();
}
}
seqSearchSen메서드의 while문으로 for문으로 바꾼 것.
static int seqSearchSen(int[] a, int n, int key) {
int i;
a[n] = key; // 보초를 추가
for(i = 0; a[i] != key; i++)
;
return i == n ? -1 : i;
}
댓글남기기