저번 내용에 이어서 이번주는 검색 알고리즘에 대해 학습할 예정이다.
Do it! 자료구조와 함께 배우는 알고리즘 입문 책으로 공부하고 있다.
- 검색 알고리즘
- 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 알고리즘이다.
- '검색하기' => 특정 항목에 주목한다. == Key 값
- '국적이 한국인 사람' / '나이가 21세 이상 27세 미만인 사람'
- 방법
- 배열: 이번 장에서는 배열에서의 검색을 학습한다!
- 연결 리스트
- 이진검색트리
- 배열 검색
- 선형 검색: 무작위로 늘어놓은 데이터 모임에서 검색을 수행
- 이진 검색: 일정한 규칙으로 늘어놓은 데이터 모임에서 빠른 검색
- 해시법: 추가 / 삭제가 자주 일어나는 데이터 모임에서 빠른 검색
- 체인법
- 오픈 주소법
ex) 데이터 추가를 자주하는 경우 검색이 빠르더라도 데이터를 추가하는 비용이 많이 들어가지 않는
알고리즘을 택하는 것이 좋다.
=> 중간에 데이터를 끼워넣는 경우에 중간 이후 학생들을 뒤로 밀어 넣는 작업을 해야하는 소요가 생긴다.
1. 선형 검색
배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 순서대로 요소를 검색한다.
=> 배열의 요소를 맨 앞부터 순서대로 검색한다.
- 성공
- 진행하다가 원하는 값을 만난다.
- 실패
- 검색할 값을 발견하지 못하고 배열의 끝을 지난다.
즉, 배열 검색의 종료 조건은 2가지임을 알 수 있다.
static int seqSearch(int[] a, int n, int key){
for(int i = 0; i<n; i++){
if(a[i] == key){
return i;
}
}
return -1;
} //for문으로 나타낸 선형 검색
//종료 조건 2가지 : 성공 / 끝까지 가면 -1 반환
- 보초법(sentinel 센티넬)
- 선형 검색은 반복할 때마다 종료 조건 2가지를 판단한다.
- 이러한 검사 비용을 반으로 줄이는 방법이 '보초법'이다.
- 전에 사용한 while문과 비교해보자
static int seqSearch(int[] a, int n, int key){
int i = 0;
while(true){
if(i == n){
return -1;
}
if(a[i] == key){
return i;
}
i++
}
}
static int seqSearchSen(int[] a, int n, int key){ //보초법
int i = 0;
a[n] = key; //배열의 마지막 요소에 찾고자 하는 키 값을 넣는다.(보초)
while(true){
if(a[i] == key){ //전에 있던 while문에서는 if문이 2개 있었다.
break;
}
i++;
}
return i == n ? -1 : i;
}
=>검색하고자 하는 key값을 맨 뒤에 보초를 세운다.
반복문에서 종료 조건을 판단하는 횟수를 2번에서 1번으로 줄인다.
변수 i가 n이면 찾은 값은 보초이므로 검색 실패를 의미한다.
2. 이진 검색
전제 조건: 데이터가 키 값으로 이미 정렬되어 있다는 것이다. (오름차순 or 내림차순)
pl: 0
pr: n-1
pc: (n-1)/2 로 가정
- key값보다 중앙값인 pc가 더 작을 때
- a[pl] ~ a[pc]는 key보다 작은 것이 분명하므로 검색 대상에서 제외
- 검색 범위는 a[pc+1] ~ a[pr]로 변경된다.
- pl의 값을 pc + 1로 업데이트한다.
- key값보다 중앙값인 pc가 더 클 때
- a[pc] ~ a[pr]은 key보다 큰 것이 분명하므로 검색 대상에서 제외
- 검색 범위는 a[pl] ~ a[pc-1]로 변경된다.
- pr의 값을 pc-1로 업데이트한다.
- 성공
- a[pc]와 key가 일치하는 경우
- 실패
- 검색 범위가 더 이상 없는 경우 => pl이 pr보다 커지면서 검색 범위를 더 이상 계산할 수 없다.
- ex) key가 6이고 축소된 검색 범위가 7 하나일 때 pr을 pc - 1로 업데이트하면 pl이 pr보다 더 커진다.
따라서 비교 횟수의 평균값은 logn이다. 검색을 반복할 때마다 범위가 절반이 되기 때문이다.
실패 => log(n+1)회 / 성공 => logn - 1회
import java.util.Scanner;
public class BinarySearch {
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 + 1];
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 key = sc.nextInt();
int idx = binSearch(x,num,key);
if(idx == -1){
System.out.println("그 값의 요소가 없습니다.");
}
else{
System.out.println(key + "은 x["+idx+"]에 있습니다.");
}
}
}
3. 복잡도: 알고리즘의 성능을 객관적으로 평가하는 기준
- 시간 복잡도: 실행에 필요한 시간을 평가한 것
- 공간 복잡도: 파일 공간과 메모리 영역이 얼마나 필요한가를 평가한 것
n/2와 n의 차이 -> O(n/2)가 아닌 O(n)으로 표기하는 이유는 n의 값이 무한히 커진다고 생각했을 때
그 값의 차이가 무의미해지기 때문이다.
또한, 2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 더 높은 쪽의 복잡도를 우선시한다.
- 선형 검색의 시간 복잡도
- 주로 O(n)이 걸린다.
- 처음 요소부터 마지막까지 가야되는 경우가 발생한다.
- 이진 검색의 시간 복잡도
- O(logn)이 걸린다.
- 검색 범위가 반으로 줄어들어서 logn이 나온다.
- java에서 제공하는 이진 검색 메소드 활용
- 자바 메서드
- 인스턴스 메서드(비정적 메서드): static을 붙이지 않고 선언한 메서드
- 클래스 메서드(정적 메서드): static을 붙이고 선언한 메서드
- '메서드가 인스턴스에 포함되는지의 여부' 가 차이점이다.
- 자바 메서드
class Id {
private static int counter = 0;
private int id;
public Id() {
id = ++counter;
}
public int getId(){
return id;
}
public static int getCounter(){
return counter;
}
}
public class WeekTwo {
public static void main(String[] args) {
Id a = new Id();
Id b = new Id();
System.out.println("a의 아이디 : " + a.getId());
System.out.println("b의 아이디 : " + b.getId());
System.out.println("부여한 아이디의 개수 : " + Id.getCounter());
}
}
=> static이 붙은 클래스 변수도 인스턴스에 포함되지 않는 변수이다.
인스턴스 메서드 호출: 객체.메서드 이름
클래스 메서드 호출: 클래스 이름.메서드 이름 으로 호출하는 방식이다.
- Java에서는 이진 검색을 하는 메서드를 표준 라이브러리로 제공한다.
- java.util.Arrays 클래스의 binarySearch 메서드
- 이진 검색 메서드를 직접 코딩할 필요가 없다.
- 모든 자료형 배열에서 검색 가능하다.
- binarySearch메서드
- 오름차순으로 정렬된 배열a를 가정하고, key값인 요소를 이진 검색한다.
- static int binarySearch(Object[] a, Object Key);
- 검색 성공: key와 일치하는 요소의 인덱스를 반환한다.
key값과 일치하는 요소가 여러 개 있다면 무작위의 인덱스를 반환한다. - 검색 실패: 삽입 포인트 - 검색하기 위해 지정한 key보다 큰 요소들 중 첫 번째 요소의 인덱스이다.
검색에 실패했을 때 삽입 포인트를 x라고 하면 -x-1을 반환한다.
- 검색 성공: key와 일치하는 요소의 인덱스를 반환한다.
- 객체 배열에서 검색하기
- static int binarySearch(Object[] a, Object key); => 어떤 형태의 클래스도 받을 수 있게끔 최상위 클래스로 전달받는다.
자연 정렬이라는 방법으로 대소 관계 판단 - 정수 배열, 문자열 배열에 유리 - static <T> int binarySearch(T[] a, T key, Comparator<? super T> c);
"자연 순서"를 가지지 않는 클래스 배열에 유리 - 자연 정렬: 사람에게 자연스러운 정렬의 형태 1, 2, 10, 100 이런 순서
- 제네릭 메서드 사용 static int binarySearch(T[] a, T key, Comparator<? super T> c);
- 제네릭: 대상의 자료형에 의존하지 않는 클래스 구현 방식
- 클래스 이름 바로 뒤에 <Type> 같은 형식의 파라미터를 붙여 선언한다.
- 배열의 요소가 어떤 기준을 가지고 줄지어 있는지, 대소 관계를 판별하는지 직접 binarySearch메서드에
알려주어야 한다. 세 번째 파라미터에 전달해준다.
- 제네릭 메서드 사용 static int binarySearch(T[] a, T key, Comparator<? super T> c);
- static int binarySearch(Object[] a, Object key); => 어떤 형태의 클래스도 받을 수 있게끔 최상위 클래스로 전달받는다.
Comparator<? super T> c
클래스 T로 생성한 두 객체의 대소 관계를 판단하기 위한 comparator이다. compare메서드가 있다.
comparator는 인터페이스, compare메서드는 구현체로 생각하면 되겠다.
import java.util.Comparator;
class X{
public static final Comparator<T> COMPARATOR = new Comp(); //그 후 객체 생성(2번)
private static class Comp implements Comparator<T> { //Comparator라는 인터페이스 구현
public int compare(T d1, T d2){
//여기에 먼저 구현 (1번)
}
}
}
import java.util.Arrays;
import java.util.Scanner;
import java.util.Comparator;
public class GenericSearch {
static class PhyscData{
private String name;
private int height;
private double vision;
public PhyscData(String name, int height, double vision){
this.name = name;
this.height = height;
this.vision = vision;
}
public String toString(){
return name + " " + height + " " + vision;
}
public static final Comparator<PhyscData> HEIGHT_ORDER
= new HeightOrderComparator();
private static class HeightOrderComparator implements Comparator<PhyscData>{
@Override
public int compare(PhyscData o1, PhyscData o2) {
return Integer.compare(o1.height, o2.height);
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
PhyscData[] x = {
new PhyscData("이나령", 162, 0.3),
new PhyscData("유지훈", 168, 0.4),
new PhyscData("김한결", 169, 0.8),
};
System.out.print("몇 cm인 사람을 찾고 있나요? : ");
int height = sc.nextInt(); //키 입력
int idx = Arrays.binarySearch(
x, //배열 x에서
new PhyscData("", height, 0.0), //키가 height인 요소를
PhyscData.HEIGHT_ORDER //HEIGHT_ORDER에 의해 검색
);
if(idx<0){
System.out.println("요소가 없습니다.");
}
else{
System.out.println("x["+idx+"]에 있습니다.");
System.out.println("찾은 데이터 : " + x[idx]);
}
}
}
다음엔 제네릭 기법과 스택, 큐에 대해서 학습해야겠다.
제네릭은 실무에서도 사용한다고 하니 더욱 주의해야겠다!