검색 알고리즘
검색과 키
어떤 검색을 하게 되더라도 특정 항목에 주목한다는 점은 검색하기의 공통점이다. 그 주목하는 항목을 키라고 한다. 키는 전체 데이터의 일부로, 검색 대상을 찾아내기 위해 주목하는 데이터를 말한다. 예를 들어, 여러 사람들 중 국적인 한국인 사람을 검색한다고 할 때, 국적이 키이고, 키 값은 한국이다. 또한 찾고자하는 키값과 일치하는 사람이 조건이며, 이런 조건은 꼭 하나만 있는 것은 아니고, 논리 곱이나 논리 합을 사용하여 복합 지정하기도 한다.
배열에서 검색하기
배열을 검색하는 예시로 다음 세가지 검색 기법을 제시한다. 이 중 몇몇은 자료구조에 의존한다.
우리는 이 장에서 배열 검색을 학습하며 다음의 알고리즘을 활용한다.
- 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색 수행
- 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색 수행
- 해시법 : 추가 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색
- 체인법 : 같은 해시값의 데이터를 선형 리스트로 연결
- 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시
선형 검색
선형 검색 (순차 검색)
직선 모양으로 늘어선 배열에에서 원하는 키값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색
종료조건
- 검색할 값과 같은 요소를 발견한 경우 -> 검색 성공
- 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 -> 검색 실패
선형 검색의 시간 복잡도에 대해서는 다음 글 <순차 탐색의 시간복잡도>을 참고하면 좋다.
실습 3-1
import java.util.Scanner;
public class SeqSearch {
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++;
}
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.print("요솟수: ");
int num = stdIn.nextInt();
int[] x = new int[num];
for (int i = 0; i < num; i++) {
System.out.print("x[" + i + "]: ");
x[i] = stdIn.nextInt();
}
System.out.print("검색할 값: ");
int ky = stdIn.nextInt();
int idx = seqSearch(x, num, ky);
if (idx == -1)
System.out.println("그 값의 요소가 없습니다.");
else
System.out.println(ky + "은(는) x["+ idx + "]에 있습니다.");
}
}SeqSearch는 배열 a의 처음부터 끝까지 n개의 요소를 대상으로 값이 key인 요소를 선형 검색 후 검색한 요소의 인덱스를 반환한다. key인 요소가 여러개 존재하면 반환값은 검색 과정에서 처음 발견한 요소의 인덱스가 된다. 값이 key인 요소가 없으면 -1을 반환한다.
탐색하는 인덱스를 바꿀 때마다 다음 조건문을 실행한다.
- i == n => -1 반환
- a[i] == key => i 반환
이때 배열의 검색을 while문이 아니라 for 문으로 구현하면 프로그램이 훨씬 간결해진다.
static int seqSearchFor(int[] a, int n, int key) {
for (int i = 0; i < n; i++)
if (a[i] == key)
return i;
return -1;
}선형 검색은 배열에서 순서대로 입력하는 유일한 방법이다.
보초법
선형 검색은 반복할 때마다 위에서 언급한 두 조건을 모두 판단한다. 종료조건을 모두 검사하는 이 비용을 반으로 줄이는 방법이 보초법이다.
보초법은 검색할 배열의 가장 끝에 검색할 값을 보초처럼 세워둠으로써 원래 배열에서 원하는 값을 찾지 못하면 미리 마지막에 세워둔 인덱스에서 멈추게한다. 이를 통해 배열 안에서 무조건 원하는 값을 찾게 한 후, 반복문을 나왔을 때 인덱스의 값이 배열의 끝인지 아닌지를 확인하면 되므로, 더이상 i == n 조건은 실행할 필요가 없어진다. 이런 방식으로 조건을 2개에서 1개로 줄인다.
실습 3-3
import java.util.Scanner;
public class SeqSearchSen {
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 stdIn = new Scanner(System.in);
System.out.print("요솟수: ");
int num = stdIn.nextInt();
int[] x = new int[num + 1];
for (int i = 0; i < num; i++) {
System.out.print("x[" + i + "]: ");
x[i] = stdIn.nextInt();
}
System.out.print("검색할 값: ");
int ky = stdIn.nextInt();
int idx = seqSearchSen(x, num, ky);
if (idx == -1)
System.out.println("그 값의 요소가 없습니다.");
else
System.out.println(ky + "은(는) x["+ idx + "]에 있습니다.");
}
}이진 검색
이진 검색
요소가 오름차순 또는 내림차순으로 정렬된 배열에서만 검색할 수 있는 알고리즘이다. 이진 검색을 위해서는 맨앞 인덱스와 맨 끝 인덱스, 그리고 둘의 중앙 인덱스가 필요하다. 맨앞 인덱스부터 맨끝 인덱스까지가 검색 범위이며, 중앙 인덱스는 찾을 값과 비교하여 판단하는 대상이다.
처음에는 배열의 처음을 맨 앞 인덱스, 배열의 끝을 맨 끝 인덱스로 지정하고, 중앙값과 검색할 값을 비교한다.
- 중앙값 < 검색할 값 => 맨앞 인덱스 = 중앙값 + 1 (중앙값 + 1 ~ 배열의 끝)
- 중앙값 > 검색할 값 => 맨 끝 인덱스 = 중앙값 - 1 (배열의 처음 ~ 중앙값 - 1)
- 중앙값 = 검색할 값 => 중앙 인덱스 리턴
이렇게 맨 앞 인덱스와 맨 끝 인덱스를 조건에 따라 조정하여 중앙값을 검색할 값과 비교하는 과정을 맨앞 인덱스 <= 맨끝 인덱스 조건이 성립할 때까지 반복한다. 만약 배열에 검색할 값이 없으면, 끝에는 맨앞 인덱스가 맨 끝 인덱스보다 커져버리므로 반복문을 빠져나오게 된다.
이진 검색에 대한 시간 복잡도는 이 글 <이진 탐색과 시간 복잡도 분석 (Binary Search and its Time Complexity Analysis)>을 확인해보면 된다.
실습 3-4
import java.util.Scanner;
public class BinSearch {
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 stdIn = new Scanner(System.in);
System.out.print("요솟수: ");
int num = stdIn.nextInt();
int[] x = new int[num];
System.out.println("오름차순으로 입력하세요.");
System.out.print("x[0]: ");
x[0] = stdIn.nextInt();
for (int i = 1; i < num; i++) {
do {
System.out.print ("x[" + i + "]: ");
x[i] = stdIn.nextInt();
} while (x[i] < x[i - 1]);
}
System.out.print("검색할 값: ");
int ky = stdIn.nextInt();
int idx = binSearch(x, num, ky);
if (idx == - 1)
System.out.println("그 값의 요소가 없습니다.");
else
System.out.println(ky + "은(는) x[" + idx + "]에 있습니다.");
}
}복잡도(complexity)
프로그램의 실행 속도는 프로그램이 동작하는 하드웨어나 컴파일러 등의 조건에 따라 달라진다. 알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도라고 한다. 복잡도는 아래 주가지 요소를 갖는다.
- 시간 복잡도(time complexity) : 실행에 필요한 시간을 평가할 것
- 공간 복잡도(space complexity) : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것
컴퓨터에게 n/2과 n의 차이는 크지 않다. 따라서 굳이 O(n/2)이렇게 표현하지 않고 O(n)으로 표현한다. 알고리즘은 연속된 연산들로 이뤄져있는 데, 각 연산들의 복잡도 중 가장 큰 복잡도가 알고리즘의 복잡도가 된다.
연습문제
Q1. 실습 3-3의 seqSearchSen 메서드를 while문이 아니라 for 문을 사용하여 수정한 프로그램을 작성하세요.
import java.util.Scanner;
public class Q1 {
static int seqSearchSen(int[] a, int n, int key) {
for (int i = 0; i < n; i++)
if (a[i] == key)
return i;
return -1;
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.print("요솟수: ");
int num = stdIn.nextInt();
int[] x = new int[num + 1];
for (int i = 0; i < num; i++) {
System.out.print("x[" + i + "]: ");
x[i] = stdIn.nextInt();
}
System.out.print("검색할 값: ");
int ky = stdIn.nextInt();
int idx = seqSearchSen(x, num, ky);
if (idx == -1)
System.out.println("그 값의 요소가 없습니다.");
else
System.out.println(ky + "은(는) x["+ idx + "]에 있습니다.");
}
}Q2. 선형 검색의 스캐닝 과정을 상세하게 출력하는 프로그램을 작성하세요. 이때 각 행의 맨 왼쪽에 현재 검색하는 요소의 인덱스를 출력하고, 현재 검색하고 있는 요소를 위에 별표 기호 *를 출력하세요.
| 0 1 2 3 4 5 6
--+--------------
| *
0| 6 4 3 2 1 9 8
| *
1| 6 4 3 2 1 9 8
| *
2| 6 4 3 2 1 9 8
3은(는) x[2]에 있습니다.import java.util.Scanner;
public class Q2 {
static int seqSearchSen(int[] a, int n, int key) {
System.out.print(" |");
for (int i = 0; i < n; i++)
System.out.printf("%2d", i);
System.out.println();
System.out.print("--+");
for (int i = 0; i < n; i++)
System.out.print("--");
System.out.println();
for (int i = 0; i < n; i++) {
System.out.print(" | ");
for (int j = 0; j < i; j++)
System.out.print(" ");
System.out.println("*");
System.out.printf("%2d|", i);
for (int j = 0; j < n; j++)
System.out.printf("%2d", a[j]);
System.out.println();
if (a[i] == key)
return i;
}
return -1;
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.print("요솟수: ");
int num = stdIn.nextInt();
int[] x = new int[num + 1];
for (int i = 0; i < num; i++) {
System.out.print("x[" + i + "]: ");
x[i] = stdIn.nextInt();
}
System.out.print("검색할 값: ");
int ky = stdIn.nextInt();
int idx = seqSearchSen(x, num, ky);
if (idx == -1)
System.out.println("그 값의 요소가 없습니다.");
else
System.out.println(ky + "은(는) x["+ idx + "]에 있습니다.");
}
}이진 검색의 시간 복잡도
이진 검색법을 이용하면 검색할 요소의 범위를 절반씩 좁힐 수 있다. 프로그램의 각 단계 연산 들의 시간 복잡도의 최댓값은 O(log n)이다. 따라서 이진 검색의 시간 복잡도는 O(log n)이다.
연습문제
Q3. 요솟수가 n인 배열 a에서 key와 일치하는 모든 요소의 인덱스를 배열 idx의 맨 앞부터 순서대로 저장하고, 일치한 요솟수를 반환하는 메서드를 작성하세요. 예를 들어, 요솟수가 8인 배열 a의 요소가 {1, 9, 2, 9, 4, 6, 7, 9}이고 key가 9면 배열 idx에 {1, 3, 7}을 저장하고, 3을 반홥니다.
import java.util.Scanner;
public class Q3 {
static int searchIdx(int[] a, int n, int key, int[] idx) {
int count = 0;
for (int i = 0; i < n; i++) {
if (a[i] == key)
idx[count++] = i;
}
return count;
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.print("요솟수: ");
int num = stdIn.nextInt();
int[] x = new int[num];
for (int i = 0; i < num; i++) {
System.out.print("x[" + i + "]: ");
x[i] = stdIn.nextInt();
}
System.out.print("검색할 값: ");
int ky = stdIn.nextInt();
int[] idx = new int[num];
int count = searchIdx(x, num, ky, idx);
if (count == 0)
System.out.println("그 값의 요소가 없습니다.");
else
for (int i : idx)
System.out.print(i + " ");
}
}Q4. 오른쪽처럼 이진 검색의 과정을 자세히 출력하는 프로그램을 작성하세요. 각 행의 맨 왼쪽에 현재 검색하고 있는 요소의 인덱스를 출력하고, 검색 범위의 맨 앞 요소 위에 <-, 맨 끝 요소 위에 ->, 현재 검색하고 있는 중앙 요소 위에 +를 출력하도록 하세요.
| 0 1 2 3 4 5 6
--+--------------
|<- + ->
3| 1 2 3 5 6 8 9
|<- +->
1| 1 2 3 5 6 8 9
2은(는) x[1]에 있습니다.
import java.util.Scanner;
public class Q4 {
static int binSearchSen(int[] a, int n, int key) {
int pl = 0;
int pr = n - 1;
System.out.print(" |");
for (int i = 0; i < n; i++)
System.out.printf("%2d", i);
System.out.println();
System.out.print("--+");
for (int i = 0; i < n; i++)
System.out.print("--");
System.out.println();
do {
int pc = (pl + pr) / 2;
System.out.print(" |");
for (int i = 0; i < n; i++)
if (i == pc)
System.out.print(" +");
else if (i == pl)
System.out.print("<-");
else if (i == pr)
System.out.print("->");
else
System.out.print(" ");
System.out.println();
System.out.printf("%2d|", pc);
for (int j = 0; j < n; j++)
System.out.printf("%2d", a[j]);
System.out.println();
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 stdIn = new Scanner(System.in);
System.out.print("요솟수: ");
int num = stdIn.nextInt();
int[] x = new int[num + 1];
for (int i = 0; i < num; i++) {
System.out.print("x[" + i + "]: ");
x[i] = stdIn.nextInt();
}
System.out.print("검색할 값: ");
int ky = stdIn.nextInt();
int idx = binSearchSen(x, num, ky);
if (idx == -1)
System.out.println("그 값의 요소가 없습니다.");
else
System.out.println(ky + "은(는) x["+ idx + "]에 있습니다.");
}
}Q5. 우리가 살펴본 이진 검색 알고리즘 프로그램은 검색할 값과 같은 값을 갖는 요소가 하나 이상일 경우, 그 요소 중에서 맨 앞의 요소를 찾지 못합니다. 예를 들어, 아래 그림의 배열에서 7을 검색하면 중앙에 위치하는 a[5]를 검색합니다. 맨 앞의 요소를 찾는 binSearchX 메서드를 작성해보세요.
import java.util.Scanner;
public class Q5 {
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) {
int idx = pc;
while (a[idx] == key) {
idx--;
}
return idx + 1;
}
else if (a[pc] < key)
pl = pc + 1;
else
pr = pc - 1;
} while (pl <= pr);
return -1;
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.print("요솟수: ");
int num = stdIn.nextInt();
int[] x = new int[num];
System.out.println("오름차순으로 입력하세요.");
System.out.print("x[0]: ");
x[0] = stdIn.nextInt();
for (int i = 1; i < num; i++) {
do {
System.out.print ("x[" + i + "]: ");
x[i] = stdIn.nextInt();
} while (x[i] < x[i - 1]);
}
System.out.print("검색할 값: ");
int ky = stdIn.nextInt();
int idx = binSearch(x, num, ky);
if (idx == - 1)
System.out.println("그 값의 요소가 없습니다.");
else
System.out.println(ky + "은(는) x[" + idx + "]에 있습니다.");
}
}Array.binarySearch에 의한 이진 검색
Java는 배얄에서 이진 검색을 하는 메서드를 표존 라이브러리로 제공한다. 이진 검색 표준 라이브러리의 메서드 중 java.util.Arrays 클래스의 binarySearch 메서드가 있다. 이 메서드는 다음과 같은 장점이 있다.
- 이진 검색 메서드를 직접 작성할 필요가 없다.
- 모든 자료형 배열에서 검색할 수 있다.
실습 3-5
import java.util.Arrays;
import java.util.Scanner;
public class BinarySearchTester {
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.print("요솟수 : ");
int num = stdIn.nextInt();
int[] x = new int[num];
System.out.println("오름차순으로 입력하세요.");
System.out.print("x[0]: ");
x[0] = stdIn.nextInt();
for (int i = 1; i < num; i++) {
do {
System.out.print("x[" + i + "]: ");
x[i] = stdIn.nextInt();
} while (x[i] < x[i-1]);
}
System.out.print("검색할 값: ");
int ky = stdIn.nextInt();
int idx = Arrays.binarySearch(x, ky);
if (idx < 0)
System.out.println("그 값의 요소가 없습니다.");
else
System.out.println(ky + "은(는) x[" + idx + "]에 있습니다.");
}
}연습문제
Q6. 실습 3-5를 수정하여 검색에 실패하면 삽입 포인트의 값을 출력하는 프로그램을 작성하세요.
import java.util.Arrays;
import java.util.Scanner;
public class Q6 {
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.print("요솟수 : ");
int num = stdIn.nextInt();
int[] x = new int[num];
System.out.println("오름차순으로 입력하세요.");
System.out.print("x[0]: ");
x[0] = stdIn.nextInt();
for (int i = 1; i < num; i++) {
do {
System.out.print("x[" + i + "]: ");
x[i] = stdIn.nextInt();
} while (x[i] < x[i-1]);
}
System.out.print("검색할 값: ");
int ky = stdIn.nextInt();
int idx = Arrays.binarySearch(x, ky);
if (idx < 0)
System.out.println("삽입포인트 : " + (-idx - 1));
else
System.out.println(ky + "은(는) x[" + idx + "]에 있습니다.");
}
}실습 3C-1
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 IdTester {
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());
}
}
실습 3-6
import java.util.Arrays;
import java.util.Scanner;
public class StringBinarySearch {
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
String[] x = {
"abstract", "assert", "boolean", "break", "byte",
"case", "catch", "char", "class", "const", "continue",
"default", "do", "double", "else", "enum", "extends",
"final", "finally", "float", "for", "goto", "if"
};
String ky = stdIn.next();
int idx = Arrays.binarySearch(x, ky);
if (idx < 0)
System.out.println("해당 키워드가 없습니다.");
else
System.out.println("해당 키워드는 x[" + idx + "]에 있습니댜.");
}
}실습 3-7
import java.util.Comparator;
public class X {
public static final Comparator<X> COMPAROTOR = new Comp();
private static class Comp implements Comparator<X> {
@Override
public int compare(X o1, X o2) {
// TODO Auto-generated method stub
return 0;
}
}
}실습 3-8
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) {
this.name = name;
this.height = height;
this.vision = vision;
}
@Override
public String toString() {
return name + " " + height + " " + vision;
}
public static final Comparator<PhyscData> HEIGHT_ORDER
= new Comparator<>() {
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 stdIn = 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 = stdIn.nextInt();
int idx = Arrays.binarySearch(x, new PhyscData("", height, 0.0), PhyscData.HEIGHT_ORDER);
if (idx < 0)
System.out.println("요소가 없습니다.");
else {
System.out.println("x[" + idx + "]에 있습니다.");
System.out.println("찾은 데이터: " + x[idx]);
}
}
}연습문제
Q7. 시력에 대한 내림차순 정렬의 신체검사 데이터에서 특정 시력을 가진 사람을 검색하는 프로그램을 작성하세요.
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Q7 {
static class PhyscData {
String name;
int height;
double vision;
public PhyscData(String name, int height, double vision) {
this.name = name;
this.height = height;
this.vision = vision;
}
@Override
public String toString() {
return name + " " + height + " " + vision;
}
final static Comparator<PhyscData> VISION_ORDER = (d1, d2) -> {
return (d1.vision > d2.vision) ? 1 :
(d1.vision < d2.vision) ? -1 : 0;
};
}
public static void main(String[] args) {
Scanner stdIn = 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("시력이 몇인 사람을 찾고 있나요?: ");
double vision = stdIn.nextDouble();
int idx = Arrays.binarySearch(x, new PhyscData("", 0, vision), PhyscData.VISION_ORDER);
if (idx < 0)
System.out.println("요소가 없습니다.");
else {
System.out.println("x[" + idx + "]에 있습니다.");
System.out.println("찾은 데이터: " + x[idx]);
}
}
}
실습 3-7
public class GenericClassTester {
static class GenericClass<T> {
private T xyz;
GenericClass(T t) {
this.xyz = t;
}
T getXyz() {
return xyz;
}
public static void main(String[] args) {
GenericClass<String> s = new GenericClass<String>("ABC");
GenericClass<Integer> n = new GenericClass<Integer>(15);
System.out.println(s.getXyz());
System.out.println(n.getXyz());
}
}
}
'자바 자료구조 & 알고리즘 > Do it! 자료구조와 함께 배우는 알고리즘 입문 (자바편)' 카테고리의 다른 글
| Do it! 자료구조와 함께 배우는 알고리즘 입문 : 1장 기본 알고리즘 (1) | 2020.09.06 |
|---|
