데이터 집합에서 원하는 값을 가진 요소를 찾아내는 검색 알고리즘을 알아보자.
검색 알고리즘이란?
검색 알고리즘은 주어진 데이터 집합에서 특정 값을 찾는 과정을 수행하는 알고리즘입니다.
일반적으로 데이터가 정렬되어 있는 경우와 그렇지 않은 경우에 따라 다른 알고리즘이 사용됩니다.
검색 알고리즘은 다양한 방법으로 구현될 수 있으며, 효율성과 정확성을 고려하여 선택됩니다.
일반적으로 사용되는 검색 알고리즘으로는 선형 검색(Linear Search), 이진 검색(Binary Search), 해시 검색(Hash Search) 등이 있습니다.
선형 검색(Linear Search): 데이터를 처음부터 끝까지 순차적으로 탐색하여 원하는 값을 찾는 알고리즘입니다. 데이터가 정렬되어 있지 않은 경우에도 사용할 수 있지만, 데이터의 크기가 클 경우 비효율적일 수 있습니다.
이진 검색(Binary Search): 데이터가 정렬된 상태에서 사용하는 검색 알고리즘으로, 중간 위치의 값을 기준으로 탐색 범위를 반으로 줄여가며 값을 찾아나갑니다. 데이터가 정렬되어 있어야만 사용할 수 있으며, 탐색 속도가 빠르고 효율적입니다.
해시 검색(Hash Search): 해시 함수를 사용하여 데이터를 특정 인덱스에 매핑한 뒤, 해당 인덱스에서 원하는 값을 찾는 알고리즘입니다. 해시 테이블을 사용하여 데이터를 저장하고 검색하는 방식으로, 매우 빠른 검색 속도를 가지고 있습니다.
- 체인법: 같은 해시값의 데이터를 선형 리스트로 연결하는 방법
- 오픈 주소법: 데이터를 위한 해시값이 충돌할 때 재해시 하는 방법
이외에도 트리 검색(Tree Search), 그래프 검색(Graph Search) 등 다양한 검색 알고리즘이 존재합니다.
알고리즘 선택은 데이터의 특성과 크기, 검색 시간 요구 등을 고려하여 이루어져야 합니다.
선형 검색.
선형 검색(Linear Search)은 가장 간단한 검색 알고리즘 중 하나로,
주어진 데이터 집합에서 원하는 값을 찾기 위해 처음부터 끝까지 순차적으로 탐색하는 방법입니다.
선형 검색은 다음과 같은 단계로 이루어집니다:
데이터 집합의 첫 번째 요소부터 시작합니다.
현재 요소와 찾고자 하는 값을 비교합니다.
값이 일치하면 해당 요소를 찾았으므로 검색을 종료합니다.
값이 일치하지 않으면 다음 요소로 이동하여 비교를 반복합니다.
데이터 집합의 끝까지 탐색했는데도 일치하는 값이 없으면 찾고자 하는 값은 데이터에 존재하지 않는 것입니다.
선형 검색은 데이터가 정렬되어 있지 않거나 검색할 데이터의 위치가 예측되지 않을 때 유용합니다.
하지만 데이터 크기가 매우 크거나 검색해야 할 위치가 불규칙하게 분포되어 있는 경우 성능이 좋지 않을 수 있습니다.
선형 검색에서 배열 검색의 종료 조건은 2개이다. 성공 또는 실패.
배열 요솟수가 n개 일 때 종료 조건을 판단하는 횟수는 평균 n / 2회
길이가 n인 배열 arr에서 값이 key인 요소를 검색하는 코드.
int i = 0;
while (true) {
if (i == n) {
return -1;
}
if (arr[i] == key) {
return i;
}
i++;
}package june2023.day08.datastructure;
import java.util.Scanner;
class Solution {
static int seqSearch(int[] arr, int n, int key) {
int i = 0;
while (true) {
if (i == n) {
return -1;
}
if (arr[i] == key) {
return i;
}
i++;
}
}
}
public class DataStructureTest {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("배열의 길이를 입력하세요.");
int num = sc.nextInt();
int[] arr = new int[num];
System.out.println("배열의 갯수" + num + "만큼 입력하세요.");
for (int i = 0; i < num; i++) {
System.out.println(i + 1 + "번째");
arr[i] = sc.nextInt();
}
// find Value
System.out.println("찾을 값 입력하세요.");
int key = sc.nextInt();
int idx = Solution.seqSearch(arr, num, key);
if (idx == -1) {
System.out.println("일치하는 값이 없습니다.");
} else {
System.out.println("일치하는 값은 " + arr[idx] + " 입니다.");
}
}
}
보초법으로 선형 검색 구현하기.
보초법(Sentinel Search)은 선형 검색에서 조금 더 효율적인 방법입니다.
일반적인 선형 검색에서는 모든 요소를 비교해야 하는데 반해, 보초법은 검색하고자 하는 값을
배열의 마지막에 추가하여 검색 반복문에서의 조건을 줄이는 방법입니다.
보초법을 사용한 선형 검색은 다음과 같은 단계로 이루어집니다:
검색하고자 하는 값을 배열의 마지막 요소로 설정합니다.
배열의 첫 번째 요소부터 시작합니다.
현재 요소와 찾고자 하는 값을 비교합니다.
값이 일치하면 해당 요소를 찾았으므로 검색을 종료합니다.
값이 일치하지 않으면 다음 요소로 이동하여 비교를 반복합니다.
배열의 마지막 요소까지 탐색했는데도 일치하는 값이 없으면 찾고자 하는 값은 데이터에 존재하지 않는 것입니다.
보초법을 사용하면 검색 반복문에서 값을 비교하는 조건을 하나 줄일 수 있기 때문에 약간의 성능 향상을 기대할 수 있습니다.
import java.util.Scanner;
public class SeqSearchTest {
static int searchKey(int[] arr, int n, int key) {
int i = 0;
arr[n] = key; // 보초를 추가 한다.
while (true) {
if (arr[i] == key) {
break;
}
i++;
}
return i == n ? -1 : i;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("배열의 길이를 입력하세요.");
int num = sc.nextInt();
int[] arr = new int[num + 1];
System.out.println(arr.length);
System.out.println("배열의 갯수" + num + "만큼 입력하세요.");
for (int i = 0; i < num; i++) {
System.out.println(i + 1 + "번째");
arr[i] = sc.nextInt();
}
// find Value
System.out.println("찾을 값 입력하세요.");
int key = sc.nextInt();
int idx = Solution.seqSearch(arr, num, key);
if (idx == -1) {
System.out.println("일치하는 값이 없습니다.");
} else {
System.out.println("일치하는 값은 " + arr[idx] + " 입니다.");
}
}
}
이진 검색.
이진 검색(Binary Search)은 정렬된 배열에서 특정 값(타겟)을 찾는 검색 알고리즘입니다.
이진 검색은 배열을 중간 요소를 기준으로 반복적으로 탐색하여 찾고자 하는 값의 위치를 찾아냅니다.
이진 검색은 탐색 범위를 반으로 줄여가면서 빠르게 값을 찾을 수 있는 장점이 있습니다.
이진 검색은 다음과 같은 단계로 이루어집니다:
배열의 중간 요소를 선택합니다.
중간 요소와 타겟 값을 비교합니다.
타겟 값이 중간 요소보다 작으면, 중간 요소의 왼쪽 절반을 새로운 탐색 범위로 설정합니다.
타겟 값이 중간 요소보다 크면, 중간 요소의 오른쪽 절반을 새로운 탐색 범위로 설정합니다.
타겟 값이 중간 요소와 일치하면, 값을 찾았으므로 검색을 종료합니다.
탐색 범위를 반으로 줄여가며 위 단계를 반복합니다.
탐색 범위가 더 이상 줄어들지 않고, 값을 찾지 못한 경우 타겟 값은 배열에 존재하지 않는 것입니다.
이진 검색은 배열이 정렬되어 있어야만 적용할 수 있는 검색 알고리즘입니다.
배열이 정렬되어 있지 않은 경우에는 이진 검색을 사용할 수 없습니다.
이진 검색 알아보기.
배열이 오름차순 또는 내림차순으로 정렬되어 있을 때
중간 값을 key 값과 비교해 오른쪽 또는 왼쪽으로 갈지 비교하는 방식
package june2023.day08.datastructure;
import java.awt.*;
import java.util.Scanner;
public class BinarySearchTest {
static int search(int[] arr, int n, int key) {
int left = 0;
int right = n - 1;
do {
int mid = (left + right) / 2;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
left = mid + 1; // 찾는 값보다 중간 값이 크다면 검색 범위을 뒤쪽으로 보냄
} else {
right = mid - 1; // 찾는 값보다 중간 값이 작다면 검색 범위을 앞쪽으로 보냄
}
} while (left <= right);
return - 1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = 5;
int[] arr = new int[n];
System.out.println("1번쨰 값을 입력하세요:");
arr[0] = sc.nextInt();
for (int i = 1; i < n; i++) {
do {
System.out.println(i + 1 + "번쨰 값을 입력하세요:");
arr[i] = sc.nextInt();
} while (arr[i] < arr[i - 1]);
}
System.out.println("찾을 값 입력");
int key = sc.nextInt();
int idx = search(arr, n, key);
if (idx == -1) {
System.out.println("요소 없다.");
} else {
System.out.println("찾는 값은 " + arr[idx] + " 입니다.");
}
}
}
복잡도 구하기.
프로그램의 실행 속도는 프로그램이 동작하는 하드웨어나 컴파일러 등의 조건에 따라 달라집니다.
알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도(complecity)라고 합니다.
- 시간 복잡도(time complecity) : 실행에 필요한 시간을 평가한 것
- 공간 복잡도(space complecity) : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것
선형 검색의 시간 복잡도.
1. int i = 0;
2. while (i < n) {
3. if (arr[i] == key) {
4. return i; // 검색 성공!
}
5. i++;
}
6. return - 1; // 검색 실패!
| 단계 | 실행횟수 | 복잡도 |
| 1 | 1 | O(1) |
| 2 | n / 2 | O(n) |
| 3 | n / 2 | O(n) |
| 4 | 1 | O(1) |
| 5 | n / 2 | O(n) |
| 6 | 1 | O(1) |
n이 점점 커지면 O(n)에 필요한 계산 시간은 n에 비례하여 점점 길어진다.
2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차수가 더 높은 쪽의 복잡도가 지배한다.
그래서 선형 검색 알고리즘은 O(n)이다.
이진 검색의 시간 복잡도.
static int search(int[] arr, int n, int key) {
1. int left = 0; // 검색 범위 첫 인덱스
2. int right = n - 1; // 검색 범위 끝 인덱스
do {
3. int mid = (left + right) / 2; // 중앙 값 인덱스
4. if (arr[mid] == key) {
5. return mid; // 검색 성공
6. } else if (arr[mid] < key) {
7. left = mid + 1; // 범위를 절반으로 줄임
} else {
8. right = mid - 1; // 범위를 절반으로 줄임
}
9. } while (left <= right);
10. return - 1; // 실패
}| 단계 | 실행 횟수 | 복잡도 |
| 1 | 1 | O(1) |
| 2 | 1 | O(1) |
| 3 | log n | O(log n) |
| 4 | log n | O(log n) |
| 5 | 1 | O(1) |
| 6 | log n | O(log n) |
| 7 | log n | O(log n) |
| 8 | log n | O(log n) |
| 9 | log n | O(log n) |
| 10 | 1 | O(1) |
이진 검색법에서는 검색할 요소의 범위가 거의 절반씩 줄어들기 때문에 최대 시간복잡도로 해도 O(log n)이다.
O(n)과 O(log n)은 O(1)보다 크며 그림으로 나타내면 아래와 같다.
Arrays.binarySearch 사용해 이진 검색하기.
import java.util.Arrays;
public class ArrayBinarySearchTest {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int key = 9;
int idx = Arrays.binarySearch(arr, key);
System.out.println(idx); // 8
System.out.println(arr[idx]); // 9
// 값이 없을 때는 -배열길이 -1;
key = 33;
idx = Arrays.binarySearch(arr, key);
System.out.println(idx); // -11 ( -length - 1)
int arr1[] = {1, 2, 3, 4, 5};
idx = Arrays.binarySearch(arr1, 6);
System.out.println(idx); // -6 (-length - 1)
}
}
'BACKEND > Data Structure & Algorithm' 카테고리의 다른 글
| 재귀 알고리즘 기초 이해하기 (0) | 2023.06.16 |
|---|---|
| 스택과 큐 - 스택이란? (0) | 2023.06.11 |
| 기본 자료구조 - 배열이란 (0) | 2023.06.06 |
| 기초수학 - 조합(Combination) (3) | 2023.06.04 |
| 기초수학 - 순열(Permutation) (0) | 2023.06.03 |