[펌_java를 이용한 자료구조] 탐색(Searching)

LONG

 

Binary Search

 이진 검색이라고도 합니다. 지난번 강좌에서 Binary Search Tree에 대해서 배우신거 기억 나시나요? Binary Search Tree는 자식노드를 최대 두개까지 가질 수 있으며, 왼쪽 자식이 오른쪽 자식보다 작아야 한다는 규칙이 있었습니다. Binary Search는 평균적으로 상당히 빠른 검색시간을 보여주는 검색 방법입니다.

 실제로 Binary Search가 어떻게 돌아가고, 또 어떻게 구현하는지에 대해서 알아보도록 하겠습니다.

[그림 3] Array안에 들어있는 숫자들.(오름차순)

 위와 같은 배열에 숫자들이 일정한 순서에 의해서 나열되어 있습니다. Binary Search를 사용하려면 찾기위한 대상이 반드시 어떤 순서에 의해서 정렬이 되어 있어야만 합니다. 그 이유에 대해서는 실제 코드를 보고, 찾는 그림을 보고 난 후 말씀드리도록 하겠습니다. 일단 실제로 어떻게 찾나 애니메이션으로 보도록 하죠.

[그림 4] Binary Search를 이용한 검색 단계

 위의 애니메이션 처럼 단계가 되는데요. 이를 코드로 구현해 보면 아래의 그림과 같습니다. 재귀함수로 구현이 되어 있습니다.

public static int Search(int[] a, int first, int size, int target) {   int middle;   if( size <= 0 )     return -1;   else   {     middle = first + (size / 2);     if( target == a[middle] )       return middle;     else if( target < a[middle] )       return Search(a, first, size / 2, target);     else       return Search(a, middle + 1, (size - 1) / 2, target);   } }

 48이란 숫자가 배열의 어느 index에 위치해 있는가를 알려줍니다. 위의 그림처럼 코드로 구현이 되는군요. 종이를 하나 준비하시고 실제로 size와 first, middle을 따라가 보시면 쉽게 이해하실 수 있습니다. 위의 코드를 보시면 target과 a[middle]을 비교하여 검색할 부분을 정해주는데, 만약 a배열의 정렬 조건과 부등호가 맞지 않는다면 원하는 결과를 얻지 못하게 됩니다.

 만약에 위의 배열에서 48을 찾는데 Serial Search를 사용한다면 5번의 과정을 거쳐야 합니다. 하지만 Binary Search를 이용하였더니 단 3 단계 만에 원하는 결과를 얻어내었습니다. Best case의 시간은 물론 Serial Search 보다 나쁘지만 Average case나 Worst case의 경우에는 Serial Search 보다 더욱 좋은 검색 시간을 보입니다.

=============================================================================================

 

Open-Address Hashing

 Hashing이란 각각의 원소들에 유일한 Key값을 하나씩 배당하여 보다 용이한 검색이 가능하도록 하는 알고리즘 입니다. Hashing은 data에 대해서 추가적인 정보(즉 Key)를 이용하여 더 빠른 검색을 할 수 있도록 하는 것 입니다. data에 대한 정보가 아무것도 없는 Serial Search 보다 더 빠른 검색시간을 제공하는 알고리즘 입니다. 이 강좌에서는 그 Key를 배열의 인덱스들중에서 고르도록 하겠습니다.

 배열에 넣는 key값은 배열 전체의 size와 data값을 이용하여 결정합니다. 이 강좌에서는 data % size 로 나눠서 나오는 나머지를 key값으로 배정합니다. 만약 100을 넣는다면? [0]에 100이 들어가게 되겠죠? 506이라면 [6]에 들어가게 될 것입니다. 789라면 [89] 에 값이 들어가게 되겠죠.

 문제는 나머지가 같은 데이터가 존재한다면 data를 넣을 공간이 없게 된다는 것입니다. 이런 경우를 Collision 이라고 하는데, 이것을 해결하기 위해서는 밑의 그림과 같은 방법을 사용합니다.


[그림 5] Hashing에서 Key값의 Collision이 발생한 경우
 위의 그림처럼 Collison을 해결할 수 있습니다. 그럼 찾을때는 어떻게 하면 될까요? 일단 찾는 데이터의 Key값을 구해내고 나서 해당 Key(index)부터 하나씩 순차적으로 내려가면서 찾으면 됩니다. Serial Search의 방법과 매우 비슷하지만, Key를 이용하여 Hashing을 하여 데이터를 저장하면 맨 처음부터 찾는 쓸데없는 수고를 덜 수 있으므로 검색하는데 더 적은 시간을 들여서 작업을 완료 할 수 있게 됩니다.

 물론 Collison을 해결하는 방법이 위처럼 Sequential한 방법만이 있는것은 아닙니다. 하지만 여기서는 Collison이 발생했을때 그것을 해결해야만 한다는것이 더욱 중요하기 때문에 더 많은 Collison해결 방법을 원하시는분은 더 찾아보시면 많은 도움이 되실 것 입니다.

&nsbp;하지만.. 이런식으로 Sequential한 방법을 사용하다가 만약에라도 더이상 값을 넣을 공간이 없다면 어떻게 될까요? 이런 자료구조를 사용한 프로그램은 동작을 제대로 하지 않게 되겠죠. 그렇기 때문에 미리 충분한 크기를(1.5 ~ 2배) 잡아주는 작업이 필요하게 됩니다.

 위와 같이 300이라는 데이터를 삽입한 후에 나머지가 1인 data (301, 401...)를 입력하게 되면 역시나 Collision이 발생하게 되겠죠? 그렇게 되면 역시 위와같은 방법을 이용하여 Collision을 해결하면 됩니다.

Chained Hashing

 Hashing에는 Collision이라는 문제가 있습니다. 자료의 수가 적다면 Collision이 많이 발생해도 나중에 검색할때 속도의 차이가 그다지 많지 않겠지만 자료가 많아질수록 그만큼 Collision도 많이 발생하여 Hashing을 이용하여 얻는 이득이 많이 사라지게 됩니다. 이것을 해결하기 위하여 하나의 key에 하나의 element만을 대응하던 기본 Hashing에서 Linked List를 이용한 Hashing을 사용할 수 있습니다. 이걸 바로 Chained Hashing 이라 하며 밑의 그림과 같은 구조로 이루어져 있습니다.


[그림 6] Chained Hashing의 기본 구조.
 전에 다뤘던 Open-Address Hashing에서는 하나의 Key에 하나의 element만이 들어가서 collison이 자주 발생하게 됩니다. 하지만 위와 같은 구조라면 Key가 중복되었을때 Linked List로 element들을 구성하게 됩니다. 이렇게 되면 Key값들에 대해서 Collision이 발생하였을때 더욱 효율적으로 List를 구성할 수 있습니다. 자료를 검색할 때도, 해당 Key의 Linked List만을 찾아보면 되므로 Open-Address Hashing보다 더욱 빠른 검색속도를 얻어낼 수 있게 됩니다.

 이건 좀 극단적인 경우긴 합니다만 Chained Hashing에서 Collision이 많이 발생해서 하나의 Node에 데이터가 주렁주렁 달려 있을 경우에는 Serial Search가 되어서 Chained Hashing을 쓰지 않은 것처럼 될 수도 있습니다.  실제 구현에 대해서는 여기서 따로 나타내는 것보다는 Linked List 를 다시 보셔서 스스로 구현해 보는것도 좋을 것이라고 생각됩니다.

강좌를 끝마치며...

 이번 강좌는 자료구조의 구현만을 다룬 강좌가 아니었습니다. 처음에 나온 Serial Search, Binary Search는 하나의 Algorithm이고, 뒤에 나온 Open-Address Hashing, Chained Hashing은 또 하나의 자료구조 라고 볼 수 있습니다.

 자료구조를 배우는 목적이, 자료들을 쉽게 관리하고 정리하는것이 목적 이라 한다면 "Search"역시 중요한 하나의 Subject이므로 이 강좌고 독자분들께 많은 도움이 되었으면 합니다. 그럼 다음강좌에서 뵙도록 하겠습니다. 그동안 건강하세요~.

ARTICLE 참고서적 : Data Structures & Other Objects Using JAVA

강좌를 시작하며...

 여러분 주변에 혹시 전화번호부가 있나요? 그곳에서 자신의 이름을 찾아보세요. 찾는 방법이야 여러가지 방법이 있겠죠. 독자분들은 어떻게 찾으셨나요? 저는 'ㅂ'을 먼저 찾고, 'ㅏ'를 찾고, 'ㄱ'을 찾고, 'ㅌ'을 찾고... 이런식으로 찾아가겠죠? 혹시나 그러실 독자분들은 없으시겠지만, 전화번호부 처음부터 찾아보신 분들도 계시나요? 안계시리라 믿습니다. 이렇게 어떤 자료들이 있는 곳에서 원하는 자료만을 찾는 것을 Searching 이라고 합니다. 이번 강좌에서는 자료들을 모아놓고, 거기서 원하는 자료를 찾아내는 여러가지 방법에 대해서 알아보려고 합니다. 이제 시작하도록 하죠.

Serial Search

 위에서도 말씀드렸습니다만, 가장 간단한 방법으로는 처음부터 찾는 방법이겠죠. 만약에 이름이 "가"라면 한번에 찾으실 수 있겠죠. 하지만 이런 이름은 말도 안되죠. "박영철"이라는 이름을 찾아보도록 합시다. 처음부터 찾는다고 가정해 본다면 'ㄱ', 'ㄴ'... 을 거쳐서 'ㅂ' 까지 간 후에 '바'를 찾고, '박'을 찾고... 이런식으로 찾다보면 언젠가는 나오게 되겠죠? 이렇게 맨 처음부터 끝까지 다 찾아보는 것을 Serial Search 라고 합니다.

  Linked List를 이용하여 JAVA 언어로 숫자 Bag을 만들어 보았습니다.


[그림 1] Linked List로 구현한 Bag
 위의 그림처럼 리스트가 있습니다. Serial Search방법으로 원하는 숫자를 찾는 함수를 작성해 보도록 하겠습니다.

public boolean Serial_search(int number) {   Node point = head;   if( point == null )     return false;   while(1)   {     if( point.Get_number() == number )       return true;     if( point.Get_next() == null )       return false;     else       point = point.Get_next();   } }

 19라는 숫자가 Bag에 있는지를 검사하여 보겠습니다.


[그림 2] Serial Search로 Bag에서 원하는 수 찾기
 이렇게 19을 찾게 되는데요, 하나의 노드를 검색하는데 1초가 걸린다고 가정해 봅시다. 19를 찾는데 걸리는 시간은 8초가 되겠군요. 하지만 76을 찾는데는 1초 밖에 걸리지 않게 됩니다. 최악의 경우에는 크기가 n개인 Bag에서 원하는 수를 찾는데는 n초가 소모되겠죠.

 최악의 경우가 n이기 때문에 그다지 좋은 검색방법이라고는 할 수 없습니다. 이것보다는 바로 뒤에 나오게 될 Binary Search를 주로 많이 쓰곤 합니다. 그냥 이런 검색 방법도 있다는 것만 알아두시면 좋을 듯 합니다.