선형(순차) 탐색 알고리즘

안녕하세요~ 

 

오늘은 순차 탐색 또는 선형 탐색이라고도 불리는 "Linear Search (Sequential Search)" 알고리즘에 대해 알아보도록 하겠습니다.

 

이 알고리즘은 탐색 알고리즘 중에서 가장 기본이 되는 알고리즘 입니다. 

 

공대를 나오지 않은 분들도 "순차"라는 단어를 봤을 때 느낌이 오셨을 겁니다. 

 

네 맞습니다. 이 알고리즘은 그냥 다수의 아이템을 순차적으로 하나씩 조회 하면서 내가 찾고자 하는 아이템이 있는지를 탐색하는 것입니다.  찾고자 하는 아이템을 찾을 때까지 모든 아이템을 검사하게되며 특정 아이템을 찾았을 경우에는 해당 아이템을 반환하고 알고리즘은 거기서 종료됩니다. 간단히 말하면 10개의 아이템 중에서 첫 번째로 검색한 아이템이 내가 원한 아이템이면 나머지 9개는 조회할 필요없이 알고리즘은 종료됩니다. 못 찾았을 경우에는 당연히 모든 아이템을 다 검사하게 되겠죠. 

 

아래 그림을 보시면 쉽게 이해가 되실 겁니다.

이 알고리즘을 사용할 경우 최선의 경우 조회 하자마자 원하는 아이템을 획득하는 것입니다. 

이 때에 시간 복잡도가 O(1)이 되겠죠. 

하지만 원하는 아이템을 마지막에 찾게 될 경우에는 O(n)이 됩니다. 

모든 n개의 아이템을 조회해야 하니까요. 

 

예를 들어 숫자 데이터를 가지고 있는 배열이 있다고 해봅시다. 

데이터는 1부터 10000 까지가 존재하고 자주 조회되는 것들은 9000~10000 사이의 숫자들이라고 가정합니다. 

이럴 때 선형 알고리즘을 이용해서 평균 조회 시간을 최소로 만들려면 어떻게 해야 할까요? 

선형 알고리즘의 특징을 잘 생각해보시면 되는데요, 선형 알고리즘은 모든 데이터셋을 처음부터 끝까지 하나 하나씩 읽어나가면서 원하는 아이템을 찾게됩니다. 

이 특징을 이용해서, 자주 조회되는 아이템들이 앞쪽에 모여있도록 데이터를 정렬하면 되는 것입니다. 

위 그림 예제에서는 숫자가 작은 수부터 큰 수로 정렬이 되어있지만 지금 우리는 9000 ~ 10000 사이의 숫자가 빈번히 조회된다는 가정을 하였으니, 위 그림과는 반대로 큰 수 부터 작은 수로 정렬을 한 데이터 셋을 만들어 놓고 조회를 하도록 하면 평균적으로 걸리는 시간이 많이 줄어들게 될 것입니다.

 

어떤가요? 그리 어렵지 않죠? 그럼 이 알고리즘을 자바 코드로 어떻게 구현할까요? 이것 또한 상당히 간단합니다.

 

for (c = 0; c < n; c++){ if (array[c] == search){ /* Searching element is present */

System.out.println(search + " is present at location " + (c + 1) + "."); break; } }

 

이렇게 for-loop 안에서 아이템(array[c])을 하나씩 조회하면서 찾고자 하는 숫자(search) 와 동일한지 비교(==)하고 찾았을 경우에는 해당 아이템의 위치를 System.out.println으로 출력해주고 알고리즘은 종료(break)하게 됩니다.

 

자, 이제 누가 "선형 알고리즘이 뭐야?" 라고 물으시면 1초의 망설임도 없이 "응~, 그건 말이야~" 하고 대답할 수 있겠죠? ㅎㅎㅎ
이상으로 선형 알고리즘 포스팅을 마칩니다.