검색 알고리즘

임준영·2021년 4월 23일

검색 알고리즘에 대해서 가볍게 공부해봤습니다. 그 중에서도 배열과 Linked List에 대해서 자세히 알아 보았고, 주로 어떤 용도에서 활용할 수 있을지도 알게 되어서 좋았습니다.

1. 정적 Array

정적 Array가 처음에 뭐지 싶었는데 찾아보니… 그냥 배열을 정적 Array라고 부르는거 였습니다.

보통 아래 그림처럼 고정된 크기와 동일한 자료형만 저장할 수 있는 자료의 집합을 배열이라고 합니다.

배열의 모습

배열의 가장 큰 장점은 인덱스만 알고 있으면 바로 원하는 키 값이 들어있는 배열의 요소에 바로 접근할 수 있다는게 장점이라고 생각합니다.

하지만 장점이 있으면 단점이 존재하기 마련입니다. 중간에 배열의 요소를 삭제하는 작업을 수행하면 배열의 요소들을 밀어넣는 작업을 하기 때문에 추가적인 비용이 들어갈 수 있다는 점 입니다.
또 한 배열의 생성할때 크기를 정해줘야 하기 때문에 어떤 크기를 가진 데이터가 들어올지 모르는 상황에서는 융통성이 많이 부족한 친구입니다.

배열의 특징

검색속도가 빠르다.

크기가 고정되어 있다.

배열 요소의 추가, 삭제를 하는데 추가적인 오버헤드가 발생한다.

2. 동적 Array

이와 대조적으로 데이터의 크기와 상관없이 융통성 있게 크기를 추가할 수 있는 친구가 있는데… 대표적으로 Linked List라는 녀석이다… 대학교 시절에 C언어를 공부할때 가장 어렵게 느껴져서 대충 들어보기만 했지만 알고리즘 입문(자바편)을 공부하면서 조금 친해질(?) 수 있었습니다.

Linked List

Linked List는 노드라고 불리는 작은 메모리 영역안에 데이터 필드와 링크영역이 존재하는데 이 데이터 필드는 실제 데이터 값이 저장되어있고 링크는 다음 노드의 주소 값을 저장하는 공간입니다.

실제로 Linked List라는 개념을 알고리즘 투게더 with 거니라는 Youtube 채널을 보면서 쉽게 이해 할 수 있었습니다. 정적 Array와 동적 Array에 차이에 대해서 자세히 이해가 안간다면 이 채널을 보는 것을 추천드립니다. Linked List 또한 단점이 존재하는데 배열과 다르게 Linked List는 원하는 키 값을 찾기 위해서는 링크를 타야하기 때문에 검색속도가 느리다는 단점이 존재합니다.

마치 학교 선생님이 반에 학생들에게 누가 창문을 깼는지 영희라는 학생에게 물어보면 영희는 철수를 손가락으로 가르키고, 철수는 지수를 가르키는 것처럼 각각의 학생들이 앉아있는 책상 위치가 주소라고하면 링크는 각각의 학생의 책상 위치를 가르킨다고 보면 됩니다. 하지만 선생님이 결국 누가 창문을 깼는지 알기 위해서는 학생들이 각각 가르키는 손가락을 확인해야 범인을 알 수 있습니다.

대신에 배열과 다르게 중간의 어떠한 값을 가지고 있는 노드를 삭제한다면 앞에 있는 노드의 링크 주소를 삭제하려는 노드의 뒤쪽 노드의 주소로만 변경해주기만 하면 되기 때문에 추가, 삭제가 용이하다는 장점이 있습니다.

또한 링크 공간이 4byte씩 메모리 공간을 소모하기 때문에 같은 데이터 개수를 저장하는 배열보다는 메모리를 많이 먹는다는 단점이 있습니다.

Linked List 특징

데이터 크기에 의존적이지 않고 융통성 있게 데이터추가 가능

키 값을 찾을 시에는 링크를 통해서 해당 노드의 값을 찾기 때문에 검색속도가 느리다.

앞 뒤 노드들만 연결해주기만 하면 노드의 추가, 삭제가 용이하다.

Linked List의 종류

Single Linked List

Doubly Linked List

Circular Linked List

앞에서 언급한것처럼 노드에는 데이터 필드와 링크라는 영역이 존재하는데, 이 링크의 구조에 따라서 Linked List의 종류가 달라집니다.

위에서 그림은 노드에 링크를 하나씩만 존재하는 Single Linked List 입니다. 가장 많이 본 녀석이죠… 그 다음에 노드에 링크가 2개씩 존재하는 녀석이 Doubly Linked List입니다. 말 그대로 더블이라는 표현에서 보듯이 위의 링크가 다음 노드의 주소를 가지고 있고 아래 링크는 앞의 노드의 주소를 가지고 있어서 서로 연결된 모습을 보입니다.

Doubly Linked List

맨 처음 나오는 노드를 헤더라고 부르고,맨 마지막 노드를 테일이라고 부릅니다. 헤더와 테일은 링크는 null을 가지고 있습니다. 즉 아무것도 가리키고 있지 않습니다.

이제 그 다음에 나오는 Linked List가 환영 연결 리스트라고 불리는 녀석입니다.
마찬가지로 노드당 링크를 2개씩 가지고 있지만 위에 Doubly Linked List랑 구별되는 특징은 헤더와 테일이 서로 연결되어 있다는 특징이 있습니다.

Circular Linked List

헤더의 한쪽 링크는 테일의 주소 값을 가지고 있고,

이제 위의 개념들을 토대로 선형검색 코드를 간단하게 구현해하여 리뷰하겠습니다.

3. 선형 검색

선형탐색은 처음부터 하나하나 비교하여 검색하는 방법으로 구현하기 쉽고, 정렬이 안 되어있어도 된다는 장점이 있습니다. 대신 하나하나 찾으면서 검색하기 때문에 시간이 오래 걸린다는 단점이 있습니다.

Java언어를 사용하여 배열에 원하는 키 값을 찾는 코드입니다.

public class SeqSearch {

    public static int seqSearch(int[] a, int n, int key){
        int i=0;
        a[n] = key; //배열의 마지막 인덱스에 원하는 키값을 넣는다.

        //배열의 크기보다 작거나 같을때까지 반복...
        for (i=0; i <= n; i++) {
            if(a[i] == key)  배열의 요소와 키 값이 같으면 for문을 탈출!!
                break;
        }
        return i==n ? -1:i; // i의 값이 배열의 크기와 같다면 -1 리턴, 같지않으면 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+1];  //보초법이라 해서 원하는 배열의 크기 +1만큼 생성합니다.

        for (int i=0; i < num; i++) {
            x[i] = sc.nextInt();
        }

        System.out.println("검색할 값: ");
        int key = sc.nextInt();  //키 값을 입력받는다.
        int idx = seqSearch(x, num, key);

        if (idx == -1)  // 배열에 원하는 키 값이 존재하지 않을때 -1을 리턴
            System.out.println("그 값의 요소가 없습니다.");
        else
            System.out.println(key +"은 x[" + idx +"]에 있습니다.");
   }
}

위의 코드는 보초법 방식으로 배열에서 원하는 키 값을 찾는 검색 알고리즘 입니다.
seqSearch 메소드를 유틸성으로 이용하기 위해서 Static 영역에 생성하여 원하는 키값을 찾는 메서드입니다.

원하는 크기의 배열을 선언과 찾고자 하는 키값을 seqSearch() 메서드의 매개변수로 넘겨줍니다.

여기서 배열을 힙 영역에 생성할 때 원하는 크기의 +1 만큼 증가시켰습니다. 왜 이렇게 선언하는 이유는 실제로 보초법을 사용하지 않을시에는 예를 들어서 소스코드가 아래와 같다고 한다면

static int seqSearch(int[] a, int n, int key){

    int i = 0;

    while (true) {
        if (i == n)
            return -1;
            
        if (a[i] == key)
            return i;
        i++; 
    }
}

i의 값에 따라서 분기문이 2개로 나뉘게 됩니다.

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

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

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

위에서 배열을 원하는 크기의 +1만큼 생성하였습니다. 검색하기 전에 검색하고자 하는 키 값을 맨 끝 요소에 저장합니다. 이때 저장하는 값을 보초라고 합니다.
이렇게 코드를 작성하면 원하는 값이 원래의 데이터에 존재하지 않아도 보초인 마지막 인덱스까지 검색하면 종료가 성립합니다. 이렇게 하면 조건분기인 종료조건1이 없어도 됩니다. 보초는 반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 합니다.

4. 이진 검색

마지막으로 이진 검색법에 대해 리뷰하겠습니다. 이 알고리즘은 선형탐색과 다르게 반씩 범위를 나누어 가면서 분할정복하여 탐색하는 방법이고, 키 값으로 이미 정렬되어 있다는 것입니다. 이진검색은 선형탐색보다 검색속도가 더 빠르다는 장점이 있습니다.

속도가 빠르다

자료구조 안 값들이 정렬되어있어야 한다.

예를 들어서 원하는 키 값이 8인경우 (n-1) / 2 = 3, a[3] = 12를 기준값으로 잡고 키 값과 비교를 합니다. 키 값이 작기 때문에 a[3]부터 검색 범위를 버리고 (n-1) / 2 = 1 a[1] = 3을 기준 값으로 잡습니다. 마찬가지로 8 > 3이기 때문에 a[1]부터 밑에 범위는 버리고 시작하면 남은 인덱스는 a[2]만 남게되고 키 값과 일치하게 되여 해당 인덱스를 리턴하면 됩니다.

이런 방식으로 이진탐색은 검색범위를 계속 좁히면서 원하는 키 값을 찾는 알고리즘 입니다.
그렇기 때문에 속도가 빠를 수 밖에 없습니다. 또 한 검색 범위를 절반씩 좁히기 위해서는 배열요소 값이 정렬되어 있어야 하는 번거로움이 존재합니다.

위의 책 그림은 이진 검색을 이해하는데 좋은 예인거 같아서 첨부하였습니다. 마찬가지로 건이님 채널에서 배웠습니다. 넘나 유익한 채널인것..

만약 선생님이 총 500 페이지인 국어책의 370페이지를 펼치라고 하였을때 학생들은 대충 절반인 250 페이지를 펼친 다음에 찾고자 하는 페이지와 비교하여 작으면 1~250 페이지의 범위는 버리고 250~500 페이지의 범위에서 해당페이지를 찾습니다. 이런식으로 범위를 나누어가면서 내가 찾고자하는 패이지를 찾는게 이진탐색 방법입니다. 참 쉽죠잉~

다음에는 이진검색을 Java코드로 살펴보겠습니다.

이진검색 예제 코드

public class BinarySearch {

    public static int binSearch(int[] a, int n, int key){
     
        int pl = 0;     //배열의 첫번째 요소 a[0]
        int pr = n - 1;   //배열의 마지막 요소 a[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.println("요솟수: ");
        int num = sc.nextInt();

        int[] x = new int[num];
        System.out.println("오름차순으로 입력하세요.");

        System.out.println("x[0] : ");
        x[0] = sc.nextInt();

        //이진검색은 사전조건이 정렬되어 있어야 합니다.
        for (int i=1; i < num; i++) {
            do {
                System.out.println("x[" + i +"] : ");
                x[i] = sc.nextInt();
            } while(x[i] < x[i - 1]); //배열의 i < i - 1번째 요소보다면 작으면 반복
        }

        System.out.println("검색할 값 : ");
        int key = sc.nextInt();

        int idx = binSearch(x, num, key); // 이진검색 메소드

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

        }
    }
}

위의 소스코드에서 do while문을 이용하여 오름차순으로 정렬하고 있습니다.
원하는 키 값과 배열의 길이, 배열의 참조 값을 binSearch() 메서드의 매개변수로 넘겨주면서 이진검색을 하고 있습니다.

binSearch() 메서드는 파리미터로 받은 키 값과 배열의 첫번째 요소와 마지막 요소를 가지고 있는 로컬변수 pl, pr, pc를 이용하여 기준 값을 구하고 키 값과 기준 값을 비교하며 범위를 절반씩 좁히면서 검색을 수행합니다. 이렇게 좁히다 보면 결국 pl과 pr은 만나게 되고 pl이 pr보다 크거나 같으면 do while문이 종료가 되고 -1을 리턴하여 검색이 실패한걸 알 수가 있습니다.

검색 알고리즘을 정말 모래알 같이 쬐끔… 맛보면서 느낀점은 데이터 크기에 따라서 배열을 사용할지 Linked List를 사용할지 어느게 더 좋은 자료구조인지 따지기 보다는 매모리 효율에 맞게 사용하는게 가장 최적의 방법이지 않을까 조심스럽게 생각해봅니다.