자바에 대한 기본기는 다지는 중이지만
자료구조 및 알고리즘에 대한 지식은 부족하여 공부하려고 함.
이 글은 내가 학습한 것에 대한 메모이다.

1. 검색 알고리즘

• 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 알고리즘

(1) 검색알고리즘 종류

1. 선형 검색: 무작위로 늘어서 있는 데이터 모임을 검색
2. 이진 검색: 일정한 규칙으로 늘어서 있는 데이터 모임을 빠르게 검색
3. 해시법: 추가, 삭제가 자주 일어나는 데이터 모임을 빠르게 검색
	1) 체인법: 같은 해시값의 데이터를 선형 리스트로 연결
    2) 오픈 주소법: 데이터를 위한 해시값이 충돌할때 재해시.

• 검색이 빠르더라도 데이터 추가하는 것이 빈번하게 있다면 추가비용이 많이 들어있는 알고리즘은 피해야 한다.

1) 선형 검색

• 직선 모양으로 늘어선 배열에서 원하는 키값을 갖는 요소를 만날때까지 순서대로 요소를 검색
• 선형 검색의 종료 조건은 해당 요소의 키값과 같은 요소를 발견했을 때 선형 검색의 알고리즘은 종료된다.
  단, 배열의 요솟수가 n개일때, 판단횟수는 n/2회

int i=0;

while(true) {
	if(i == n) 
    	return -1; // 검색실패(-1 반환)
    if(a[i] == key)
    	return i; // 검색성공(인덱스 반환)
    i++;
}

(1) 보초법

• 맨 끝의 요소를 검색하기 전에 값을 저장하는 보초
• 즉, 2를 검색하기 위해 보초로 a[7]에 2를 저장한다.
• 보초는 반복문에서 종료 판단횟수를 2회에서 1회로 줄인다.

package chap3;

import java.util.Scanner;

class SeqSearchSen {
    static int seqSearch(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; // 변수 i값이 n이면 값이 보초임.
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("요솟수: ");
        int num = scanner.nextInt();
        int[] x = new int[num + 1]; // 요솟수가 num + 1인 배열

        for(int i=0; i<num; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = scanner.nextInt();
        }

        System.out.print("검색할 값: ");
        int ky = scanner.nextInt();

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

• 선형검색의 코드에는 종료조건 2개인 if문을 제시함.
• 하지만, 위 코드는 하나의 if문을 사용하고 리턴값을 보초인지 데이터 요소값인지 찾는 조건을 넣었음.
• 보초법을 적용해서 if문의 판단횟수는 줄였음.

2) 이진 검색

• 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘
• 이진 검색은 표시한 선택요소를 단숨에 여러 칸 이동 후 검색 시작

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

• 예를 들면, 39를 검색하려고 할때 배열의 중앙에 위치한 a[5] 부터 검색. a[5] = 31
• a[6]부터 a[10]까지의 중앙에 위치한 a[8] 검색.
• a[8] = 68. 원하는 값보다 크기 때문에 a[6]~a[7]로 좁힐 수 있음.
• 두 요소 중 앞쪽의 값을 선택한 후 확인.
• 실습 코드는 아래에 있다.

package chap3;

import java.util.Scanner;

class BinSearch {
    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 scanner = new Scanner(System.in);

        System.out.print("요솟수: ");
        int num = scanner.nextInt();
        int[] x = new int[num];

        System.out.println("오름차순으로 입력하세요");

        System.out.print("x[0]: ");
        x[0] = scanner.nextInt();

        for(int i=1; i<num; i++) {
            do {
                System.out.print("x[" + i + "]: ");
                x[i] = scanner.nextInt();
            } while(x[i] < x[i-1]);
        }

        System.out.print("검색할 값: ");
        int ky = scanner.nextInt();

        int idx = binSearch(x, num, ky);

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

(1) 복잡도 구하기

• 복잡도: 알고리즘의 성능을 객관적으로 평가하는 기준

- 시간 복잡도: 실행에 필요한 시간을 평가하는 것.
- 공간 복잡도: 기억 영역과 파일 공간이 얼마나 필요한가를 평가

선형 검색의 시간 복잡도

static int seqSearch(int[] a, int n, int key) {
	int i = 0;
    
    while(i < n) {
    	if(a[i] == key)
        	return i;
        i++;
    }
    return -1;
}

이진 검색의 시간 복잡도

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

• 이진 검색법은 검색할 요소의 범위가 줄어들음.

(2) Arrays.binarySearch 이진검색

• 자바는 배열에서 이진검색을 하는 메서드를 표준 라이브러리에 제공
• binarySearch 메서드는 오름차순으로 정렬된 배열a를 가정하고 값이 key 요소인 이진 검색.
• 검색에 성공한 경우 key와 일치하는 요소의 인덱스 반환
• 검색에 실패한 경우 반환값을 -x-1로 변경한다.

객체의 배열에서 검색하기

static int binarySearch(Object[] a, Object key)

• 자연 정렬이 된 배열에서 요소의 대소관계를 판단하고 검색하는 메서드

static<T> int binarySearch(T[] a, T key, Comparator<? super T>c)

• 자연 정렬이 아닌 순서로 나열한 배열에서 검색하는 메서드

Comparator<? super T>c

• 클래스 T의 두 객체 사이의 대소관계를 생성하는 comparator.
  o1>o2이면 양수 변환, 같으면 0변환 작으면 음수 변환

package java.util;

public interface Comparator<T> {
	int compare(T o1, T o2);
    boolean equals(Object obj);
}

• 객체의 대소관계를 판단하는 Comparator 사용자가 구현하려면 인터페이스를 구현한 클래스를 정의하고 인스턴스를 생성.

3) 제네릭스

• 제네릭스는 처리 대상의 자료형에 의존하지 않도록 클래스를 구현
• 자료형 클래스로부터 안전함.

class 클래스이름 <매개변수> { }
interface 인터페이스 이름<매개변수> { }

• 파라미터 입력하는 방법은 다음과 같다.

1. 대문자는 1개를 사용한다.
2. 컬렉션 내부 요소의 자료형은 element의 머리글자 E를 사용
3. 맵(Map) 내 키와 값의 자료형은 key와 value의 머리글자 K와 V를 사용
4. 일반적인 자료형은 T를 사용한다.

• 파라미터에는 와일드 카드를 지정.

<? extends T>: 클래스T의 하위 클래스를 전달
<? super T>: 클래스T의 상위 클래스를 전달