탐색 알고리즘(선형, 이진, 해시)

선형 탐색(Linear Search)

---

선형 탐색은 가장 간단한 탐색 방법이라고 할 수 있다.

위와 같은 배열에서 10을 찾으려고 할 때, 선형 탐색에서는

가장 왼쪽 칸부터 한 칸 씩 오른쪽으로 가면서 각각의 값을 비교한다.

 

선형 탐색의 경우 단순하며, 이해하기 쉽고 찾는 대상이 앞쪽에 있으면 빠르게 찾을 수 있겠지만

찾는 대상이 뒤쪽에 있으면 그만큼 찾는 속도가 느려진다.

또한 각각의 값들을 일일이 확인해야 하기 때문에 값이 많아질수록 시간이 더 오래걸리게된다.

 

Big-O표기법으론 O(n)으로 볼 수 있다.

fun main(){
    var arr = arrayOf(1, 5, 63, 51, 8, 97, 13, 15, 22, 30)
    var cnt = 0
    for(i in arr){
        if(i == 15) break
        cnt++
    }
    println(cnt)
}

위처럼 간단하게 코드로 구현할 수 있는데, 빠르면 단 한번만에 값(1)을 찾을 수 있지만

최악의 경우(30을 찾을 경우) 배열의 크기만큼 for문을 돌아야 하기 때문에 비효율적이다.

 

이진 탐색(Binary Search)

---

이진 탐색의 경우 사용하기전에 전제 조건이 필요하다.

그 조건은 탐색할 배열등의 데이터들이 미리 오름차순이나 내림차순으로 정렬이 되어있어야 한다는 점이다.

 

정렬된 배열에서 이진 탐색이 동작하는 방식은 아래와 같다.

여기선 배열이 내림차순으로 정렬되있다고 가정해보도록 하자.

1. 먼저 배열의 중간 값이 찾는 값과 일치하는지 확인한다.
2. 일치하지 않을 경우 내가 찾으려는 값과 중간 값의 대소를 비교한다.
3. 만약 내가 찾으려는 값이 중간값보다 크면 해당 배열의 왼쪽 반만 취한다.
4. 취한 배열을 가지고 다시 1번부터 값을 찾을 때 까지 반복한다.

그림을 보고 설명해보자면 위 배열에선 숫자들이 오름차순으로 정렬되어있다.

우리가 여기서 8을 찾고싶다면, 가장 먼저 5나 6을 8과 비교하여 값이 일치하는지 확인한다.

 

중간값이 우리가 찾는 값이 아니라면 둘의 대소를 비교한다.

8은 5보다 크기 때문에 배열의 오른쪽 반을 잘라서 다시 위의 과정들을 반복한다.

위 배열에서 이진 탐색을 사용할 경우 단 두 번 만에 8이라는 값을 찾을 수 있다.

fun main(){
	var arr = arrayOf(1, 5, 8, 13, 15, 22, 30, 51, 63, 97)
    var target = 13
    var low = 0
    var high = arr.lastIndex
    var mid = 0;

    while (low <= high) {
        mid = (low + high) / 2
        
        if(arr[mid] == target) break
        else if(arr[mid] > target) high = mid - 1
        else low = mid + 1
    }
    println(mid)
}

평균적으로 이진 탐색이 선형 탐색보다 탐색 속도가 더 빠르다.

이진 탐색법의 경우 Big-O표기법으로 O(logN)으로 나타낼 수 있다.

해시 탐색(Hash Search)

---

위의 두 방법의 경우 배열 내의 어느 장소에 어떠한 데이터가 있는지 알지 못하는 상태에서 탐색한다.

하지만 해시 탐색의 경우 데이터와 저장 장소를 미리 연계해 둠으로써

매우 짧은 시간에 값을 찾을 수 있도록 하는 알고리즘이다.

 

기본적인 아이디어는 데이터의 값과 같은 index위치에 넣어두면

다른 추가 작업 없이 한 번에 찾을 수 있다는 생각이다.

 

위의 그림으로 보면 첫 번째 장소에 1이 들어있고 9번째 장소에 9가 들어있으니

찾을 값을 index값에 대입하면 해당 값을 바로 찾을 수 있다.

(실제로는 index는 0부터 시작이니 값도 0, 1, 2, 3, 4, 5순으로 들어가야 한다.)

 

그런데 여기서 문제는 만약 39라는 값을 해시 탐색을 사용하는 배열에 집어넣는다고 했을 때

데이터가 39 단 하나만 들어있어도 우리는 크기 39의 배열을 선언해야 하기 때문에 그만큼 메모리의 낭비가 생긴다.

 

그래서 해시 탐색의 경우 해시 함수를 사용해 제한된 배열 크기에서 index값을 결정한다.

예를 들어 39와 73이라는 값을 크기가 5인 배열에 집어넣고 싶다면

각 값들을 5로 나눈 나머지 값의 index에 데이터를 삽입할 수 있다.

 

39의 경우 5로 나누면 나머지가 4이며, 73의 경우 나머지가 3이기 때문에

아래와 같이 들어갈 수 있다.

그런데 여기서 또 문제가 생기는데, 만약 배열에 삽입하는 값이 39와 74라고 생각해보자.

그러면 39와 74를 나눈 값이 4로 동일해져버린다.

 

이런 상황을 해시 충돌이라고 하는데, 이 경우에는 몇 가지 방법을 통해서

나중에 들어온 데이터를 적절하게 배열에 삽입하도록 되어있다.

해당 방법들에 대해선 이 글에선 자세한 생략하도록 하고,

만약 해당 자리에 값이 있을 경우 그 다음 칸에 저장하는 방법을 사용하도록 하겠다.

fun main(){
    var arr = arrayOfNulls<Int>(5)
	
    insert(arr, 10)
    insert(arr, 39)
    insert(arr, 73)
    insert(arr, 23)
    
    arr.forEach{ println(it) }
    
    find(arr, 73)
    find(arr, 23)
    find(arr, 1)
}

fun insert(arr: Array<Int?>, value: Int){
    var idx = value % arr.size
    
    if(arr[idx] != null){
        for(i in 1 .. arr.size){
            println("해시 충돌")
            idx++
            if(idx >= arr.size) idx %= arr.size
            if(arr[idx] == null){
                arr[idx] = value
                break
            }
        }
    }else{
        arr[idx] = value
    }
}

fun find(arr: Array<Int?>, value: Int){
    var idx = value % arr.size
    
    for(i in 0 .. arr.size){
        if(arr[idx] == value){
            println("indx = ${idx}")
            return
        }
        idx++
        if(idx >= arr.size) idx %= arr.size
    }
    println("값을 찾지 못했습니다.")
}

위의 코드를 실행할 경우 23을 삽입할 떄 총 3번의 해시 충돌이 일어나는데,

먼저 23의 index는 처음에 3으로 결정된다.

하지만 3자리에는 이미 73이 들어있기 때문에 index를 1 증가시킨다.

 

그 후 4자리에도 이미 39가 들어있기 때문에 index를 증가시켜 5가 되는데,

index는 4를 넘어가면 안되기 때문에 다시 0으로 돌아간다.

0자리에도 마찬가지로 10이 있기 때문에 최종적으로 다음 자리인 1번 자리에 삽입된다.

 

해시 탐색의 경우 평균적으로 Big-O표기법으로 O(1)로 나타낼 수 있다.

하지만 해시 충돌이 일어날 경우 O(n)이 될 수 있다.