[📚누구나 자료구조와 알고리즘] 2. 알고리즘이 중요한 까닭 - 선형검색과 이진검색

이전 포스팅에서는 자료 구조의 기본 연산과, 자료 구조에 따라서 각 연산의 효율성이 달라질 수 있다는 것을 다루었다.

자료 구조의 기본 연산과 속도 측정 (시간복잡도)의 이해

 

이번 포스팅에서는 동일한 자료 구조에서도 더 효율적인 결과를 낼 수 있는 코드(알고리즘)를 사용할 수 있는 방법을 다루어보려고 한다. 

 

알고리즘

Algorithm. 알고리즘은 어떤 일을 수행하기 위한 명령어들의 집합이다.

 

카카오톡 보내기 알고리즘이 있다고 가정한다면, 이 알고리즘은 대략적으로 다음과 같은 명령어들의 집합일 것이다. 

   1. 카카오톡을 켠다

   2. 메세지를 수신할 상대와의 채팅방을 연다

   3. 메세지를 쓴다

   4. 전송 버튼을 누른다 

 

컴퓨터 알고리즘도 이와 같이 "특정 과제를 달성하기 위해 컴퓨터에 제공되는 명령어 집합" 이다
(제이 웬그로우, 『누구나 자료구조와 알고리즘』, 심지현, 길벗, 2011, p50)

 

현실에서도 문제를 해결하기 위한 서로 다른 방법들이 존재하듯, 컴퓨터 알고리즘에서도 과제를 달성하기 위한 수십가지의 명령어 집합이 존재할 수 있다. 이때, 어떤 알고리즘은 다른 어떤 알고리즘보다 훨씬 빠르다. 동일한 문제를 해결하는 것이라면 당연히 빠른, 즉 효율적인 알고리즘을 선택하는 것이 중요할 것이다. 

 

이제 여러 알고리즘과 각 알고리즘의 효율성에 대해 살펴보도록 하자. 

 

정렬된 배열 

정렬된 배열이라는 자료 구조를 통해 기본 알고리즘들을 다뤄보고자 한다. 

 

정렬된 배열은 일반적인 배열과 거의 동일하다. 차이점은 배열의 모든 원소들이 정렬(sorted) 되어있어야 한다는 것이다. 숫자로 구성된 배열이라고 한다면 [1,10,5,20,15] 가 아닌 [1,5,10,15,20] 처럼 오름차순 순으로 되어있어야 한다. 그렇다면 정렬된 배열에서 기본 연산의 효율성은 어떨까? 

 

정렬된 배열의 삽입

정렬된 배열에서 값을 삽입할 때는, 정렬이 깨지지 않는 올바른 위치에 새 값을 삽입해야 한다. 

즉, 검색을 통해 올바른 위치를 찾고, 필요 시 원소를 이동해서 삽입할 자리를 만들고나서 원소를 삽입하는 단계를 거쳐야 한다. 

 

위에서 예를 든 [1,5,10,15,20] 배열에서 17이라는 값을 삽입하려는 경우를 생각해보자. 

 

삽입할 자리를 찾기 위해 첫번째 원소부터 하나씩 확인해본다(선형검색). 1은 17보다 작으므로 다음 원소를 확인한다, 5, 10, 15 모두 17보다 작다. 20은 17보다 크므로 20의 앞자리가 17이 들어갈 자리임을 알 수 있다. 5개 원소를 확인하느라 5단계가 소요되었다. 20 앞 자리를 비우기 위해서는 20을 한 칸 뒤로 옮긴다. 여기서 한 단계가 소요된다. 그리고 값을 삽입하는데 한 단계가 소요된다. 즉, 최종적으로 5+1+1= 7 단계가 소요되었다. 

 

(정렬되지 않은) 일반적인 배열의 삽입에서는 원소가 삽입되는 위치에 따라 필요한 단계가 달라졌는데 (앞쪽에 삽입할 수록 오래 걸림), 정렬된 배열에서도 삽입되는 원소의 위치에 따라 단계가 달라질까?

 

정답은 그렇지 않다. 배열의 원소 갯수가 N개라면, 필요한 단계는 항상 N+2 단계이다. 새 원소를 삽입해야 하는 위치가 앞쪽일 수록 검색의 수는 줄어들고 이동의 수는 늘어난다. 뒤쪽일 수록 검색의 수는 늘어나지만 이동의 수는 줄어든다. 이해를 돕기 위해 아래와 같이 간단하게 그림을 그려보았다. 

전체 N개 원소를 가진 배열이 있을 때, 원소가 M번째 원소 앞에 삽입되어야 한다고 하면, 검색해야 하는 원소의 갯수는 M개, 이동해야 하는 원소의 갯수는 N - M + 1개 이다. 원소를 삽입하는 1단계를 모두 더하면 최종적으로 M + (N-M+1) + 1 = N+2 단계가 되는 것이다.  

 

일반 배열에서 삽입에서 최악의 시나리오는 N+1 단계인데, 정렬된 배열에서 삽입은 언제나 N+2 단계이다. 삽입 연산에서는 분명히 정렬된 배열이 일반 배열보다 비효율적이지만, 정렬된 배열이 강력한 이유는 다른 연산에서는 정렬된 배열이 일반 배열보다 훨씬 더 효율적이기 때문이다. 

 

정렬된 배열의 검색 - 선형검색

[1,5,2,8,3]라는 (정렬되지 않은) 일반 배열이 존재할 때, 4라는 값이 이 배열에 있는지를 검색해보는 상황을 생각해보자. 

 

보다시피 4이라는 값은 배열에 존재하지 않는다. 따라서 이 배열의 모든 원소 5개를 다 검색해봐야 4가 없다는 사실을 알 수 있다. 즉, 일반적인 배열에서 선형 검색(linear search) 방법으로 존재하지 않는 값을 검색할 때 모든 원소를 다 찾아봐야한다. 

 

💡 일반적인 배열에서 선형검색을 수행하는 javascript 함수를 생성해보면 아래와 같다. 

 

function linear_search(array,search_item) {
    let index = 0 ;
    for (i=0; array[i]!==search_item; i++) {
        index = i+1;
        if (index == array.length) {
            return "no search_item"
        }
    }
    return index
}

 

만약 이 배열이 정렬된 배열이라면 어땠을까? [1,2,3,5,8] 로 정렬된 형태의 배열이었다면, 1,2,3,5 까지만 검색해보더라도 4가 없다는 사실을 알 수 있다. 이 배열은 정렬된 배열이기 때문에 이미 4보다 큰 5를 발견한 순간 (더 검색을 해보지 않더라도) 4가 없다는 사실을 알 수 있기 때문이다. 따라서 정렬된 배열에서는 선형 검색 방법으로 검색할 때, 검색하려는 값 또는 그보다 더 큰 원소를 발견한 순간 검색을 멈출 수 있다. 

 

선형검색의 경우, 정렬된 배열에서 일반적인 배열보다는 더 빠르게 검색이 끝나는 케이스가 존재한다. 다만, 최악의 상황에서는 (찾으려는 값이 맨 끝 또는 그보다 더 클 때) 결국 모든 원소를 다 검색해봐야 하므로 N개의 원소가 있는 배열을 검색했을 때 정렬된 배열과 일반 배열 모두 N 단계가 걸린다. 

 

정렬된 배열의 검색 - 이진검색 

하지만 정렬된 배열이 강력한 이유는, 선형검색이 아닌 이진검색(binary search)이라는 검색 방법을 사용할 수 있기 때문이다.

 

1부터 9까지의 자연수를 담은 정렬된 배열 num = [1,2,3, ..., 8,9] 에서 7이라는 값을 검색해본다고 가정해보자. 

 

선형검색을 사용하면 1부터 순서대로 하나씩 검색해 나가므로 총 7단계를 거쳐야 한다. 

이진검색을 사용하면 어떤 일이 벌어지는지 확인해보자.

 

1단계: 중간값을 찾는다. 배열의 길이(원소의 갯수)는 9이므로 중간값은 5번째 값인 5이다.

5은 찾고자 하는 값 7보다 작으므로 0~4번 인덱스는 제거한다.

 

2단계: 다시 중간값을 찾는다. 남은 원소의 갯수는 4개이므로 2 또는 3번째 값이 중간 값이다. 두번째 값을 검색한다. 둘 중 어떤 것을 선택해도 상관없다  두번째 값은 7이고, 7이 찾고자 하는 값이므로 검색을 멈춘다.

 

선형검색에서는 7을 찾을 때 7단계가 걸렸지만, 이진 검색에서는 2단계만 걸렸다. 두 검색 모두 9를 검색하는 경우가 가장 많은 단계를 거치게 되는 최악의 시나리오 상황인데, 최악의 시나리오로 비교했을 때도 선형검색은 9 단계를 거치고, 이진 검색은 4단계가 걸린다. 

 

💡 정렬된 배열에서 이진 검색을 수행하는 javascript 함수를 생성해보면 아래와 같다. 

 

 function binary_search(array,search_item) {
                let min_index = 0
                let max_index = array.length -1 
                let length = max_index-min_index+1
                let mid = length%2 ==0 ? length/2 -1 : Math.floor(length/2)
                let mid_index = min_index + mid

                while (min_index <= max_index) {
                	let mid_value = array[mid_index] 
                    if (mid_value == search_item) {
                        return mid_index
                    }
                    else if (array[mid_index] > search_item) {
                        max_index = mid_index -1 
                    }
                    else if (array[mid_index] < search_item) {
                        min_index = mid_index +1
                    }
                    length = max_index-min_index+1
                    mid = length%2 ==0 ? length/2 -1 : Math.floor(length/2)
                    mid_index = min_index + mid
                }
                return "no search item"
            }

 

중요한 점은, 이진 검색은 정렬된 배열 자료구조에서만 사용할 수 있다는 점이다. 일반 배열에서는 이진검색을 사용할 수 없다. 즉 이진검색을 사용할 수 있다는 점이 정렬된 배열의 장점 중 하나이다. 

 

이진 검색의 진정한 파워는 배열의 원소가 많을 때 나타난다. 이진 검색에서는 각 단계마다 전체 원소의 반을 제거해낸다. 원소가 1만개라면 첫 단계에서 이미 5천개를 제거해버린다. 각 단계에서 절반씩을 제거하기 때문에 이진검색에서는 배열의 원소 갯수가 두 배로 늘어날 때 이진검색 단계는 1개만 늘어난다. 

 

이와 같이 일반 배열과 비교할 때 정렬된 배열에서 삽입은 좀 더 오래걸리지만, 검색에서는 뛰어난 성능을 보인다. 따라서 삽입보다는 검색이 더 많이 이루어지는 소프트웨어를 만들 때는 정렬된 배열과 이진검색을 활용하는 것이 좋을 것이다. 

 

---

참고문헌:  제이 웬그로우, 『누구나 자료구조와 알고리즘』, 심지현, 길벗, 2011

 

누구나 자료 구조와 알고리즘 - YES24