[EKOO의 JAVA를 이용한 자료구조:9회] Searching (1)

[EKOO의 JAVA를 이용한 자료구조:9회] Searching (1)

저자:EKOO| 날짜: 2005년 06월 10일

 

참고서적 : 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를 주로 많이 쓰곤 합니다. 그냥 이런 검색 방법도 있다는 것만 알아두시면 좋을 듯 합니다.