728x90
검색 알고리즘
검색과 키
- 검색을 할 때 특정 항목에 주목하게 되는데 이를 key라고 함
- key: 데이터의 일부
배열에서 검색
- 용도나 목적, 실행 속도, 자료구조 등을 고려하여 알고리즘 선택해야 함
다음의 알고리즘 활용
1. 선형 검색: 무작위로 늘어놓은 데이터 모임에서 검색
2. 이진 검색: 일정한 규칙으로 늘어놓은 데이터 모임에서 빠른 검색
3. 해시법: 추가, 삭제가 자주 일어나는 데이터 모임에서 빠른 검색
1) 체인법: 같은 해시 값의 데이터를 선형 리스트로 연결
2) 오픈 주소법: 데이터를 위한 해시 값이 충돌할 때 재해시
배열 검색의 종료 조건
- 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 = 검색 실패
- 검색할 값과 같은 요소를 발견할 경우 = 검색 성공
- 배열의 요솟수가 n개일 때 조건 1,2를 판단하는 횟수는 평균 n/2회
- 원하는 값이 배열에 존재하지 않는 경우 1는 n+1, 2는 n회
선형검색, 순차검색
- linear search, sequential search
- 맨 앞부터 순서대로 요소를 검색
- 한 번만 할 경우 빠름
보초법
- sentinel method
- 종료 조건의 비용을 반으로 줄이는 방법으로
검색하기 전 검색하고자 하는 키의 값을 맨 끝 인덱스에 저장 - 보초: 이 때 저장하는 값
- 보초는 종료 판단 횟수를 2회에서 1회로 줄이는 역할 = if(i == n) 조건 하나가 필요없음
이렇게 해 두면 원하는 키 값을 찾지 못했을 때 판단하는 종료 조건 1이 없어도 됨
이진검색
- 전제조건: 데이터가 키 값으로 이미 정렬되어 있어야 함 = 오름차순 or 내림차순
pl: 맨 앞 인덱스, 0
pr: 맨 끝 인덱스, n-1
pc: 중앙 인덱스, (n-1)/2
- a[pc]와 key를 비교하여 같으면 검색 성공
- 원하는 값을 찾지 못하면 아래와 같은 방법으로 검색 범위를 좁힐 수 있음
이진 검색의 검색 범위
1. a[pc] < key
- a[pl] ~ a[pc]는 검색 대상 제외
- a[pc+1] ~ a[pr]이 검색 범위가 되고, pl = pc+1로 업데이트 되면서 다시 검색
2. a[pc] > key
- a[pc] ~ a[pr]은 검색 대상 제외
- a[pl] ~ a[pc-1]이 검색 범위가 되고, pr = pc-1로 업데이트 되면서 다시 검색
이진 검색 알고리즘의 종료 조건
1. a[pc] == key일 경우 = 검색 성공
2. 검색 범위가 더 이상 없는 경우 = 검색 실패
이진 검색의 비교 횟수
- 검색을 반복할 때마다 검색 범위가 절반이 되므로
비교 횟수의 평균값 = long n - 검색에 실패 = [long n + 1] 회 //천장 메서드 기호?
- 검색에 성공 = (약) long n - 1회
- 천장 메서드: x보다 크거나 같으면서 가장 작은 정수, [3.5] 는 4
복잡도
- complexity
- 알고리즘의 성능을 객관적으로 평가하는 기준
1. 시간 복잡도: 실행에 필요한 시간을 평가
2. 공간 복잡도: 기억 영역과 파일 공간이 얼마나 필요한가를 평가 (메모리를 얼마나 차지하느냐)
- 예를 들어 선형 검색에서 배열을 그대로 받아서 쭉 검색하면 되므로 시간복잡도가 올라가고,
이진 검색을 할 때는 데이터를 전체적으로 한 번 정렬하므로 공간복잡도는 올라가지만, 시간복잡도는 낮아짐
선형 검색 - 시간 복잡도
static int seqSearch(int[] a, int n, int key) {
int i = 0; //1번
while(i < n) { //n번
if(a[i] == key) //n번
return i; //1번, 검색 성공
i++; //n번
}
return -1; //1번, 검색 실패
}O(1) - 한 번만 실행
O(n) - n에 비례하는 횟수만큼 실행하는 경우
- n이 점점 커지면서 O(n)에 필요한 계산 시간은 n에 비례하여 길어짐
- 그러나 O(1)에 필요한 계산 시간은 변하지 않음
O(f(n)), O(g(n)) 의 시간 복잡도를 계산하는 공식
O(f(n)) + O(g(n)) = O( max( f(n), g(n) ) )
max는 둘 중에 큰 쪽을 나타냄
전체 복잡도는 차원이 가장 높은 복잡도를 선택
- 선형 알고리즘의 복잡도 = O(1)+O(n)+O(n)+O(1)+O(n)+O(1) = O(max(1, n, n, 1, n, 1)) = O(n)
선형 검색 - 보초법
package chap03_1;
import java.util.Scanner;
//선형 검색(보초법)
public class Quiz1 {
//요솟수가 n인 배열 a에서 key와 같은 요소를 보초법으로 선형 검색 합니다.
static int seqSearchSen(int[] a, int n, int key) {
int i; //while 반복문 시작 = 0
a[n] = key; //보초를 추가, 맨 마지막 인덱스에 검색할 key 추가
/*
* while(true) {
* if(a[i] == key) { //검색 성공
* break;
* }
* i++;
* }
*/
for(i = 0; a[i] != key; i++) { //0부터
;
}
return i == n ? -1 : i; //마지막 인덱스 n이면 -1, 중간에 break가 걸리면 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]; //요솟수 num+1로 배열 길이 만듦
for(int i = 0; i < num; i++) {
System.out.print("x[" + i + "] : ");
x[i] = scan.nextInt(); //배열에 값 입력
}
System.out.print("검색할 값: "); //키 값을 입력
int ky = scan.nextInt();
int idx = seqSearchSen(x, num, ky); //배열 x에서 값이 ky인 요소를 검색
if(idx == -1) { //마지막 인덱스 값까지 갔을 때 나타나면 -1이니까 그 전에는 못 찾은 것
System.out.println("그 값의 요소가 없습니다.");
} else { //중간에 break 걸리면 i
System.out.println(ky + "은(는) x[" + idx + "]에 있습니다.");
}
}
}선형 검색의 스캐닝 과정 상세 출력
package chap03_1;
import java.util.Scanner;
//선형 검색의 과정을 자세히 나타냄
public class Quiz2 {
//이 메서드에서는 선형 과정을 나타내는 프로그램을 출력
static int seqSearchEx(int[] a, int n, int key) { //길이가 n인 배열 a에서 key가 있는지 찾기
System.out.print(" |");
for(int i = 0; i < n; i++) {
System.out.printf("%4d", i); //4칸 안에서 숫자 넣기
}
System.out.println();
System.out.print("---+"); //4칸 기준이니까
for(int i = 0; i < 4 * n + 2; i++) { //-가 4칸*n씩 있고, 2번 더 넣기, 크게 중요x
System.out.print("-");
}
System.out.println();
for(int i = 0; i < n; i++) { //행(가로)
System.out.print(" |"); //맨 위에 하나 넣고
//String.format() - 문자열의 형식 설정
//%%%퍼센트, 정수(인덱스*4칸 하고 + 3), 문자열(공백), * 넣고, 다음 줄
//%%ds를 넣으면 %가 출력되어 나옴, %s
//""는 d에 들어가고, (i * 4) + 3)는 s에 들어감
System.out.printf(String.format("%%%ds*\n", (i * 4) + 3), "");
/*************************************************************/
//왼쪽에 인덱스 표시
System.out.printf("%3d|", i);
for(int j = 0; j < n; j++) { //열(세로)
System.out.printf("%4d", a[j]);
}
/*************************************************************/
System.out.println("\n |");
if(a[i] == key)
return i; //검색 성공, return i하면서 break 됨
}
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인 배열
for(int i = 0; i < num; i++) {
System.out.print("x[" + i + "]=");
x[i] = scan.nextInt();
}
System.out.print("찾는 값: ");
int ky = scan.nextInt();
int result = seqSearchEx(x, num, ky); //배열 x에서 값이 ky인 요소 검색하는 메서드 seqSearchEx 실행
if(result == -1)
System.out.println("찾는 값이 없습니다.");
else
System.out.println(ky + "는 " + "x[" + result + "]에 있습니다.");
}
}- String.format(): 해당 서식에 맞게 String 형식으로 반환하기 위해 사용
- %% = %를 의미함
다른 방법 (\t = tab, repeat() 사용)
이진 검색 - 시간 복잡도
static int seqSearch(int[] a, int n, int key) {
int pl = 0; //1번, 맨 앞의 인덱스
int pr = n - 1; //1번, 맨 뒤의 인덱스
do{
int pc = (pl + pr) / 2; //n번, 중앙 인덱스
if(a[pc] == key) //n번
return pc; //1번, 검색 성공
else if(a[pc] < key) //n번
pl = pc + 1; //n번, 검색 범위를 뒤족 반으로 좁힘
else
pr = pc - 1; //n번, 검색 범위를 앞쪽 반으로 좁힘
} while(pc <= pr); //n번
return -1; //1번, 검색 실패
}- 이진 검색 알고리즘의 복잡도 = O(1)+O(1)+O(log n)+O(log n)+O(1)+O(log n)+...+O(1) = O(log n)
- O(n)과 O(log n)은 O(1)보다 큼
이진 검색의 스캐닝 과정 상세 출력
package chap03_1;
import java.util.Arrays;
import java.util.Scanner;
public class Quiz4 {
static int binSearchEx(int[] a, int n, int key) {
System.out.print(" |");
for(int i = 0; i < n; i++) {
System.out.printf("%4d", i);
}
System.out.println(); //맨 윗줄 끝
System.out.print("---+");
for(int i = 0; i < 4*n + 2; i++) {
System.out.print("-");
}
System.out.println(); //두번째 줄 끝
int pl = 0; //인덱스 맨 앞
int pr = n-1; //인덱스 맨 뒤
//pl, pr, pc로 무한반복문을 만들어야 하기 때문에 do ~ while, while 사용
do {
int pc = (pl + pr) / 2; //인덱스 중앙
System.out.println("pc는: " + pc); //배열의 길이가 2이면 중앙값은 0임
//3줄 1세트 만들기
//첫번째줄
System.out.print(" |");
//<- + 까지 만들기
if(pl != pc) //맨 앞 인덱스와 중앙 인덱스가 같지 않으면, 3개 이상인 경우
System.out.printf(String.format("%%%ds<-%%%ds+", (pl*4)+1, (pc-pl)*4), "", "");
else //pl == pc이면, 2개인 경우
System.out.printf(String.format("%%%ds<-+", pc * 4 + 1), "");
// -> 만들기
if(pc != pr) //중앙 인덱스와 맨 뒤 인덱스가 같지 않으면
System.out.printf(String.format("%%%ds->\n", (pr - pc)*4 -2), "");
else
System.out.println("->");
//두번째 줄
System.out.printf("%3d|", pc); //맨 왼쪽에 현재 검색하고 있는 요소의 인덱스 값 표시
for(int i = 0; i < n; i++) {
System.out.printf("%4d", a[i]); //인덱스 값 넣기
}
//세번쨰 줄
System.out.println("\n |");
//이진 검색
if(a[pc] == key) //중앙 인덱스 값이 key이면 key 반환
return pc;
else if(a[pc] < key) //중앙 인덱스 값이 key보다 작으면
pl = pc + 1; //시작 값을 중앙인덱스+1 부터 시작하게 업데이트
else //중앙 인덱스 값이 key보다 크면
pr = pc - 1;
} while (pl <= pr); //맨 앞 인덱스가 맨 뒤 인덱스보다 커지지 않을때까지 계속 반복
//그 사이에 중앙값이 key값으로 나오면 그 값을 return하고 없으면 -1(검색 실패) return
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인 배열
for(int i = 0; i < num; i++) {
System.out.print("x[" + i + "] = ");
x[i] = scan.nextInt();
}
Arrays.sort(x); //오름차순 정렬
System.out.println(Arrays.toString(x));
System.out.print("찾는값: ");
int ky = scan.nextInt();
int result = binSearchEx(x, num, ky);
if(result == -1)
System.out.println("찾는 값이 없습니다.");
else
System.out.println(ky + "는 x[" + result + "]에 있습니다.");
}
}- 배열의 길이가 2이면 중앙값은 0임
이진 검색 - 맨 앞의 요소를 찾는 메서드
- 이진 검색은 검색할 값과 같은 값을 갖는 요소가 하나 이상일 경우 그 요소 중에서 맨 앞의 요소를 찾지 못함
1. 검색이 성공했을 경우
2. 그 위치로부터 앞쪽으로 하나씩 검사 (배열의 맨 앞을 넘지 않는 범위에서)
package chap03_1;
import java.util.Arrays;
import java.util.Scanner;
public class Quiz5 {
//이진 검색으로 맨 앞의 요소를 찾는 메서드
static int binSearchX(int[] a, int n, int key) {
int pl = 0; //처음 인덱스
int pr = n-1; //맨 뒤 인덱스
while(pl <= pr) { //맨 뒤 인덱스가 처음 인덱스보다 커지면 break
int pc = (pl + pr) / 2; //중앙 인덱스
if(a[pc] == key) { //1. 검색 성공했을 때
for(int i = pc; i >= 0; i--) { //2.그 위치부터 맨 앞으로 이동하면서
if(a[i] == a[pc]) { //3. 가장 앞쪽의 인덱스 찾기, 같은 값이 있으면
pc = i; //4. 그 인덱스 값을 pc에 넣고
}
}
return pc; //맨 앞쪽까지 다 확인 후 pc 반환
} else if(a[pc] < key) {
pl = pc + 1;
} else if(a[pc] > key) {
pr = pc - 1;
}
}
return -1; //검색 실패
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.print("요솟수: ");
int num = scan.nextInt();
int[] a = new int[num];
for(int i = 0; i < num; i++) {
System.out.print("a[" + i + "] =");
a[i] = scan.nextInt();
}
Arrays.sort(a); //오름차순 정렬
System.out.print("찾는값: ");
int ky = scan.nextInt();
int result = binSearchX(a, num, ky);
if(result == -1)
System.out.println("찾는값이 없습니다.");
else
System.out.println(ky + " 는 a[" + result + "]에 있습니다.");
}
}Arrays.binarySearch
- 이진 검색을 하는 메서드를 표준 라이브러리로 제공
- 가정: 오름차순으로 정렬된 배열 a, 키 값이 key인 요소
- 자료형에 따라 9가지 방법으로 오버로딩 (같은 메서드 이름, 매개변수 다름)
import java.util.Arrays;
public class binarySearch {
public static void main(String[] args) {
int[] x = {1, 2, 6, 32, 3};
//binarySearch 메서드는 오름차순 정렬을 가정하므로 sort 필요
Arrays.sort(x); //[1, 2, 3, 6, 32]
int result = Arrays.binarySearch(x, 3);
System.out.println(result); //인덱스 값: 2 반환
}1. 검색 성공
- key와 일치하는 요소의 인덱스 반환
- 일치하는 요소가 여러개 ▶ 무작위의 인덱스 반환
2. 검색 실패
- 삽입 포인트 = key보다 큰 요소 중 첫번째 요소의 인덱스
배열의 모든 요소가 key보다 작으면 배열의 길이가 삽입 포인트가 됨 - 삽입 포인트 x ▶ -x -1 반환
binarySearch 메서드 - 기본 자료형 배열
package chap03_1;
import java.util.Arrays;
import java.util.Scanner;
public class BinarySearchTester {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.print("요솟수: ");
int num = scan.nextInt();
int[] x = new int[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 result = Arrays.binarySearch(x, ky); //메서드 사용하여 인덱스값 찾기
if(result < 0) {//검색 실패
System.out.println("찾을 수 없습니다.");
//삽입 포인트의 값을 출력
int point = -result -1; //삽입포인트
System.out.printf("삽입포인트는 %d입니다\n", point);
}
else //검색 성공
System.out.println(ky + "은(는) x[" + result + "]에 있습니다.");
}
}binarySearch 메서드 - 객체의 배열에서 검색
static int binarySearch(Object[] a, Object key)- 자연 정렬이라는 방법으로 요소의 대소 관계 판단
- 정수 배열, 문자열 배열 등
static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)- 순서로 줄지어 있는 배열에서 검색할 때
- "자연 순서"를 논리적으로 갖지 않는 클래스 배열에서 검색할 때
자연 정렬
- natural ordering
자연 정렬되지 않은 배열
- 제너릭 메서드(generic method)으로 검색하면 됨
- 제너릭 메서드는 자료형에 구애받지 x
배열의 요소가 어떤 순서로 줄지어 있는지,
각 요소의 대소 관계를 어떻게 판단할 것인지에 대해서는
binarySearch 메서드에 알려줘야 함 ▶ 세 번째 매개변수 c에 전달
java.util.Comparator 인터페이스 - compare 메서드
2022.10.29 - [프로그래밍 언어/Java] - [Java] Comparable VS Comparator
[Java] Comparable VS Comparator
Comparable VS Comparator 둘 다 인터페이스(interface) 이므로 추상클래스를 반드시 구현해야 함 새로운 클래스 객체를 만들어 비교하려고 하면 비교할 기준이 필요 Comparable { } Java.lang 패키지 (import 필요X
j-won950101.tistory.com
comparator 실습
1. Comparator 인터페이스와 compare 메서드를 구현한 클래스 먼저 작성
2. 클래스의 인스턴스를 생성함, 이 인스턴스를 comparator라고 부름
3. binarySearch 메서드의 세 번째 매개변수로 클래스 X의 클래스 변수인 X.comparator를 전달하면 이진 검색 수행
package chap03_1;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class PhysExamSearch {
static class PhyscData {
//필드
private String name;
private int height;
private double vision;
//생성자
public PhyscData(String name, int height, double vision) {
super();
this.name = name;
this.height = height;
this.vision = vision;
}
@Override
public String toString() {
return "PhyscData [name=" + name + ", height=" + height + ", vision=" + vision + "]";
}
//오름차순으로 정렬하기 위한 comparator
public static final Comparator<PhyscData> HEIGHT_ORDER = new HeightOrderComparator();
private static class HeightOrderComparator implements Comparator<PhyscData> {
public int compare(PhyscData d1, PhyscData d2) {
return (d1.height > d2.height) ? 1 :
(d1.height < d2.height) ? -1 : 0;
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
PhyscData[] x = { //키의 오름차순으로 정렬되어 있음
new PhyscData("이나령", 162, 0.3),
new PhyscData("유지훈", 168, 0.4),
new PhyscData("김한결", 169, 0.8),
new PhyscData("홍준기", 171, 1.5),
new PhyscData("전서현", 173, 0.7),
new PhyscData("이호연", 174, 1.2),
new PhyscData("이수민", 175, 2.0),
};
System.out.print("몇 cm인 사람은 찾고 있나요?");
int height = scan.nextInt();
int result = Arrays.binarySearch(
x, //배열 x에서
new PhyscData("", height, 0.0), //키가 height인 요소를
PhyscData.HEIGHT_ORDER //HEIGHT_ORDER에 의해 검색
);
if(result < 0)
System.out.println("요소가 없습니다.");
else {
System.out.println("[x" + result + "]에 있습니다.");
System.out.println("찾은 데이터: " + x[result]);
}
}
}메서드
- 메서드가 인스턴스에 포함되어 있는지에 따라 달라짐
클래스 메서드
- 정적 메서드
- static
- 클래스 전체에 대한 처리를 담당
- 인스턴스 메서드와 처리 영역을 구분하기 위해 주로 사용
- 인스턴스에 포함되지 x
클래스 이름.메서드 이름
인스턴스 메서드
- 비정적 메서드
- 인스턴스에 포함
클래스형 변수 이름.메서드 이름
제네릭
class 클래스 이름 <파라미터1, 파라미터2, ...> { /* ... */ }
interface 인터페이스 이름 <파라미터1, 파라미터2, ...> { /* ... */ }- 처리해야 할 대상의 자료형에 의존하지 않는 클래스(인터페이스) 구현 방식
- 클래스 이름 바로 뒤에 <Type> 같은 형식의 파라미터를 붙여 선언
- 매개변수로 정의한 '자료형'을 전달받을 수 있음
작성법
1. 1개의 대문자 사용
2. 컬렉션(collection)의 자료형은 E(element)
3. 맵(Map)의 키(key), 값(value)은 K, V
4. 일반적으로 T 사용
와일드 카드
<? extends T> : 클래스 T의 서브 클래스를 전달받음
<? super T> : 클래스 T의 슈퍼 클래스를 전달받음
728x90
'Study > Data Structure&Algorithm' 카테고리의 다른 글
| [자료구조&알고리즘] 재귀 알고리즘(팩토리얼, 유클리드 호제법), 하노이의 탑, N퀸 문제 ??? (0) | 2023.05.08 |
|---|---|
| [자료구조&알고리즘] stack(스택), queue(큐) (0) | 2023.05.07 |
| [알고리즘] 유클리드 호제법 (Euclidean algorithm), 약수, 배수 (0) | 2023.04.25 |
| [자료구조&알고리즘] 기본 자료구조(배열, 클래스) (0) | 2023.04.18 |
| [자료구조&알고리즘] 기본 알고리즘(알고리즘, 반복) (0) | 2023.04.09 |
