03 검색

Do it 자료구조와 함께 배우는 알고리즘 입문 자바편 을 읽고 정리한 내용입니다.

검색 알고리즘

배열 검색

배열 검색은 다음의 알고리즘을 활용한다.

1. 선형 검색 : 무작위롤 늘어놓은 데이터 모임에서 검색을 수행한다.
2. 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 빠른 검색을 수행한다.
3. 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 빠른 검색을 수행한다.
	- 체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법
    - 오픈 주소법 : 데이터를 위한 해시 값이 충동할 때 재해시하는 방법

선형 검색(순차 검색)

요소가 직선 모양으로 늘어선 배열에서의 검색
원하는 키 값을 갖는 요소를 만날 때까지 앞에서부터 순서대로 요소를 검색한다.

• 검색의 종료 조건
  • 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 (실패)
  • 검색할 값과 같은 요소를 발견한 경우 (성공)

배열의 요솟수가 n개 일 때 검색에 필요한 비교 횟수의 평균값은n/2회

보초법

검색하고자 하는 키 값을 배열 맨 끝 요소에 저장(보초)
이렇게 하면 실패했을 때의 종료 조건을 판단하지 않아도 되어 비용이 반으로 줄어든다.

이진 검색

요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색
배열 요소의 중앙 값과 키 값을 비교하며 검색한다.

오름차순으로 정렬된 배열
 - 중앙 값 < 키 값 : 중앙 값의 오른쪽 요소들에서 검색
 - 중앙 값 > 키 값 : 중앙 값의 왼쪽 요소들에서 검색

• 검색의 종료 조건
  • 중앙 값과 검색할 값이 일치하는 경우
  • 검색 범위가 더 이상 없는 경우

배열의 요솟수가 n개 일 때 검색에 필요한 비교 횟수의 평균값은 log n회

복잡도

알고리즘의 성능을 객관적으로 평가하는 기준

1. 시간 복잡도 (time complexity) : 실행에 필요한 시간을 평가한 것
2. 공간 복잡도 (space complexity) : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

선형 검색의 시간 복잡도

선형 검색의 종료 조건을 판단하는 평균 횟수는 n/2.
이처럼 n에 비례하는 횟수만큼 실행하는 경우의 복잡도를 O(n)으로 표기

이진 검색의 시간 복잡도

이진 검색의 종료 조건을 판단하는 평균 횟수는 log n.
따라서 복잡도는 O(log n)

Arrays.binarySearch에 의한 이진 검색

Arrays.binarySearch : Java에서 제공하는 이진 검색 표준 라이브러리의 메서드

오름차순으로 정렬된 배열 a를 가정하고 키 값이 key인 요소를 이진 검색한다.

• 검색에 성공 하는 경우
  key와 일치하는 요소의 인덱스를 반환한다. 일치하는 요소가 여러 개 있다면 무작위의 인덱스를 반환한다.

• 검색에 실패 하는 경우
  삽입 포인트를 x라고 할 때 -x-1을 반환한다.

  삽입 포인트 : 검색하기 위해 지정한 key보다 큰 요소 중 첫 번째 요소의 인덱스. 만약 배열의 모든 요소가 key보다 작다면 배열의 길이

예제1) 기본 자료형 배열에서 binarySearch 메서드로 검색

import java.util.Arrays;
import java.util.Scanner;

class BinarySearchTester {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        
        // 요솟수가 num개인 int 자료형 배열 생성
        System.out.print("요솟수 : ");
        int num = sc.nextInt();
        int[] x = new int[num];
        
        System.out.println("오름차순으로 입력하세요.");
        
        System.out.print("x[0] : ");
        x[0] = sc.nextInt();	// 첫 번째 요소 먼저 입력
        
        // 오름차순으로 입력받기 위해 앞 요소보다 작으면 다시 입력
        for(int i = 1; i < num; i++) {
        	do {
            	System.out.print("x["+ i +"] : ");
        		x[i] = sc.nextInt();
            }while (x[i] < x[i-1]);
        }
        
        System.out.print("검색할 값 : ");
        int key = sc.nextInt();
        
       	int idx = Arrays.binarySearch(x, key);
        // 컴파일러가 자동으로 'static int binarySearch(int[] a, int key)' 메서드를 호출
        
       	if(idx < 0)
        	System.out.print("검색한 값이 존재하지 않습니다.");
        else
        	System.out.print(key+"은(는) x["+ idx +"]에 있습니다.");
    }
}

객체의 배열에서 검색

예제2) 자연 정렬로 정렬된 배열에서 검색

import java.util.Arrays;
import java.util.Scanner;

class StringBinarySearch {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
		
        // 자연 정렬로 정렬된 문자열 배열
        String[] x = {
        	"abstract", "assert", "boolean", "break", "byte",
            "case", "catch", "char", "class", "const", "continue",
            "default", "do", "double", "else", "enum", "extends",
            "final", "finally", "float", "for", "goto", "if",
            "implements", "import", "instanceof", "int", "interface",
            "long", "native", "new", "package", "private" 
    	}
        
        System.out.print("원하는 키워드를 입력하세요: ");
        
        String key = sc.next();
        
    	int idx = Arrays.binarySearch(x, key);
        // 컴파일러가 자동으로 'static int binarySearch(Object[] a, Object key)' 메서드를 호출
        
        if(idx < 0)
        	System.out.print("해당 키워드가 존재하지 않습니다.");
        else
        	System.out.print(key+"은(는) x["+ idx +"]에 있습니다.");
}

예제3) 자연 정렬로 정렬되지 않은 배열에서 검색

import java.util.Arrays;
import java.util.Scanner;
import java.util.Comparator;

class PhyExamSearch {
	static class Physcata{
    	private String name;
        private int height;
        private double vision;
        
        public PhyscData(String name, int height, double vision) {
        	this.name = name; this.height = height; this.vision = vision; 
        }
        
        public String toString() {
        	return  name + " " + height + " " + vision;
        }
        
        // 오름차순으로 정렬하기 위한 comparator
        public static final Comparator<PhyscData> HEIGHT_ORDER = new HeightOrderComparator();
        
        private static class HeightOrderComparator implements Comparator<PhyscData> {
        	public int compare(PhyscData d1, PhyscData d2) {
            	return (d1.hegiht > d2.height) ? 1 :
                	   (d1.hegiht < d2.height) ? -1 : 0;
            }
        }
        
        public static void main(String[] args) {
        	Scanner sc = new Scanner(System.in);
            PhyscData[] x =  {
            	new PhyscData("이나영", 162, 0.3),
                new PhyscData("유지훈", 168, 0.4),
                new PhyscData("김한결", 169, 0.8),
                new PhyscData("홍준기", 171, 1.5),
                new PhyscData("이수민", 175, 2.0)
            };
            
            System.out.print("몇 cm인 사람을 찾고 있나요? ");
            int height = sc.nextInt();
            
            int idx = Arrays.binarySearch(
            	x, 									// 배열 x에서
                new PhyscData("", height, 0.0),		// 키가 height인 요소를
                PhyscData.HEIGHT_ORDER				// comparator HEIGHT_ORDER에 의해 검색
            );
            // 컴파일러가 자동으로 'static<T> int binarySearch(T[] a, T key, Comparator<? super T> c)' 메서드를 호출
   
   			if(idx < 0)
        		System.out.print("검색한 값이 존재하지 않습니다.");
        	else {
        		System.out.println("x["+ idx +"]에 있습니다.");
            	System.out.println("찾은 데이터 : " + x[idx]);
        	}
        }
    }
}

보충1) 클래스 메서드와 인스턴스 메서드

• 인스턴스 메서드
  • static을 붙이지 않고 선언한 메서드
  • 클래스형 변수 이름.메서드 이름으로 호출
• 클래스 메서드
  • static을 붙이고 선언한 메서드
  • 클래스 전체에 대한 처리를 담당, 인스턴스 영역에 포함되지 않음
  • 클래스 이름.메서드 이름으로 호출

보충2) 제네릭

• 처리해야 할 대상의 자료형에 의존하지 않는 클래스(인터페이스) 구현 방식
• 선언 방법 : <Type> 같은 형식의 파라미터를 붙여 선언

class 클래스 이름 <파라미터> {/* .... */}
interface 인터페이스 이름 <파라미터> {/* .... */}

• 파라미터 이름 작성 방법

1. 1개의 대문자를 사용 (소문자는 가급적 사용X)
2. 컬렉션(collection)의 자료형은 element의 앞 글자인 E 사용
3. 맵(Map)의 키, 값은 K와 V를 사용
4. 일반적으로는 T 사용

형변수에는 와일드카드 지정 가능

• <? extends T> : 클래스 T의 서브 클래스를 전달받는다.
• <? super T> : 클래스 T의 슈퍼 클래스를 전달 받는다.