알고리즘 공부 - 검색부터 다시 해보자

개요

나는 현재 개발자로 솔루션회사에서 근무중인 주니어개발자이다. JAVA 언어가 베이스인 회사에서 자바와 스프링 프레임워크로 코딩하는 것은 당연하지만, 일을 할수록 공부하는 시간이 줄어들고 알고리즘등 혹시 나중에 코딩테스트가 필요할텐데 싶은 생각에 앞으로 꾸준히 문제를 풀어야겠다고 생각이 들어 문법은 건너뛰고 검색 알고리즘부터 재귀, 큐, 스택등으로 개념정리부터 해보려고 한다.

 

열심히 정리해보자!

 

선형검색(linear search) 

간단하게 생각하자면 선형 = 일자로 쭉 늘어진 것 따위 일것이다. 그렇게 key 와 일치하는 값을 찾기위해 하나씩 검색하면서 진행하는 알고리즘으로 보통 for문이나 switch문으로 loop를 돌려서 index 를 증가시키며 찾는 것이다. 가장 단순한 알고리즘으로 구현하기도 가장 쉽다. 시간 복잡도는 O(n)이며 n만큼 비례하는 횟수로 실행하는 경우를 의미한다. 

static int searchAl(int key) {
	int[] searchArr = {}; // 뭐가들어있는지 모르는 배열이 있고 값이 있다고 가정해보자 //
    int result = 0; // 결과값을 담을 변수 //
	for(int i=0; i< searchArr.length(); i++) {
    	if (searchArr[i] = key) {
			result = i;
			break;
    	}
    }

정말 대충 구현해보았는데 이처럼 index i 를 증가시키며 한칸씩 결과값이랑 일치할때까지 찾아가는 것이다.

여기서 해당 Loop 가 종료하는 조건은 크게 두가지이다. 

1. 검색할 값을 발견하지 못하고 loop가 모두 끝났을 때 (일치하는 값이 배열에 없는 경우)

2. 검색할 값과 일치하는 값을 찾은 경우

 

이 종료하는 조건을 줄이면 그만큼 안정성이 높아지는 알고리즘이 된다. 그래서 선형 알고리즘엔 보초법이라는 개념을 추가할 수 있다.

보초법이란 ? 알고리즘의 종료조건의 비용을 줄이기 위해 sentinel method, 보초를 세워두고 진행하는 것입니다.

여기서 보초는 내가 찾을 key 값을 의미하며, 찾고싶은 key값을 배열의 마지막에 추가하고 Loop를 돌리면 최소한 위 두가지중 첫번째인 

일치하는 값이 없이 종료하는 경우에 마지막 배열의 인덱스에서 일치하며 종료되어 종료 비용을 줄입니다. 물론 일치한 배열의 마지막 인덱스는 임의로 추가하였기때문에 없는 것으로 치는 겁니다. 

 

 

이진 검색 (binary search)

선형검색을 단방향검색이라 하면 이진검색을 똑같이 배열에 있을 때 그리고 이 배열이 오름차순 또는 내림차순으로 정렬이 되어있다는

가정이 되어있을 때 적용할 수 있다. 정렬이된 이 배열의 중간값부터 시작하여 해당 값이 크거나 작거나를 비교해 왼쪽(-) 혹은 오른쪽(+)으로 진행하여 다시 중간값으로 가서 큰지 작은지 비교하는 것이다.

그렇게 경우의 수를 1/2 만큼씩 줄여가며 Up & Down 으로 비교하면서 index 를 찾아가는 것으로 정렬이 되어있다면 선형검색보다 적은 시간복잡도를 가질 수 있다. 이진 검색의 시간복잡도는 O(log n)이다. 

static int binaryAl(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) {   // key보다 작다면 검색 범위를 뒤쪽 절반으로 줄임
        	pl = pc + 1;
        } else { 					// 그게아니면 검색 범위를 앞쪽 절반으로 줄임 
        	pr = pc - 1;
        } while ( pl <= pr );

 

위 처럼 계속해서 중간값과 비교하며 크면 뒤쪽의 중간값으로,  작다면 앞쪽의 중간값으로 이동하면서 비교하는 알고리즘이다. 

그리고 JAVA에서는 이를 Arrays 클래스의 binarySearch(Array , Key) 메소드가 지원함으로 사실 따로 코드를 직접 구현할 필요는 없지만 로직이나 개념은 알고가는게 좋겠다.