검색

검색이란 저장된 자료 중에서 원하는 항목을 찾는 작업으로서 자료를 구별하여 인식할 수 있는 키인 탐색 키를 가진 항목을 찾는 것이다.

 

검색의 종류

1. 순차 검색(sequential search)

2. 이진 검색(Binary search)

3. 완전 검색(Exhausting Search)

 

1. 순차 검색

일렬로 되어 있는 자료를 순서대로 검색하는 방법으로 가장 간단하고 직관적인 방법이다. 배열이나 연결 리스트 등 순차 구조로 구현된 자료 구조에서 원하는 항목을 찾을 때 유용하다. 알고리즘이 단순해 구현이 쉽지만, 검색 대상의 수가 많은 경우 수행시간이 급격히 증가해 비효율적이다.

 

1) 정렬되어 있지 않은 경우 첫 원소부터 순서대로 자료 구조의 마지막까지 검색 대상과 키 값이 같은 원소가 있는지 비교하며 찾는다. 시간 복잡도 O(n)

2) 정렬되어 있는 경우 찾고자 하는 원소의 순서에 따라 비교 횟수가 결정된다.  시간 복잡도 O(n)

평균 비교 횟수 = (n+1)/2 시간 * 정렬되어 있기 때문에 검색 실패를 반환하는 경우 평균 비교 횟수가 반으로 줄어든다.

 

2. 이진 검색

자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법으로서 목적 키를 찾을 때까지 이진 검색을 순환 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행

→ 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다.

 

검색 범위의 시작점과 종료점을 이용해 검색을 반복 수행한다.

정렬 -> 중앙 인덱스를 이용해 중앙값 선언 ->

1) 중앙값 = =키 값 -> 검색성공

2) 중앙값 < 키 값 -> 범위 조정 시작점: 중앙값+1

3) 중앙값 > 키 값 -> 범위 조정 끝 점: 중앙값-1

 

3. 완전 검색

가능한 모든 경우의 수를 시도하는 것으로서 brute-force / Generate-and-test 기법이라고도 불린다. 경우의 수가 상대적으로 작을 때 유용하다. 수행속도는 느려도 해답을 찾지 못할 확률은 적은 편이다.

 

<베이비진 함수로 구현>

package dailypractice;

import java.util.Arrays;

public class BabyJin_230220_method {

	public static void main(String[] args) {

		int[] arr = { 1, 1, 1, 2, 2, 2 };
		// 최댓값 만들고 카운팅 배열에 넣기
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] > max) {
				max = arr[i];
			}
		}
		int[] cArr = new int[max + 1];
		for (int i = 0; i < arr.length; i++) {
			cArr[arr[i]] += 1;
		}
		System.out.println(babyJinCheck(cArr));
	}

	static boolean babyJinCheck(int[] cArr) {
		int triplet = 0;
		int run = 0;

		for (int j = 0; j < 2; j++) {
			for (int i = 0; i < cArr.length; i++) {
				if (cArr[i] >= 3) {
					cArr[i] -= 3;
					triplet++;
				}
//				System.out.println(Arrays.toString(cArr));
				if (i < cArr.length - 2) {
					if (cArr[i] == 1 && cArr[i + 1] == 1 && cArr[i + 2] == 1) {
						run++;
						cArr[i]--;
						cArr[i + 1]--;
						cArr[i + 2]--;
//						System.out.println(Arrays.toString(cArr));
					}
				}
			}
		}
		return (triplet == 2 || run == 2 || (triplet == 1 && run == 1));
	}
}