ÀÌ Àå¿¡¼´Â ¼ÒÇÁÆ®¿þ¾î °øÇп¡¼ ¿À·§µ¿¾È ¿¬±¸µÇ¾î ¿Â ¾Ë°í¸®Áò Áß °¡Àå ½Ç¿ëÀûÀÌ°í ÀÚÁÖ »ç¿ëµÇ´Â °Ë»ö°ú Á¤·Ä µÎ °¡Áö ¾Ë°í¸®Áò¿¡ ´ëÇØ ¾Ë¾Æ º»´Ù. °¢ ºÐ¾ßº°·Î ÇѱÇÀÇ Ã¥À¸·Î ÃâÆÇµÉ Á¤µµ·Î Å« ÁÖÁ¦À̹ǷΠÀÌ Àå¿¡¼ ¾Ë°í¸®ÁòÀÇ ¸ðµç °ÍÀ» ´Ù·ç±â´Â Çö½ÇÀûÀ¸·Î ¾î·Æ´Ù. ±×·¡¼ ÀÌ ÀåÀÇ ¸ñÇ¥´Â ¾Ë°í¸®ÁòÀÇ °³³ä¿¡ ´ëÇÑ ¼Ò°³¿Í °ü½ÉÀ» À¯µµÇÏ´Â °ÍÀÌ´Ù. ´õ ±í°í Á¤±³ÇÑ ¾Ë°í¸®Áò¿¡ °ü½ÉÀÖ´Â »ç¶÷Àº º°µµÀÇ ¾Ë°í¸®Áò ¼ÀûÀ» Âü°íÇϱ⠹ٶõ´Ù.
°Ë»ö(Search)À̶õ ÀÚ·áÀÇ ÁýÇÕ(table)¿¡¼ ¿øÇÏ´Â ¾î¶² ÀÚ·á(Key)°¡ ÀÖ´ÂÁö, ÀÖ´Ù¸é ¾îµðÂë¿¡ ÀÖ´ÂÁö¸¦ ã¾Æ³»´Â ¾Ë°í¸®ÁòÀÌ´Ù. ÄÄÇ»ÅÍ´Â ¹æ´ëÇÑ ¾çÀÇ ÀڷḦ Á¶Á÷ÀûÀ¸·Î ÀúÀåÇÒ ¼ö ÀÖ´Â ±â¾ï ´É·ÂÀÌ ÀÖÀ¸¸ç ÀÌ ±â¾ï ´É·ÂÀ» È°¿ëÇÏ¿© µ¥ÀÌÅÍ º£À̽º¸¦ ±¸ÃàÇÑ´Ù. µ¥ÀÌÅÍ º£À̽º°¡ ´Ü¼øÈ÷ µ¥ÀÌÅ͸¦ ½×¾Æ ³õ±â¸¸ ÇÑ´Ù¸é Á¾ÀÌ ¹¶Ä¡¸¦ â°í¿¡ º¸°üÇØ ³õ´Â °Í°ú º°¹Ý ´Ù¸¦ ¹Ù°¡ ¾øÀ» °ÍÀÌ´Ù. µ¥ÀÌÅÍ º£À̽º°¡ Á¤¸» ¾µ¸ð°¡ ÀÖÀ¸·Á¸é ½×ÀÎ ÀÚ·á¿¡¼ ¿øÇÏ´Â ÀڷḦ Á¤È®ÇÏ°í ºü¸£°Ô °Ë»öÇÏ´Â ¿¬»ê ±â´ÉÀÌ ÇÊ¿äÇÏ´Ù.
°Ë»öÀº ¼ÒÇÁÆ®¿þ¾î °øÇп¡¼ °¡Àå ¿À·§µ¿¾È ¿¬±¸µÇ¾î ¿Â ÁÖÁ¦ÀÌ¸ç ¶ÇÇÑ °¡Àå ½Ç¿ëÀûÀÎ ÁÖÁ¦À̱⵵ ÇÏ´Ù. ¿øÇÏ´Â ÀڷḦ ºü¸£°Ô ã´Â °Í »Ó¸¸ ¾Æ´Ï¶ó »õ·Î Ãß°¡µÇ°Å³ª »èÁ¦µÇ´Â ÀÚ·áµéµµ ´ÙÀ½ °Ë»öÀ» À§ÇØ ¾î¶»°Ô Á¶Á÷ÇÒ °ÍÀÎÁö±îÁö Æ÷°ýÇÏ´Â Á¾ÇÕ ÀÚ·á °ü¸® ¾Ë°í¸®ÁòÀÌ ¹Ù·Î °Ë»öÀÌ´Ù.
¼øÂ÷ °Ë»ö(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ÀÇ ¼Óµµ»ó ¼ö¸¸°Ç Á¤µµ´Â ¼ø½Ä°£¿¡ ã¾ÆÁÙ Á¤µµ´Ù. ±×¸®°í ¾Ë°í¸®ÁòÀÇ °£´ÜÇÔÀ¸·Î ÀÎÇØ ¹ö±×°¡ ¹ß»ýÇÒ Æ´ÀÌ ¾ø¾î ¾ÈÀü¼º°ú °³¹ßÀÚÀÇ ÆíÀǼº ¸é¿¡¼µµ ³ôÀº Á¡¼ö¸¦ ÁÙ ¼ö ÀÖ´Ù. »ç½Ç ¼øÂ÷ °Ë»öÀº Å×À̺í Å©±â°¡ ¼ö¹é°Ç Á¤µµ¶ó¸é ´Ù¸¥ ¹æ¹ýº¸´Ù ¿ÀÈ÷·Á È¿À²ÀûÀÌ¸ç °¡Àå ÀÚÁÖ »ç¿ëµÇ´Â °Ë»ö ¹æ¹ýÀÌ´Ù.