ÀÌ Àå¿¡¼­´Â ¼ÒÇÁÆ®¿þ¾î °øÇп¡¼­ ¿À·§µ¿¾È ¿¬±¸µÇ¾î ¿Â ¾Ë°í¸®Áò Áß °¡Àå ½Ç¿ëÀûÀÌ°í ÀÚÁÖ »ç¿ëµÇ´Â °Ë»ö°ú Á¤·Ä µÎ °¡Áö ¾Ë°í¸®Áò¿¡ ´ëÇØ ¾Ë¾Æ º»´Ù. °¢ ºÐ¾ßº°·Î ÇѱÇÀÇ Ã¥À¸·Î ÃâÆÇµÉ Á¤µµ·Î Å« ÁÖÁ¦À̹ǷΠÀÌ Àå¿¡¼­ ¾Ë°í¸®ÁòÀÇ ¸ðµç °ÍÀ» ´Ù·ç±â´Â Çö½ÇÀûÀ¸·Î ¾î·Æ´Ù. ±×·¡¼­ ÀÌ ÀåÀÇ ¸ñÇ¥´Â ¾Ë°í¸®ÁòÀÇ °³³ä¿¡ ´ëÇÑ ¼Ò°³¿Í °ü½ÉÀ» À¯µµÇÏ´Â °ÍÀÌ´Ù. ´õ ±í°í Á¤±³ÇÑ ¾Ë°í¸®Áò¿¡ °ü½ÉÀÖ´Â »ç¶÷Àº º°µµÀÇ ¾Ë°í¸®Áò ¼­ÀûÀ» Âü°íÇϱ⠹ٶõ´Ù.

20-1.°Ë»ö

°Ë»ö(Search)À̶õ ÀÚ·áÀÇ ÁýÇÕ(table)¿¡¼­ ¿øÇÏ´Â ¾î¶² ÀÚ·á(Key)°¡ ÀÖ´ÂÁö, ÀÖ´Ù¸é ¾îµðÂë¿¡ ÀÖ´ÂÁö¸¦ ã¾Æ³»´Â ¾Ë°í¸®ÁòÀÌ´Ù. ÄÄÇ»ÅÍ´Â ¹æ´ëÇÑ ¾çÀÇ ÀڷḦ Á¶Á÷ÀûÀ¸·Î ÀúÀåÇÒ ¼ö ÀÖ´Â ±â¾ï ´É·ÂÀÌ ÀÖÀ¸¸ç ÀÌ ±â¾ï ´É·ÂÀ» È°¿ëÇÏ¿© µ¥ÀÌÅÍ º£À̽º¸¦ ±¸ÃàÇÑ´Ù. µ¥ÀÌÅÍ º£À̽º°¡ ´Ü¼øÈ÷ µ¥ÀÌÅ͸¦ ½×¾Æ ³õ±â¸¸ ÇÑ´Ù¸é Á¾ÀÌ ¹¶Ä¡¸¦ â°í¿¡ º¸°üÇØ ³õ´Â °Í°ú º°¹Ý ´Ù¸¦ ¹Ù°¡ ¾øÀ» °ÍÀÌ´Ù. µ¥ÀÌÅÍ º£À̽º°¡ Á¤¸» ¾µ¸ð°¡ ÀÖÀ¸·Á¸é ½×ÀÎ ÀÚ·á¿¡¼­ ¿øÇÏ´Â ÀڷḦ Á¤È®ÇÏ°í ºü¸£°Ô °Ë»öÇÏ´Â ¿¬»ê ±â´ÉÀÌ ÇÊ¿äÇÏ´Ù.

°Ë»öÀº ¼ÒÇÁÆ®¿þ¾î °øÇп¡¼­ °¡Àå ¿À·§µ¿¾È ¿¬±¸µÇ¾î ¿Â ÁÖÁ¦ÀÌ¸ç ¶ÇÇÑ °¡Àå ½Ç¿ëÀûÀÎ ÁÖÁ¦À̱⵵ ÇÏ´Ù. ¿øÇÏ´Â ÀڷḦ ºü¸£°Ô ã´Â °Í »Ó¸¸ ¾Æ´Ï¶ó »õ·Î Ãß°¡µÇ°Å³ª »èÁ¦µÇ´Â ÀÚ·áµéµµ ´ÙÀ½ °Ë»öÀ» À§ÇØ ¾î¶»°Ô Á¶Á÷ÇÒ °ÍÀÎÁö±îÁö Æ÷°ýÇÏ´Â Á¾ÇÕ ÀÚ·á °ü¸® ¾Ë°í¸®ÁòÀÌ ¹Ù·Î °Ë»öÀÌ´Ù.

20-1-°¡.¼øÂ÷ °Ë»ö

¼øÂ÷ °Ë»ö(Sequential Search)Àº ¸ðµç ¾Ë°í¸®Áò Áß¿¡¼­ °¡Àå ±âº»ÀûÀ̸鼭 ¶ÇÇÑ »ó½ÄÀûÀÎ °Ë»ö ¹æ¹ýÀÌ´Ù. Å×À̺íÀÇ Ã³À½ºÎÅÍ ¼ø¼­´ë·Î ÀÐÀ¸¸é¼­ ¿øÇÏ´Â Å°¿Í ºñ±³Çϱ⸦ °Ë»ö¿¡ ¼º°øÇϰųª ¾Æ´Ï¸é Å×ÀÌºí ³¡¿¡ À̸¦ ¶§±îÁö ¹Ýº¹ÇÏ´Â °ÍÀÌ´Ù. ¾Ë°í¸®ÁòÀÌ ¿ö³« °£´ÜÇؼ­ ´Ü¼øÇÑ ·çÇÁ Çϳª·Î ±¸ÇöÇÒ ¼ö ÀÖ°í ÀÓÀÇÀÇ ÀÚ·á¿¡µµ Àû¿ëÇÒ ¼ö ÀÖÀ¸¸ç ÀڷḦ º°µµ·Î °ü¸®ÇÒ ÇÊ¿äµµ ¾ø´Ù. ´ë½Å ³Ê¹« °£´ÜÇϱ⠶§¹®¿¡ °Ë»ö È¿À²Àº º°·Î ÁÁÁö ¸øÇÏ´Ù. ´ÙÀ½ ¿¹Á¦´Â Á¤¼ö ¹è¿­¿¡¼­ ¿øÇÏ´Â Á¤¼ö°ªÀ» ã´Â´Ù.

 

¿¹ Á¦ : SequentailSearch

#include <Turboc.h>

 

int LinearSearch(int *ar,unsigned num,int key)

{

     unsigned i;

 

     for (i=0;i<num;i++) {

          if (ar[i] == key) {

              return i;

          }

     }

     return -1;

}

 

void main()

{

     int ar[]={23,47,19,63,57,26,75,73,82,89,47,11};

     unsigned num;

     int key,idx;

 

     num=sizeof(ar)/sizeof(ar[0]);

     key=75;

     idx=LinearSearch(ar,num,key);

     if (idx == -1) {

          puts("ã´Â °ªÀÌ ¾ø½À´Ï´Ù.");

     } else {

          printf("ã´Â °ªÀº %d¹ø°¿¡ ÀÖ½À´Ï´Ù.\n",idx);

     }

}

 

ÀÌ ¿¹Á¦¿¡¼­ ar ¹è¿­ÀÌ °Ë»ö ´ë»óÀÎ Å×À̺íÀ̸ç ÀÌ Å×ÀÌºí¿¡¼­ ƯÁ¤ Å°°ªÀÌ ¾îµðÂë ÀÖ´ÂÁö¸¦ °Ë»öÇϴµ¥ ¿¹Á¦¿¡¼­´Â 75¶ó´Â Å°¸¦ ã¾Æ º¸¾Ò´Ù. ¹°·Ð Å×½ºÆ® ¿¹Á¦ÀÌ°í Å×ÀÌºí ±æÀÌ°¡ ªÀ¸¹Ç·Î À°¾ÈÀ¸·Îµµ ±Ý¹æ °Ë»öÇÒ ¼ö ÀÖÁö¸¸ ÄÄÇ»ÅÍ´Â ´«ÀÌ ¾øÀ¸¹Ç·Î ¼øȸÇϸ鼭 Å°¸¦ ã¾Æ¾ß ÇÑ´Ù. LinearSearch ÇÔ¼ö´Â ƯÁ¤ ¹è¿­¿¡¼­ ¼øÂ÷ °Ë»öÀ» Çϴµ¥ ¼¼ °³ÀÇ Àμö¸¦ ¹Þ¾ÆµéÀδÙ. arÀº Å×À̺íÀÇ ½ÃÀÛ ¹øÁö, numÀº Å×À̺íÀÇ Å©±â, key´Â ã°íÀÚ ÇÏ´Â Å°°ªÀÌ´Ù.

°Ë»ö ¹æ¹ýÀº Áö±ØÈ÷ »ó½ÄÀûÀε¥ ¹è¿­ÀÇ ¼±µÎ¿¡¼­ ¼øȸ¸¦ ½ÃÀÛÇÏ¿© ¸Å ¹è¿­ ¿ä¼Ò°¡ key ÀÎÁö ºñ±³ÇÏ¿© key¿Í °°Àº ¿ä¼ÒÀÇ Ã·ÀÚ¸¦ ¸®ÅÏÇÑ´Ù. ¸¸¾à ¹è¿­ ³¡±îÁö ¼øȸ¸¦ ¸¶Ãƴµ¥ Á¶°Ç¿¡ ¸Â´Â Å°°¡ ¾ø´Ù¸é -1À» ¸®ÅÏÇÏ¿© °Ë»ö¿¡ ½ÇÆÐÇßÀ½À» ¾Ë¸°´Ù. È£Ãâ¿ø¿¡¼­´Â ¸®ÅÏµÈ °ªÀ» º¸°í Å°°¡ ¹è¿­ÀÇ ¾îµðÂë¿¡ ÀÖ´ÂÁö¸¦ ¾Ë ¼ö ÀÖ´Ù. Å×À̺íÀÌ ¿¬°á ¸®½ºÆ®¶ó¸é ÷ÀÚ¸¦ ¸®ÅÏÇÏ´Â ¹æ¹ýÀ» ¾µ ¼ö´Â ¾ø°í °Ë»öµÈ ³ëµåÀÇ Æ÷ÀÎÅ͸¦ ¸®ÅÏÇØ¾ß ÇÑ´Ù. ¹°·Ð ãÁö ¸øÇßÀ» ¶§´Â NULLÀ» ¸®ÅÏÇÏ¸é µÉ °ÍÀÌ´Ù.

Å°´Â º¸Åë Å×ÀÌºí¿¡¼­ ´Ù¸¥ ·¹ÄÚµå¿Í Áߺ¹µÇÁö ¾Ê´Â À¯ÀÏÇÑ °ªÀ» °¡Áö´Â °ÍÀ» »ç¿ëÇϴµ¥ ¿¹¸¦ µé¾î ÁÖ¼Ò·Ï ±¸Á¶Ã¼ ¹è¿­À̶ó¸é Áֹεî·Ï¹øÈ£¸¦ Å°·Î »ç¿ëÇÏ´Â °ÍÀÌ °¡Àå ÁÁ´Ù. ÀÌó·³ ·¹Äڵ尣¿¡ Áߺ¹µÇÁö ¾Ê´Â À¯ÀÏÇÑ Å°¸¦ ÇÁ¶óÀ̸Ӹ® Å°(Primary Key)¶ó°í ÇÑ´Ù. ÇÁ¶óÀ̸Ӹ® Å°°¡ ¾ø´Â Å×ÀÌºí¿¡¼­´Â ƯÁ¤ Å°¿Í ÀÏÄ¡ÇÏ´Â ·¹Äڵ尡 µÑ ÀÌ»ó Á¸ÀçÇÒ ¼ö Àִµ¥ ÀÌ·² ¶§´Â óÀ½ºÎÅÍ °Ë»öÀ» ½ÃÀÛÇÏ¿© ½ÇÆÐÇÒ ¶§±îÁö ¹Ýº¹ °Ë»öÇÏ¿© ¸ðµç ·¹Äڵ带 ãÀ» ¼ö ÀÖ´Ù.

¼øÂ÷ °Ë»öÀº °Ë»ö ¹æ¹ýÀÌ °£´ÜÇϹǷΠÁ÷Á¢ ¸¸µé¾î ¾²±âµµ ½±´Ù. ´ëºÎºÐÀÇ ÄÄÆÄÀÏ·¯µéÀº ¼øÂ÷ °Ë»ö ÇÔ¼ö¸¦ Á¦°øÇϴµ¥ ºñÁÖ¾ó C++Àº lsearch ÇÔ¼ö¸¦ Á¦°øÇÑ´Ù.

 

void *lsearch( const void *key, void *base, unsigned int *num, unsigned int width, int (__cdecl *compare)(const void *elem1, const void *elem2) );

 

Àμö·Î Å°°ª, Å×À̺íÀÇ ¼±µÎ ¹øÁö, ¿ä¼ÒÀÇ °³¼ö¿Í Å©±â, ±×¸®°í ºñ±³ ÇÔ¼ö¿¡ ´ëÇÑ ÇÔ¼ö Æ÷ÀÎÅ͸¦ ¿ä±¸ÇÑ´Ù. ÀÓÀÇÀÇ Å¸ÀÔ¿¡ ´ëÇØ µ¿ÀÛÇØ¾ß ÇϹǷΠºñ±³ ¹æ¹ýÀ» »ç¿ëÀÚ°¡ ÇÔ¼ö·Î Á÷Á¢ Á¤ÀÇÇÒ ¼ö ÀÖµµ·Ï µÇ¾î ÀÖ´Ù. ºñ±³ ÇÔ¼ö´Â Àμö·Î Àü´ÞµÈ µÎ °ªÀ» ºñ±³ÇØ º¸°í Ʋ¸± °æ¿ì TRUE¸¦, ÀÏÄ¡ÇÒ °æ¿ì FALSE¸¦ ¸®ÅÏÇÏ¸é µÈ´Ù. lsearch ÇÔ¼ö´Â Å×À̺íÀÇ ¸ðµç ¿ä¼Ò¿¡ ´ëÇØ ºñ±³¸¦ ¼öÇàÇÑ ÈÄ °Ë»öµÈ Æ÷ÀÎÅ͸¦ ¸®ÅÏÇ쵂 ¹ß°ßµÇÁö ¾ÊÀ¸¸é NULLÀ» ¸®ÅÏÇÑ´Ù. ´ÙÀ½ ¿¹Á¦´Â lsearch ÇÔ¼ö·Î À§ ¿¹Á¦¸¦ ´Ù½Ã ÀÛ¼ºÇØ º» °ÍÀÌ´Ù.

 

¿¹ Á¦ : lsearch

#include <Turboc.h>

#include <search.h>

 

int compare(const void *elem1,const void *elem2)

{

     return (*(int *)elem1 != *(int *)elem2);

}

 

void main()

{

     int ar[]={23,47,19,63,57,26,75,73,82,89,47,11};

     unsigned num;

     int key;

     int *ptr;

 

     num=sizeof(ar)/sizeof(ar[0]);

     key=75;

     ptr=(int *)lsearch(&key,ar,&num,sizeof(int),compare);

     if (ptr==NULL) {

          puts("ã´Â °ªÀÌ ¾ø½À´Ï´Ù.");

     } else {

          printf("ã´Â °ªÀº %d¹ø°¿¡ ÀÖ½À´Ï´Ù.\n",ptr-ar);

     }

}

 

½ÇÇà °á°ú´Â µ¿ÀÏÇÏ¸ç ¾ÕÀÇ ¿¹Á¦¿¡ ºñÇØ º°¹Ý Ʋ¸° Á¡µµ ¾ø´Ù. ¶ÇÇÑ Æ¯º°È÷ Æí¸®ÇÑ Á¡µµ ¾ø´Âµ¥ lsearch ÇÔ¼ö´Â ÀÓÀÇ Å¸ÀÔ¿¡ ´ëÇØ µ¿ÀÛÇØ¾ß Çϱ⠶§¹®¿¡ Æ÷ÀÎÅÍ¿Í ÇÔ¼ö Æ÷ÀÎÅ͸¦ »ç¿ëÇϱ⠶§¹®ÀÌ´Ù. »ç½Ç ÀÌ ÇÔ¼ö´Â º° ½Ç¿ë¼ºÀÌ ¾ø¾î ANSI C Ç¥ÁØ¿¡µµ Æ÷ÇԵǾî ÀÖÁö ¾ÊÀ¸¸ç À¢¸¸Çϸé Á÷Á¢ ¸¸µé¾î ¾²´Â °ÍÀÌ ´õ Æí¸®ÇÏ´Ù.

¼øÂ÷ °Ë»öÀº ±× ¾Ë°í¸®ÁòÀÇ ´Ü¼øÇÔÀ¸·Î ÀÎÇØ ÄÚµå´Â °£´ÜÇÏÁö¸¸ ¼Óµµ´Â ¹«Ã´ ´À¸®´Ù. Å©±â 100ÀÇ ¹è¿­¿¡¼­ ¾î¶² °ªÀ» °Ë»öÇÒ ¶§ °Ë»ö ½Ã°£Àº ¿î¿¡ Á¿ìµÇ´Âµ¥ ã´Â Å°°¡ ¹è¿­ ¾ÕÂÊ¿¡ ÀÖÀ¸¸é »¡¸® ãÀ» °ÍÀÌ°í µÚÂÊ ³¡¿¡ ÀÖ´Ù¸é ¾ÕÂÊÀ» ´Ù ºñ±³ÇØ ºÁ¾ß ºñ·Î¼Ò ãÀ» ¼ö ÀÖÀ» °ÍÀÌ´Ù. Å×À̺í Å©±â°¡ nÀ̶ó°í ÇÒ ¶§ ¿øÇÏ´Â Å° °ªÀ» ã±â À§ÇØ Æò±Õ nÀÇ Àý¹Ý¸¸Å­ ºñ±³ÇØ¾ß ÇÏ°í Å°°¡ ¾øÀ» °æ¿ì´Â n¹ø ºñ±³¸¦ ÇØ ºÁ¾ß ¾ø´Ù´Â °ÍÀ» ¾Ë ¼ö ÀÖ´Ù. ¸¸¾à nÀÌ ¹é¸¸ Á¤µµ µÈ´Ù¸é ±× °Ë»ö ¼Óµµ´Â °¡È÷ ²ûÂïÇÑ ¼öÁØÀÏ °ÍÀÌ´Ù.

°Ë»ö ¼Óµµ°¡ ¿ö³« ´À¸®±â ¶§¹®¿¡ °Ë»öµÈ ÀÚ·áÀÇ ¼ø¼­¸¦ ¾ÕÂÊÀ¸·Î ¿Å°Ü ´ÙÀ½ ¹ø °Ë»ö¿¡¼­´Â Á» ´õ »¡¸® °Ë»öµÇµµ·Ï ÇѴٰųª ÀÚÁÖ °Ë»öµÉ¸¸ÇÑ ÀڷḦ ÃÖ´ëÇÑ ¾ÕÂÊ¿¡ ¹èÄ¡ÇÏ´Â °³¼±Ã¥ÀÌ ÀÖ±â´Â ÇÏÁö¸¸ ÀÌ´Â Å×À̺íÀÇ ¿ä¼Ò ¼ø¼­°¡ Àǹ̾øÀ» ¶§¸¸ ¾µ ¼ö ÀÖ´Â ¹æ¹ýÀÌ´Ù. ±×·¡¼­ ÀϹÝÀûÀ¸·Î ¼øÂ÷ °Ë»öÀº °Ë»ö¸¸ ÇÒ »ÓÀÌÁö ÀڷḦ °ü¸®ÇÏ´Â ¾Ë°í¸®ÁòÀº Æ÷ÇÔµÇÁö ¾Ê´Â´Ù.

±×·¯³ª ÀÌ·¸°Ô ¹«½ÄÇÑ ¼øÂ÷ °Ë»öµµ ³ª¸§´ë·Î ÀåÁ¡ÀÌ Àִµ¥ ÀÚ·áÀÇ »óÅ¿¡ ´ëÇØ ¾î¶² °¡Á¤À» ÇÏÁö ¾Ê±â ¶§¹®¿¡ ÀÚ·áÀÇ »ðÀÔ, »èÁ¦¿¡ ´ëÇÑ Æ¯º°ÇÑ Ã³¸®°¡ ÇÊ¿ä¾ø´Ù´Â Á¡ÀÌ´Ù. ¹è¿­ ¶Ç´Â ¿¬°á ¸®½ºÆ®ÀÇ ¾îµð¿¡³ª ÀڷḦ »ðÀÔÇØ ³õ±â¸¸ ÇÏ¸é ´ÙÀ½¹ø °Ë»ö ´ë»ó¿¡ Æ÷ÇÔµÇ°í »èÁ¦ÇÑ ÀÚ·á´Â ´çÀå °Ë»ö ´ë»ó¿¡¼­ Á¦¿ÜµÇ¹Ç·Î ÀڷḦ º¯°æÇϴµ¥ ¾Æ¹«·± ÁÖÀÇ »çÇ×ÀÌ ¾ø´Ù. ¹Ý¸é À̺Р°Ë»öÀ̳ª Çؽ¬ µîÀÇ °í±Þ °Ë»ö ¹æ¹ýÀº °Ë»ö ¼Óµµ°¡ ºü¸¥ ´ë½Å ÀڷḦ °ü¸®ÇÏ´Â °ÍÀÌ ¹«Ã´ ¾î·Æ´Ù.

¶ÇÇÑ ¼øÂ÷ °Ë»öÀÇ ´Ü¼ø ¹«½ÄÇÔÀº Àú´É½º·¯¿î ÄÄÇ»ÅÍ¿¡°Ô´Â °¡Àå ¾î¿ï¸®´Â °Ë»ö ¹æ¹ýÀ̱⵵ Çѵ¥ ¿äÁò CPUÀÇ ¼Óµµ»ó ¼ö¸¸°Ç Á¤µµ´Â ¼ø½Ä°£¿¡ ã¾ÆÁÙ Á¤µµ´Ù. ±×¸®°í ¾Ë°í¸®ÁòÀÇ °£´ÜÇÔÀ¸·Î ÀÎÇØ ¹ö±×°¡ ¹ß»ýÇÒ Æ´ÀÌ ¾ø¾î ¾ÈÀü¼º°ú °³¹ßÀÚÀÇ ÆíÀǼº ¸é¿¡¼­µµ ³ôÀº Á¡¼ö¸¦ ÁÙ ¼ö ÀÖ´Ù. »ç½Ç ¼øÂ÷ °Ë»öÀº Å×À̺í Å©±â°¡ ¼ö¹é°Ç Á¤µµ¶ó¸é ´Ù¸¥ ¹æ¹ýº¸´Ù ¿ÀÈ÷·Á È¿À²ÀûÀÌ¸ç °¡Àå ÀÚÁÖ »ç¿ëµÇ´Â °Ë»ö ¹æ¹ýÀÌ´Ù.