선형검색 , 이진 검색 , 해시법

Notice

Recent Posts

Recent Comments

Link

« 2024/11 »
일	월	화	수	목	금	토
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30

Tags more

Archives

Today

Total

관리 메뉴

영권's

선형검색 , 이진 검색 , 해시법 본문

컴퓨터 공학/자료구조

선형검색 , 이진 검색 , 해시법

ykkkk 2020. 10. 13. 17:39

1. 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행합니다.

2. 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행합니다.

3. 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행합니다.

· 체인법 : 같은 해시값의 데이터를 선형 리스트로 연결하는 방법

· 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시 하는 방법

1. 선형 검색

선형 검색이란

요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키값을 갖는 요소를 안날 때까지 맨앞부터 순서대로 요소를 검색하면 되는데 이것이 선형 검색(linear search) 또는 순차 검색(sequential search)이라는 알고리즘입니다.

위 그림에서 선형 검색은 다음과 같은 순서로 진행 됩니다.

첫 번째 요소 6을 선택합니다. 원하는 값이 아닙니다.
두 번째 요소 4를 선택합니다. 원하는 값이 아닙니다.
세 번째 요소 3을 선택합니다. 원하는 값이 아닙니다.
네 번쨰 요소 2를 선택합니다. 원하는 값입니다.(검색 성공)

이 경우 검색에 성공한 경우 입니다. 하지만 키 값과 같은 값을 가진 요소가 배열에 없을 수도 있습니다.

위 그림은 검색 실패를 한경우 입니다.

검색 성공일 때와 실패일 때를 보면 검색의 종료 조건은 2가지인 것을 알 수 있습니다.

다음 조건 중 하나라도 성립하면 검색을 종료합니다.

조건 ① 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 (검색 실패)

조건 ② 검색할 값과 같은 요소를 발견한 경우 (검색 성공)

배열의 요솟수가 n개일때, 조건 1,2를 판단하는 횟수는 평균 n/2회 입니다.

선형 검색 코드 예제

import java.util.Scanner;
// 선형 검색

class SeqSearch {
	// 배열 a의 앞쪽 n개의 요소에서 key와 같은 요소를 선형 검색 
	static int seqSearch(int[] a, int key) {
		int i = 0;

		while (true) {
			if (i == a.length)
				return -1;		// 검색 실패!(-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];		// 요솟수가 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, ky);	// 배열x에서 키 값이 ky인 요소를 검색

		if (idx == -1)
			System.out.println("그 값의 요소가 없습니다.");
		else
			System.out.println(ky+"은(는) x[" + idx + "]에 있습니다.");
	}
}

보초법

선형검색은 반복할 때마다 종료조건 1과 2를 모두 판단합니다.

단순한 판단이라고 생각할 수 있겠지만 '타끌 모아 태산'이라는 말이 있듯이 종료 조건을 검사하는 비용은 결코 무시할 수 없습니다.

이 비용을 반으로 줄이는 방법이 보초법 입니다.

위 그림에서 0~6번 인덱스에 해당하는 값은 초기에 준비해 놓은 상태 입니다.

검색하기 전 검색하고자 하는 키 값을 맨 끝 요소( a[7] )에 저장합니다.

이때 저장하는 값을 보초(sentinel) 이라고 합니다.

그러면 b처럼 원하는 값이 원래의 데이터에 존재하지 않아도 보초인 a[7] 까지 검색하면 종료 조건②가 성립합니다.

이렇게 하면 원하는 키 값을 찾지 못했을 때를 판단하는 종료 조건①이 없어도 되고 보초는 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 합니다.

보초법을 적용한 선형 검색 코드 예제

import java.util.Scanner;
// 선형 검색(보초법)

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;
	}

	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];				// 요솟수 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);		// 배열x에서 값이 ky인 요소를 검색

		if (idx == -1)
			System.out.println("그 값의 요소가 없습니다.");
		else
			System.out.println(ky+"은(는) x[" + idx + "]에 있습니다.");
	}
}

if (i == a.length)
return -1; // 검색 실패!(-1을 반환)
if (a[i] == key)
return i; // 검색 성공!(인덱스를 반환)

에서

if (a[i] == key) // 검색 성공!
break;

반복문안에 판단 횟수가 절반으로 줄어듭니다.

선형 검색의 시간 복잡도 = O(n)

2. 이진 검색

이진검색이란

요소가 오름차순 또는 내림차순으로 정렬된 상태에서 검색하는 알고리즘으로 선형검색보다 더 빠르게 검색할 수 있는 장점이 있습니다.

위 그림처럼 정렬된 데이터에서 39를 검색하는 과정을 보겠습니다.

먼저 배열의 중앙에 위치한 요소인 a[5](31) 부터 검색을 시작합니다.

검색하려는 값인 39가 중앙 요소 31보다 큰 값입니다.

그러므로 검색 대상을 뒤 쪽의 (a[6]~a[10])으로 줄일 수 있습니다.

다음 검색 범위의 중앙에 위치한 a[8](68)을 확인 후 검색 값 39 보다 큰 값이므로 검색 범위를 a[6] ~ a[7]로 줄일 수 있습니다.

이제 검색 대상이 2개이기 떄문에 아거나 선택해도 되지만 앞쪽의 값 39을 선택하여 원하는 값인지 확인합니다.

39는 검색하려는 값이기 때문에 검색 성공입니다.

이진검색 알고리즘의 종료조건

종료조건 ① 검색대상과 key값이 일치하는 경우

종료조건 ② 검색 범위가 더이상 없는 경우

이진 검색은 검색을 반복할 때마다 검색 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균 값은 log n 입니다.

검색에 실패한 경우는 [log(n+1)] 회 , 검색에 성공한 경우는 약 log n -1 회 입니다.

또한 이진 검색 알고리즘은 검색 대상(배열)이 정렬되어 있음을 가정합니다.

이진 검색 예제 코드

import java.util.Scanner;
// 이진 검색 

class BinSearch {
	// 요솟수가 n인 배열 a에서 key와 같은 요소를 이진 검색합니다.
	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];				// 요솟수가 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);	// 배열x에서 값이 ky인 요소를 검색

		if (idx == -1)
			System.out.println("그 값의 요소가 없습니다.");
		else
			System.out.println(ky+"은(는) x[" + idx + "]에 있습니다.");
	}
}

이진 검색의 시간 복잡도 = O(log n)

3. 해시법

해시법은 데이터를 저장할 위치를 간단한 연산으로 구하는 것이다. 게다가 추가, 삭제도 효율적으로 수행할 수 있다.
배치하고자 하는 배열의 길이가 13일 때, data들의 index는 data%13이 된다. 그럼 삽입 삭제가 용이하다.
이렇게 index를 계산하는 과정을 해시 함수(hash function)이라고 한다. 해시 테이블의 각 요소(인덱스들)를 버킷(bucket)이라고 한다.

배열의 키 값(각 요소의 값)을 배열의 요솟수로 나눈 나머지를 표에 정리한 값을 해시 값(hash value)이라고 하며, 이 해시 값은 데이터에 접근할 때 사용한다.

해시 검색과정)

1) 해시 함수가 키 값을 해시 값으로 변환

2) 해시 값을 인덱스로 하는 버킷을 선택

3) 선택한 버킷의 연결 리스트를 처음부터 순서대로 검색. 키 값과 같은 값을 찾으면 검색 성공. 끝까지 스캔하여 찾지 못하면 검색 실패

요소 추가과정)

1) 해시 함수가 키 값을 해시 값으로 변환

2) 해시 값을 인덱스로 하는 버킷을 선택

3) 버킷이 가리키는 연결 리스트를 처음부터 순서대로 검색. 키 값과 같은 값을 찾으면 키 값이 이미 등록된 상태이므로 추가에 실패. 끝까지 스캔하여 찾지 못하면 리스트의 맨 앞 위치에 노드를 삽입.

요소 삭제과정)

1) 해시 함수가 키 값을 해시 값으로 변환

2) 해시 값을 인덱스로 하는 버킷을 선택

3) 버킷이 가리키는 연결 리스트를 처음부터 순서대로 검색. 키 값과 같은 값을 찾으면 그 노드를 리스트에 삭제. 그렇지 않다면 삭제에 실패

충돌

나머지가 서로 같은 수들은 반드시 존재한다. 따라서 버킷이 중복될 수 밖에없는데 이를 충돌(collision)이라고 한다.
충돌에 대한 대처는 다음과 같다.
1. 체인법 : 같은 해시 값을 갖는 요소를 연결 리스트로 관리한다.
2. 오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복한다.

체인법

- 체인법은 같은 해시 값을 갖는 데이터를 연결 리스트에 의해 사슬 모양으로 연결하는 방법이다. 따라서 배열(해시 테이블)의 각 버킷에 저장하는 값은 연결 리스트의 첫번째 노드에 대한 포인터이다.

2. 오픈 주소법

- 충돌이 발생했을 때 재해시(rehashing)를 수행하여 비어 있는 버킷을 찾아내는 방법

- 재해시를 여러번 반복하므로 선형 탐사법(linear probing)이라고도 함

검색과정)

1) 같은 해시 값의 데이터가 다른 버킷에 저장되어 있으면 재해싱해서 원하는 값을 찾을 때까지 재해시를 반복

참고 :

Do it 자료구조와 함께 배우는 알고리즘 입문 자바편(도서)

velog.io/@ghj7138/%ED%95%B4%EC%8B%9C%EB%B2%95-C#%EC%B2%B4%EC%9D%B8%EB%B2%95

kururu.tistory.com/66

'컴퓨터 공학 > 자료구조' 카테고리의 다른 글

정렬2 (단순 삽입 정렬, 병합 정렬) (0)	2020.10.29
정렬 1 (선택 정렬, 버블 정렬) (0)	2020.10.28
그래프 (0)	2020.10.21
트리(Tree) (0)	2020.10.17
스택(Stack) , 큐(Queue) (0)	2020.10.15