이 글은 'Do it! 자료구조와 함께 배우는 알고리즘 입문 (자바 편)' 책(이번 포스팅의 경우 chap3)을 보고 정리한 내용입니다. (기본적인 자바 문법을 안다는 가정에서 기본적인 부분(사람마다 다르겠지만...)위주로 정리한다.

3장에서는 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 검색 알고리즘에 대해 살펴본다.

검색과 키

주소록을 검색한다고 가정했을 때, 검색(searching)은 다음과 같은 과정으로 이루어진다.

1. 국적이 한국인 사람을 찾는다
2. 나이가 21세이상 27세 미만인 사람을 찾는다
3. 찾으려는 이름과 가장 비슷한 이름의 사람을 찾는다

위의 검색뿐만 아니라 어떤 검색을 하게 되더라도 특정 항목에 주목한다는 점은 '검색하기'의 공통점이다. 여기서 그 주목하는 항목을 키(key)라고 하면, 국적을 검색하는 경우 국적이 키이고 나이를 검색하는 경우 나이가 키 역할을 한다. 데이터가 단순한 정숫값이면 데이터 값을 키 값이라고 생각해도 좋지만 대부분의 경우에서 키는 데이터의 '일부'이다. 그런데 위의 검색과정을 보면 키 값을 아래처럼 지정한다.

1. 키 값과 일치하도록 지정합니다(한국).
2. 키 값의 구간을 지정합니다(21세 이상 27세 미만).
3. 키 값과 비슷하도록 지정합니다(발음이 가장 비슷한 이름).

물론 이런 조건은 하나만 지정하기도 하지만 논리곱이나 논리합을 사용하여 복합해서 지정하기도 한다.

배열에서 검색하기

아래는 검색에 대한 세 가지 예로, 이 세가지 검색 기법에서 몇몇은 자료구조에 의존하는 방법이다.

• 배열 검색
• 선형 리스트 검색(9장)
• 이진 검색트리 검색(8장)

이 장에서 학습하는 것은 '배열 검색'이며 다음의 알고리즘을 활용한다.

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

데이터 집합이 있을 때 '검색만 하는 경우'라면 검색에 사용할 알고리즘은 시간이 짧은 것을 선택하면 된다. 그러나 데이터 집합에 대한 검색뿐 아니라 데이터의 추가, 삭제 등을 자주하는 경우라면 검색 이외의 작업에 소요되는 비용을 종합적으로 평가하여 알고리즘을 선택해야 한다. (예를 들어 데이터의 추가를 자주하는 경우에는 검색이 빠르더라도 데이터의 추가 비용이 많이 들어가는 알고리즘은 피해야 한다)

따라서 어떤 목적을 이루기 위해 선택할 수 있는 알고리즘이 여러 가지인 경우에는 용도나 목적, 실행 속도, 자료구조 등을 고려하여 알고리즘을 선택해야 한다.

(1) 선형 검색

요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 앞부터 순서대로 요소를 검색하면 되는데, 이것이 선형 검색(linear search) 또는 순차 검색(sequential search)이라는 알고리즘이다. 

성공의 예와 실패의 예를 보면 배열 검색의 종료 조건은 2개임을 알 수 있다. 다음 조건 중 하나라도 성립하면 검색을 종료한다.

• 조건1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
• 조건2. 검색할 값과 같은 요소를 발견한 경우

물론 '조건 1'이 성립: 검색 실패, '조건 2'가 성립: 검색 성공이다. 배열의 요솟수가 n개일 때 조건 1, 2를 판단하는 횟수는 평균 n / 2회이다.

import java.util.Scanner;

public class SeqSearch {
    // 요솟수가 n인 배열 a에서 key와 같은 요소를 선형 검색한다.
    static int seqSearch(int[] a, int n, int key) {
    
   		int i = 0;

        while (true) {
            if (i == n)
                return -1;  // 검색 실패!(-1을 반환)
            if (a[i] == key)
                return i;   // 검색 성공!(인덱스를 반환)
            i++;
        }
        
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

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

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

        System.out.print("검색할 값: ");    // 키 값을 입력
        int ky = sc.nextInt();

        int idx = seqSearch(x, num, ky);    // 배열 x에서 키 값이 ky인 요소를 검색

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


    }
    
}

메서드 SeqSearch는 배열 a의 처음부터 끝까지 n개의 요소를 대상으로 값이 key인 요소를 선형 검색하고 검색한 요소의 인덱스를 반환한다. 또한 값이 key인 요소가 여러 개 존재할 경우 반환값은 검색 과정에서 처음 발견한 요소의 인덱스가 된다. 값이 key인 요소가 존재하지 않으면 -1을 반환한다. 

배열을 검색할 때 배열 요소의 인덱스를 가리키는 변수는 i이다. i는 0으로 초기화하고 요소를 하나 검색할 때마다 while문이 제어하는 루프 본문의 끝에서 증가시킨다. while문을 빠져나가는 경우는 앞에서 살펴본 종료 조건 가운에 하나가 성립한 경우이다.

• i == n이 성립하는 경우 (종료 조건1 : 검색 실패이므로 -1을 반환)

• a[i] == key가 성립하는 경우 (종료 조건2 : 검색 성공이므로 i를 반환)

이때 whie문을 for문으로 수정하면 프로그램은 보다 짧고 간결해진다. (생략)

보초법

선형 검색은 반복할 때마다 다음의 종료 조건 1과 2를 모두 판단한다. 단순한 판단이라고 생각할 수 있지만 '티끌 모아 태산'이라는 말이 있듯이 종료 조건을 검사하는 비용을 결코 무시할 수 없다.

1. 검색할 값을 발견하지 못 하고 배열의 끝을 지나간 경우

2. 검색할 값과 같은 요소를 발견한 경우

이 비용을 반(50%)으로 줄이는 방법이 보초법(sentinel method)이다. 

간단하게 말해서 준비해 놓은 데이터의 마지막 요소로 검색할 값을 저장하여 종료 조건 1이 없어도 된다. (보초를 세운다고 생각!) 보초는 반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 한다.

package problem.algorithm.chap3;

import java.util.Scanner;

public class SeqSearchSen {

    public int seqSearchSen(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;
    }


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

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

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

        System.out.print("검색할 값:");     // 키 값을 입력
        int ky = sc.nextInt();

        SeqSearchSen sol = new SeqSearchSen();
        int idx = sol.seqSearchSen(x, num, ky);       // 배열 x에서 값이 ky인 요소를 검색

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

이 프로그램은 종료조건 1이 필요하지 않기 때문에 하나의 if문만 사용했다. 따라서 반복 종료에 대한 판단 횟수는 실제로 절반으로 줄어든다.

이진 검색

이진 검색은 선형 검색보다 좀 더 빠르게 검색할 수 있다는 장점이 있다. 

이진 검색(binary search)은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다.

아래 그림에서 오름차순으로 정렬된 데이터에서 39를 검색하는 과정을 생각해보자.
먼저 배열의 중앙에 위치한 요소인 a[5](31)부터 검색을 시작한다.

     0                    1                 2                 3                4                5                 6                7                 8               9               10

검색하려는 값인 39는 중앙 요소(a[5])보다 큰 값이다. 그러므로 검색 대상을 뒤쪽의 5개(a[6] ~ a[10])로 좁힐 수 있다. 그런 다음 검색 범위의 중앙에 위치한 요소인 a[8](68)이 원하는 값인지 확인한다.

        0                    1                 2                 3                4               5               6                7                 8               9               10

검색하려는 값인 39보다 큰 값이다. 그러므로 검색 대상을 앞쪾의 2개로 좁힐 수 있다. 이제 검색해야하는 대상은 2개이다. 이때 두 요소의 중앙 요소는 39나 58 중 아무거나 선택해도 상관없지만 여기서는 앞쪽의 값 39를 선택하여 원하는 값인지 확인한다.

     0                    1                 2                 3                4               5                6                7                 8               9               10

39는 원하는 키의 값과 일치하므로 검색 성공이다. 

이러한 n개의 요소가 오름차순으로 늘어선 배열 a에서 키를 이진 검색으로 검색하는 과정을 일반적인 방법으로 표현해본다.
이때 검색 범위의 맨 앞 인덱스를 pl, 맨 끝 인덱스를 pr, 중앙 인덱스를 pc라고 지정한다. 검색을 시작할 때, pl은 0, pr은 n-1, pc는 (n - 1) / 2로 초기화한다. 여기까지 설명한 내용이 첫번째 단계이다. 검색 대상의 범위는 하얀칸이고 검색 대상에서 제외되는 범위는 검정색 칸의 요소이다. 여기서 주목할 점은 이진 검색을 한 단계씩 진행할 때마다 검색 범위가 반으로 좁혀진다는 것이다. 또한 검사한 요소를 하나씩 제외시키는 선형 검색과는 다르게 이진 검색은 검색할 요소가 해당 단계에서 다음에 검색할 범위의 중간 지점으로 단숨에 이동한다.

1. a[pc] < key 일 때

a[pl] ~ a[pc]는 key 보다 작은 것이 분명하므로 검색 대상에서 제외한다. 검색 범위는 중앙요소 a[pc]보다 뒤쪽의 a[pc+1] ~ a[pr]로 좁힌다. 그런 다음 pl의 값을 pc + 1로 업데이트 한다.

2. a[pc] > key 일 때

a[pc] ~ a[pr]은 key보다 큰 것이 분명하므로 검색 대상에서 제외한다. 검색 범위는 중앙요소 a[pc]보다 앞쪽 a[pl] ~ a[pc - 1]로 좁힌다. 그런 다음 pr의 값을 pc - 1로 업데이트한다. 

이 과정을 구현한 프로그램은 아래와 같다. 이진 검색은 검색을 반복할 때마다 검색 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균값은 log n이다. 검색에 실패한 경우는 [log(n+1)]회, 검색에 성공한 경우는 대략 [logn - 1]회 이다.

import java.util.Scanner;

public class BinSearch {

    public 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 sc = new Scanner(System.in);

        System.out.print("요솟수: ");
        int num = sc.nextInt();
        int[] x = new int[num];         // 요솟수가 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 ky = sc.nextInt();

        BinSearch binSearch = new BinSearch();

        int idx = binSearch.binSearch(x, num, ky);     // 배열x에서 키 값이 ky인 요소를 검색

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

이진 검색은 알고리즘은 검색 대상(배열)이 정렬(sort)되어 있음을 가정한다. 따라서 이 프로그램의 색칠된 부분은 사용자가 각 요소의 값을 입력하는 과정에서 바로 앞에 입력한 요소보다 작은 값인 경우에는 다시 입력하게 한다. 

복잡도

프로그램의 실행 속도는 프로그램이 동작하는 하드웨어나 컴파일러 등의 조건에 따라 달라진다.
알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도(complexity)라고 한다.

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

실행 횟수 n에 비례하는 횟수만큼 실행하는 경우의 복잡도를 O(n)으로 표기한다.
선형 검색의 알고리즘의 복잡도는 O(n)이다. 

이진 검색의 시간 복잡도는 O(log n) 이다.

Arrays.binarySearch에 의한 이진 검색

Java는 배열에서 이진 검색을 하는 메서드를 표준 라이브러리로 제공한다. 이진 검색 표준 라이브러리의 메서드로는 java.utils.Arrays 클래스의 binarySearch 메서드가 있다. binarySearch 메서드는 다음과 같은 장점이 있다.

1. 이진 검색 메서드를 직접 코딩할 필요가 없다.
2. 모든 자료형 배열에서 검색할 수 있다.

binarySearch 메서드는 오름차순으로 정렬된 배열 a를 가정하고, 키 값이 key인 요소를 이진 검색한다. (자료형에 따라 9가지 방법으로 오버로딩 되어있다)

검색에 성공한 경우

key와 일치하는 요소의 인덱스를 반환한다. 일치하는 요소가 여러 개 있다면 무작위의 인덱스를 반환한다. (맨 앞의 인덱스나 어떤 특정한 인덱스를 반환하는 것이 아니다!) 

검색에 실패한 경우

반환한 값은 삽입 포인트를 x라고 할 때 (-x - 1)을 반환한다. 삽입 포인트는 검색하기 위해 지정한 key보다 큰 요소 중 첫 번째 요소의 인덱스이다. 만약 배열의 모든 요소가 key보다 작다면 배열의 길이를 삽입 포인트로 정한다. 만약 배열의 모든 요소가 key보다 작다면 배열의 길이를 삽입 포인트로 정한다.

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

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

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

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

        System.out.print("x[0] :"); // 배열의 첫 요소를 먼저 입력한다.
        x[0] = stdIn.nextInt();

        for(int i = 1; i < num; i++) {
            do {
                System.out.print("x[" + i + "] : ");
                x[i] = stdIn.nextInt();
            } while (x[i] < x[i - 1]); // 바로 앞의 요소보다 작으면 다시 입력한다.
        }

        System.out.print("검색할 값 : "); // 키 값을 입력 받음
        int ky = stdIn.nextInt();

        int idx = Arrays.binarySearch(x, ky); // 배열 x에서 키 값이 ky인 요소를 검색

        if (idx < 0) {
            System.out.println("그 값의 요소가 없습니다.");
        } else {
            System.out.println(ky + "은(는) x[" + idx + "]에 있습니다.");
        }
    }
}

기본 자료형 배열에서 binarySearch 메서드로 검색하기

binarySearch 메서드는 int형이나 long형과 같은 기본 자료형 배열에서 이진 검색을 하는 메서드이다. (위의 코드를 참조)

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

객체의 배열에서 검색하기

객체의 배열에서도 검색할 수 있다. Array 클래스의 메서드 중 아래 2개의 메서드로 검색한다.

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

   자연 정렬이라는 방법으로 요소의 대소 관계를 판단한다. 따라서 정수 배열, 문자열 배열에서 검색할 때 적당하다.

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

   "자연 순서"가 아닌 순서로 줄지어 있는 배열에서 검색하거나 "자연 순서"를 논리적으로 갖지 않는 클래스 배열에서 검색할 때 알맞다.

(binarySearch 메서드가 전달받는 자료형은 Object이다. Object는 모든 클래스의 최상위 클래스이다. 그래서 어떤 형태의 클래스도 받을 수 있다)

자연 정렬(natural ordering)

자신이 직접 만든 클래스 A에 대해서 "자연스러운 순서로 정렬할 필요가 있겠다!"라는 생각이 든다면 다음과 같이 클래스를 정의하면 된다.

/**
 * 자신이 직접 만들 클래스 A에 대해서 '자연 정렬'을 사용자가 원하는대로 정의하는 방법
 * comareTo, equals 메서드를 오버라이한다.
 */
public class A implements Comparable<A> {

    // 필드, 메서드 등

    @Override
    public int compareTo(A o) {
        // this가 o보다 크면 양의 값 반환
        // this가 o보다 작으면 음의 값 반환
        // this가 o와 같으면 0 반환
    }

    @Override
    public boolean equals(Object obj) {
        // this가 obj와 같으면 true 반환
        // this가 c와 같지 않으면 false 반환
    }
}

자연 정렬로 정렬되지 않은 배열에서 검색하기 

자연 정렬로 정렬되지 않은 배열에서의 검색은 제네릭 메서드(generic method)로 하면 된다. 제네릭 메서드의 첫 번째 매개변수 a는 검색 대상이고, 두 번째 매개변수 key는 키 값이다. 제네릭 메서드는 자료형에 구애받지 않는다. 따라서 매개변수로 전달하는 자료형은 Integer, String, 신체검사 데이터용 클래스 PhyscData등 어떤 것을 전달해도 좋다.

하지만 배열의 요소가 어떤 순서로 줄지어 있는지, 각 요소의 대소 관계를 어떻게 판단할 것인지에 대해서는 binarySearch 메서드에 알려주어야 한다. 이 정보는 세 번째 매개변수 c에 전달한다. 

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

세 번째 매개변수 c에는 comparator를 전달한다. comparator의 근원은 다음과 같이 정의된 java.util.Comparator 인터페이스이다.

// java.util.Comparator의 정의
package.java.util;

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

객체의 대소 관계를 판단하는 comparator를 직접 구현하려면 Comparator 인터페이스를 구현한 클래스를 정의하고 그 클래스형의 인스턴스를 생성해야 한다. 그런 다음 매개변수로 전달된 두 객체의 대소 관계를 비교하여 그 결과를 다음과 같이 반환하는 compare 메서드를 구현하면 된다.

public int compare(T d1, T d2) {
	if(d1 > d2) return 양수;
	if(d1 < d2) return 음수;
	if(d1 == d2) return 0;
}

따라서 클래스 X에 대한 comparator는 아래의 코드와 같이 정의할 수 있다.

import java.util.Comparator;
// 클래스 X의 내부에서 comparator를 정의하는 방법은 다음과 같다.

class X {
	// 필드, 메서드 등
    public static final Comparator<T> COMPARATOR = new Comp();
    
    private static class Comp implements Comparator<T> {
    	public int compare(T d1, T d2) {
        	//d1이 d2보다 크면 양의 값 반환
            //d1이 d2보다 작으면 음의 값 반환
            //d1이 d2와 같으면 0 반환
            }
    }
}

Comparator 인터페이스와 compare 메서드를 구현할 클래스를 먼저 작성한다. 그 후에 클래스의 인스턴스를 생선한다. 즉 COMPARATOR로 선언한 인스턴스를 comparator라고 부른다. 지금은 comparator를 클래스 내부에 정의하고 있지만 클래스 외부에서 정의해도 된다.

지금까지의 복잡한 내용에 비해 comparator의 사용법은 간단하다. binarySearch 메서드의 세 번째 매개변수로 클래스 X의 클래스 변수인 X.COMPARATOR를 전달하면 된다. 호출된 binarySearch 메서드는 전달받은 comparator를 기준으로 배열 요소의 대소 관계를 판단하여 이진 검색을 수행한다. 

제네릭 

다음은 제네릭 클래스를 구현한 프로그램이다.

// 제네릭 클래스의 예
public class GenericClassTester {

    static class GenericClass<T> {
        // 제네릭 클래스의 파라미터를 T라고 작성한다.
        private T xyz;
        public GenericClass(T xyz) { // 생성자
            this.xyz = xyz;
        }
        T getXyz() {                // xyz를 반환한다.
            return xyz;
        }
    }

    public static void main(String[] args) {
        // 다음과 같이 파라미터에 String을 넘길 수도 있고 Integer를 넘길 수도 있다.
        GenericClass<String> s = new GenericClass<>("ABC");
        GenericClass<Integer> n = new GenericClass<>(15);

        System.out.println(s.getXyz());
        System.out.println(n.getXyz());
    }
}

이상 3장을 마무리한다. 다음 장은 4장. '스택과 큐'에 대해 알아보도록한다.