검색(탐색) 알고리즘 이란 무엇인가?

▏목적

 

      ◦ 검색 알고리즘 이해하기   

 

 

 

 

▏시작하는 말

 

알고리즘 공부를 하기 위하여 프로그래머스 Lv 2문제들을 꾸준히 하루에 한 문제씩 풀어나가는 중이다. 나는 알고리즘을 따로 배워본 적 없이 JAVA의 기초 지식만 있었기 때문에 1 / 3 정도 풀고 나니 남은 문제들은 구현은 해도 효율성이 좋지 않거나 손쉽게 풀 수 없는 문제들만 남았다. 때문에 나는 제대로 된 알고리즘 개념부터 공부해야겠다는 생각을 했다. 그래서 오늘부터 알고리즘 하나씩 공부한 후 이 블로그에 정리해보려고 한다. 오늘 공부한 것은 검색알고리즘으로 선형 검색과 이진 검색이다.

 

 

 

 

▏정의

 

선형 검색 : 무작위로 늘어놓은 데이터 집합 일 때 적절한 검색 알고리즘

이진 검색 : 일정한 규칙으로 늘어놓은 데이터 집합  일 때 적절한 검색 알고리즘

해시법 : 추가 · 삭제가 자주 일어나는 데이터 집합 일 때 적절한 검색 알고리즘

 

 

 

 

▏선형 검색

 

선형 검색을 풀이하면 sequential( linear ) search 이다. 즉, 앞에서부터 순차적으로 검색하는 알고리즘이다.

 

앞에서 부터 검색하기 때문에 데이터 수가 많아지면 시간이 많이 걸린다는 단점이 있다.

 

배열 검색에서 가장 기본적인 알고리즘으로 원하는 키 값을 갖는 요소를 찾을 때 까지 앞에서부터 순서대로 검새하는것이 선형(순차) 배열이다.

 

 

 

 

▏이진 검색

 

이진 검색의 방법은 배열의 중앙 요소부터 검색하는 것 이다.

 

검색하려는 값과 중앙요소를 비교하며 탐색 범위를 줄여나간다. 원하는 요소 찾을 때 까지 이를 반복한다.

 

이진 검색에 전제 조건은 요소가 오름차순 · 내림차순으로 정렬되어 있어야한다.

 

public static int linear(int[] arr, int n) {
	int fi = 0; //first_index
	int li = arr.length-1; //last_index
	do {
		int mi = (fi + li) / 2; // middle_index
		if(arr[mi] == n) {
			return mi;
		}else if(arr[mi] < n){
			fi = mi +1;
		}else {
			li = mi -1;
		}
	}while(fi <= li);
	return -1;
}

// int[] arr = {5,7,15,28,29,31,39,58,68,70,95};
// int n = 39;

 

 

 

 

▏해시법

 

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

오픈 주소법 : 데이터를 위한 해시 값이 충도랗ㄹ 때 재해시하는 방법

 

 

 

 

▏참고 자료

 

https://velog.io/@dlrmsghks7/%ED%83%90%EC%83%89-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84-%EC%95%8C%EC%95%84%EB%B4%85%EC%8B%9C%EB%8B%A4