선형 검색과 보초법에 대해서

안녕하세요, 오늘은 검색 알고리즘의 선형 검색과 보초 법에 대해서 알아보려고 합니다.
검색 알고리즘에는 대표적으로 선형 검색과 이진 검색으로 크게 두 가지로 분류를 할 수 있습니다.

🔎 검색 알고리즘은 무엇인가?

검색 알고리즘의 의미는 데이터베이스 내 수집 된 여러 아이템 중에서 특정 성질 혹은 키 값을 구성한 데이터를 찾아내는 알고리즘입니다. 대표적으로 검색 알고리즘은 배열, 선형 리스트, 이진 검색 트리 등 앞으로 배울 다양한 부분에서 검색 알고리즘을 활용합니다. 이번에 저희는 배열에서의 검색 알고리즘만을 공부해볼 것입니다. 먼저 아래의 알고리즘 사용 주의 사항에 대해 이야기하겠습니다.

 

알고리즘 활용 시 주의점

1. 상대적인 알고리즘의 수행 시간

2. 활용 용도나 목적, 자료구조 등 체계적인 부분

3. 데이터의 추가, 수정, 삭제 등 작업에 소요되는 비용

만약 당신이 어떤 목적을 이루기 위해 선택할 수 있는 알고리즘의 개수가 여러 가지인 경우 용도나 목적, 실행 속도, 자료구조 등을 잘 고려하여 작업에 소요되는 비용을 종합적으로 평가하여 효율적인 알고리즘을 선택하여 그 상황의 문제에 적용을 잘해야 합니다.

📈 선형 검색에 대해서 알아보자!

선형 검색은 검색 알고리즘에서의 가장 기본이 된다고 말할 수 있는 검색 알고리즘입니다. 요소가 직선 모양으로 늘어선 배열에서 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색합니다. 선형 검색 또는 순차 검색이라고 부르기도 합니다.

 

일반적인 int 정수형의 배열 모습입니다.

위의 배열은 크기가 7이며 int 정수형의 데이터를 가지고 있는 배열입니다. 이 배열에서 선형 검색 알고리즘을 활용하여 배열 속 데이터 값인 2를 찾는 알고리즘을 한 번 구현해보도록 하겠습니다. 코드로 구현을 하기 전 그림으로 알고리즘의 구조를 알아보겠습니다.

 

int 정수형 배열에서 선형 검색 알고리즘을 활용하여 숫자 2를 검색하는 과정 - 검색 성공

위의 사진은 선형 검색 알고리즘을 활용하여 배열 속에서 숫자 2를 찾는 과정입니다. 순차적으로 0번째 인덱스의 값부터 배열의 높은 인덱스 값으로 이동하면서 특정 값을 찾고 있습니다. 위의 상황은 배열에 찾는 값이 존재하기 때문에 선형 검색 성공입니다.

 

그러나 저희의 인생과 같이 언제나 성공만은 할 수가 없습니다. 한 번씩 실패를 경험해야 그다음의 성공을 준비할 수 있습니다. 그러면 만약 배열 속에서 찾는 값이 존재하지 않으면 어떻게 될까요? 이번에는 위의 배열에서 숫자 5를 한 번 찾아보도록 하겠습니다.

 

int 정수형 배열에서 선형 검색 알고리즘을 활용하여 숫자 5를 검색하는 과정 - 검색 실패

예상한 결과와 같이 위의 배열에는 찾고자 하는 값인 5가 존재하지 않기 때문에 배열 인덱스의 값을 모두 찾아보아도 그 값이 존재하지 않는다는 것을 알 수 있습니다. 즉 한 칸씩 옮기면서 구성하던 인덱스의 값이 배열의 크기와 값이 같게 되었으며 검색 실패입니다.

🎉 선형 검색의 종료 조건은?

위의 예시를 통해 이제는 선형 검색에 대한 개념이 잡혔을 것이다. 그럼 선형 검색의 종료 조건은 무엇인가? 위의 예시에 답이 존재한다. 선형 검색의 종료 조건은 간단히 말해 검색할 값이 존재하는 경우, 검색할 값이 존재하지 않는 경우 이렇게 2개로 구분할 수 있다.

 

선형 검색의 종료 조건

1. 검색할 값과 같은 요소를 발견한 경우 (검색 성공)

2. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 (검색 실패)

또한 선형 검색의 종료 조건 1과 2를 판단하는 선형 검색의 검색 판단 횟수는 배열의 요솟수가 n개일 때 평균 n/2회입니다.

💻 선형 검색을 구현해보자!

지금까지 선형 검색의 개념, 구조, 종료 조건에 대해서 알아보았습니다. 이번에는 위에서 배운 내용을 바탕으로 간단한 프로그램을 만들어보겠습니다. Java 언어로 구성을 할 것이며 Java 언어뿐만이 아니라 다른 언어로도 똑같이 프로그램 구현이 가능합니다.

public class SeqSearch {
    public static Scanner scanner = new Scanner(System.in);
    public static void main(String[] args) {
        System.out.print("요솟수를 입력해주세요 : "); int input = scanner.nextInt();
        int[] arr = new int[input];
        setArr(arr);

        System.out.print("배열에서 검색할 값을 입력해주세요 : "); int searchInput = scanner.nextInt();
        int index = findArr(arr, searchInput);

        if(index == -1) System.out.println("찾으시는 값은 배열에 존재하지 않습니다.");
        else System.out.println("찾으시는 값은 배열 x[" + index + "]에 존재합니다.");
    }
    public static void setArr(int[] arr){
        for(int i = 0; i < arr.length; i++){
            System.out.print("배열의 x[" + i + "]의 값을 입력해주세요 : ");
            arr[i] = scanner.nextInt();
        }
    }
    public static int findArr(int[] arr, int searchInput){
        for(int i = 0; i < arr.length; i++) if(arr[i] == searchInput) return i;
        return -1;
    }
}

선형 검색을 이용한 간단한 프로그램 구현 모습

먼저, 사용자에게 배열의 요소수 즉 크기를 입력받고 그 크기에 맞게 int 정수형 배열을 생성하였습니다. 그 후 배열의 요소를 각각 입력을 하여 배열에 저장을 하였습니다. 배열에 요소를 모두 입력을 받았다면 최종적으로 사용자에게 배열에서 검색할 값을 입력받습니다. 그러면 프로그램 내에서는 선형 검색 알고리즘을 통해 배열의 인덱스 0번째부터 그 값을 순차적으로 검색하기 시작합니다.

 

만약 사용자가 입력한 값이 배열에 존재한다면 그 값의 인덱스 값을 반환하고 만약 배열의 처음부터 끝까지 모두 검색을 수행하였으나 값이 존재하지 않는다면 findArr 매서드의 for문을 탈출하여 최종적으로 숫자 -1을 반환하여 검색 실패를 의미하고 있습니다.

🎯 보초 법이 대체 뭐야?

보초 법은 선형 검색 알고리즘을 활용할 때 함께 사용을 한다면 효율성이 있는 기술?, 방법?이라고 할 수 있다. 위에서 선형 검색 알고리즘의 종료 조건은 총 2가지였다. 어떻게 보면 적다고 할 수 있지만 종료 조건을 검사하는 비용은 결코 무시할 수 없다. 그래서 그 종료 조건을 검사하는 비용을 줄여주기 위한 방법으로 보초 법을 활용하면 된다. 아래의 그림을 통해 보초법을 설명하겠습니다.

 

기존의 배열에 보초 값이 추가 되어있는 모습입니다. (기존의 데이터 검색 성공)

기존의 배열에 보초 값이 추가 되어있는 모습입니다. (보초 데이터 검색 성공)

보초 법을 사용하는 간단한 방법을 알려드리도록 하겠습니다. 기존의 배열에서 요솟수를 1을 추가하여 배열 마지막 인덱스에 사용자가 찾는 값을 저장해둡니다. 그러면 선형 검색을 통해 순차적으로 값을 찾게 될 것이며 검색 조건 2번 배열에서 값을 발견하지 못하고 배열의 끝을 지나간 경우는 이제 존재하지 않게 될 것입니다. 즉 검색 실패의 경우는 앞으로 존재할 수가 없는 것을 알 수 있습니다.

 

최종적으로 저희는 이제 선형 검색을 통해 찾은 값이 기존의 배열에 존재하는 데이터인지 또는 보초로 설정해둔 특정의 값인지 구별만 할 수 있도록 코드를 작성한다면 선형 검색 알고리즘의 종료 조건을 검사하는 비용을 50%나 줄일 수 있어 더욱 효율적입니다.

📆 보초법을 사용해보자!

아래의 코드는 위에서 예기한 것과 같이 사용자로부터 배열의 크기를 입력받은 것에서 1 크게 배열을 구성합니다. 그 후 배열 마지막 인덱스에 사용자가 찾는 값을 추가합니다. 그렇다면 검색 실패는 절대 발생하지 않고 매번 검색 성공을 합니다. 그러면 이제 그 검색 성공의 값이 기존의 배열에 데이터 값인지 또는 보초의 값인지 판단을 해야 합니다. 판단의 기준은 인덱스 값으로 판단할 수 있습니다.

 

만약 그 인덱스의 값이 배열의 마지막 인덱스라면 찾은 값은 보초의 값이며 -1을 반환합니다. 그러나 그렇지 않다면 기존의 배열에 데이터 값이므로 그 값의 인덱스를 전달합니다. 전달받은 값을 통해 저희는 찾은 값의 검색 성공, 실패 여부를 확인할 수 있습니다.

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

        System.out.print("요솟수를 입력해주세요 : "); int num = scanner.nextInt();
        int arr[] = new int[num + 1];

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

        System.out.println("검색할 값을 입력해주세요 : "); int ky = scanner.nextInt();
        int idx = seqSearchSen(arr, num, ky);

        if(idx == -1) System.out.println("배열에서 검색하신 값은 존재하지 않습니다.");
        else System.out.println(ky + "은(는) 배열 x[" + idx + "]에 존재합니다.");
    }

    public static int seqSearchSen(int arr[], int num, int key){
        int i = 0;
        arr[num] = key;

        while(true){
            if(arr[i] == key) break;
            i++;
        }
        return i == num ? -1 : i;
    }
}

선형 검색과 보초법을 활용한 간단한 프로그램 예시

👍 글을 마치며

오늘은 검색 알고리즘에서의 대표적인 알고리즘 선형 검색 알고리즘에 대해서 알아보았습니다. 선형 검색은 알고리즘에서 가장 기본적인 알고리즘이라고 할 수 있습니다. 그러한 만큼 꼭 공부를 열심히 해두어야 하고 앞으로 쓸 일이 많을 것입니다. 또한 선형 검색에 이어서 배운 보초 법은 선형 검색에서의 종료 조건을 한 개 줄여주면서 값의 검색 비용을 줄여줍니다. 앞에서도 강조를 했듯이 어떠한 문제를 해결하기 위해서는 많고 다양한 알고리즘이 있습니다. 하지만 그렇게 많은 알고리즘 속에서 그 문제를 해결하기 위해 다양한 방면에서 알고리즘을 판단하여 가장 효율적인 알고리즘을 선택하여서 문제를 수행하는 것이 가장 중요하다는 것을 기억해야 합니다.

 

참고 : Do it 자료구조와 함께 배우는 알고리즘 입문 자바 편