Binary Search vs Linear Search

정말 노마드 코더님은 비전공자들에게 한줄기 빛과 같다....

그동안 정보처리기사, Sqld 등등.. 자주 나오는 개념인 이진 탐색(Binary Search)!! 자격증 따면서 글로만 읽었을 때에는 이게 왜 중요한지 이해가 안갔었는데 오늘 영상을 보니 이해가 한방에 되었고 정말 중요한 알고리즘이라는 것을 느꼈다.

오늘도 역시 노마드 코더님의 강의를 보고 블로그 글을 포스팅함으로써 개념을 정리해보려고 한다.

 

 

노마드 코더 강의 출처: https://www.youtube.com/watch?v=WjIlVlmmNqs

 

 

 

오늘은 왜 알고리즘이 중요한지 배우기 위해서 같은 작업을 수행하는 알고리즘 2개를 비교해보겠다.

배열 안에 있는 숫자를 어떻게 찾을 수 있을지는 여러 알고리즘이 있는데 어떤 알고리즘을 선택하는지에 따라 수행시간은 정말 천차만별로 달라지게 된다.

 

다시 말해, 어떤 알고리즘을 언제 사용해야 할지 알게 되면 코드 스피드는 빨라지게 될 것이다. (이것이 우리가 알고리즘을 배워야 하는 이유!)

 

 

 

 

 

 

 

 

 

 

1. 선형 검색 알고리즘 (Linear Search)

 

Search(검색) 알고리즘 패밀리에는 2가지 알고리즘이 있다. 우리는 최대한 빠르게, 검색 작업을 수행하는 것이 중요한 관건이다. 다른 알고리즘 패밀리도 있습니다. 정렬(Sorting) 알고리즘에서는 자료를 정리하는 알고리즘 입니다. 예를 들면 A부터 Z 까지 정렬하기, 혹은 작은 수에서 큰 수로 정렬하기 가 정렬 알고리즘에 속합니다.

 

 

먼저 선형 검색 알고리즘(Linear Search) 부터 알아보겠다.

10개의 숫자가 존재하는 배열에서 7이라는 숫자를 찾는 경우를 살펴보자. 그렇다면 1번 아이템부터 차례로 7이 맞는지 탐색하게 된다. (그림 참고▼)

 

 

 

선형 검색 알고리즘은 첫번째 아이템부터 7이 맞는지 확인하는 알고리즘을 말한다.

 

처음부터 순서대로, 차근차근 찾는 알고리즘은 선형 검색 알고리즘이다. 이러한 선형 검색 알고리즘의 최악의 경우는 우리가 찾는 아이템이 만약에 배열의 맨 마지막 끝에 있다거나 혹은 배열에 아예 없는 경우이다.(처음부터 하나씩 검색하므로..) 이 말인 즉슨, 배열이 커지면 커질수록 선형 검색을 하는 시간이 무척 길어질 것이라는 것이다. 이걸 바로 Linear Time Complexity (선형 시간복잡도)라고 한다.

 

 

선형 시간복잡도란 인풋이 많을수록 수행하는 시간 역시 선형적으로 증가한다는 개념이다.

 

 

 

 

 

 

 

 

 

2. 정렬된 배열과 이진 검색 알고리즘 (Binary Search)

 

이진 검색 알고리즘은 모든 배열에서 쓰는건 불가능하다. 오직, 정렬된 배열(Sorted Array) 에서만 쓸 수 있다는 특징이 있다. 어떤 알고리즘은 특정한 자료구조에만 쓸 수 있다는 특징이 있는데, 이진 검색 알고리즘이 바로 그 경우이다. 참고로 선형 검색 알고리즘과 비교해보면, 선형 검색 알고리즘은 모든 배열에서 사용 가능하지만 이진 검색 알고리즘은 불가능하다.

 

 

앞서 말한 Sorted Array 란 무엇일까? 예를 들어서 작은 수부터 큰 수로 정렬된 배열이 Sorted Array(정렬된 배열) 가 된다. 그러나 이렇게 정렬된 배열은 정렬 x 배열보다 아이템을 추가할 때 시간이 더 걸린다는 특징이 있다. 하지만 검색할 때는 정렬 x인 배열에 비해 무척 빠르다는 특징이 있다.

(정렬된 배열의 특징: 아이템 추가는 시간이 걸리지만 검색은 정말 빠르다)

 

 

정렬이 안된 배열에 아이템을 추가하는 것은 공간이 있기만 하면 그냥 맨 끝에 추가만 하면 된다. 반대로 정렬이 된 배열에서 아이템을 추가하는 것은 작업이 복잡하다. 밑에 예제를 보자.

 

 

 

정렬된 배열에서 8을 추가할 때는 8보다 큰 숫자를 차례대로 찾게 된다.

 

 

예를 들어 2 5 7 10 이라는 배열에 8을 추가할 때 0번 인덱스부터 작업을 해야 한다. 즉, 인덱스를 차례로 순서대로 탐색하면서 큰지 작은지를 각각 비교해야 한다. 8이라는 숫자를 2 5 7 10 이라는 배열에 추가하고 싶을 때 0번 인덱스인 2와 비교하고.. 8이 더 크므로, 1번 인덱스로 넘어가게 된다. 그리고 1번 인덱스인 5와 비교하고.. 아직 8이 더 크니까 2번 인덱스로 이동하게 된다... 3번 인덱스인 10에서.. 10이 8보다 크므로 8의 위치를 이제 지정할 수 있게 된다. 

 

 

그렇다면 이제 8의 위치를 알았으니 8의 오른쪽에 있는 아이템 10을 오른쪽으로 이동시키게 되고 중간 빈공간에는 8이 들어서게 된다. 이것이 정렬된 배열에서 숫자를 추가할 때의 알고리즘이 된다. 정렬이 안된 배열에서보다 훨씬 시간이 많이 걸리는 것을 알 수 있다. (처음부터 하나하나 비교하고 옮기는 작업까지 있으므로...)

 

 

하지만 이렇게 정렬하고 배열에 추가하는 과정에 시간을 투자한다면 검색을 하는 순간, 엄청난 효과를 발휘하게 된다. 밑에서 알아보자.

 

 

 

 

 

 

 

 

 

 

3. 이진 검색 알고리즘 (Binary Search)

 

 

 

이진 검색은 반으로 쪼개는 핵심을 기억해두자

 

 

이진 검색에서 '이진'은 0 또는 1을 의미하는 것이 아닌 반으로 쪼개는 것이다. 즉, 하나를 두 개로 쪼개는 것을 의미한다. 1~ 10 까지 정렬된 배열을 살펴보자. 여기서 9를 찾는 것이 우리의 목표이다. 선형 검색과는 달리, 이진 검색은 인덱스 0번부터 검색하지 않는다. 이진 검색은 중간에서부터 시작하는게 핵심이다.

 

 

 

 

 

이진 검색은 먼저 중간의 숫자와 큰지 작은지를 비교하게 됩니다.

 

 

이진 검색은 먼저 중간의 숫자와 큰지 작은지를 비교하게 된다. 밑의 예를 통해서 알아보자!

 

 

 

 

 

 

이진 검색 알고리즘에서 9 검색하기

 

1~10 까지 정렬된 배열에서 이진 검색 알고리즘을 적용해서 9를 검색한다고 할 때, 먼저 중간의 숫자를 먼저 찾는다. 중간의 숫자는 5 이다. 9와 비교 ( 5 < 9 ) 했을때 9는 5보다 크므로 5의 오른쪽을 탐색하게 된다.

 

 

 

 

 

 

 

6~10 까지 탐색 후보를 좁힘

 

 

그 다음 6~10까지 탐색할 때는 이전의 방법과 마찬가지로, 중간의 숫자 8을 찾고 검색 목표의 숫자 9와 비교를 한다( 8 < 9 ).  9가 8보다 크므로 탐색의 범위는 6, 7, 8 의 숫자가 무시된 9와 10이 남는다.

 

 

 

 

 

중간 숫자인 8과 비교했을때 목표 9는 8보다 크므로, 탐색 범위는 8의 오른쪽으로 좁혀진다. (9, 10)

 

 

 

그 다음 프로세스에서는 9를 드디어 찾게 된다. (남은 아이템이 2개밖에 안남았으므로..)

보시다시피 선형 검색 알고리즘은 9번의 프로세스를 거쳐서 9를 찾지만(일일히 검색), 이진 검색 알고리즘은 단 3번만에 9를 찾게 된다.

 

 

 

 

 

이진 검색은 매 스탭마다 절반의 아이템을 제외하고 검색하기 때문에 검색의 효율이 높다. 만약 배열이 10000개의 숫자로 이루어져있다면 이진 검색 알고리즘은 더욱 더 효과적으로 작용하게 된다. 선형 검색 알고리즘의 경우 10000번의 스탭으로 이루어지지만 이진 검색 알고리즘은 최대 14번만의 스탭으로 검색을 할 수 있게 된다(10000길이 기준). 그러나 이진 검색 알고리즘을 사용하려면 무조건 정렬된 배열을 사용해야 된다는 것! 배열을 정렬할 시, 아이템을 추가한다면 이 또한 엄청난 시간이 소요된다는 것... 이러한 상충관계를 명확히 인지하는 것이 좋다. (그래서 알고리즘 및 데이터 구조를 알아야 하는 것!)