ÇؽÃ(Hash)´Â ÀڷḦ ÀÔ·ÂÇÒ ¶§ºÎÅÍ °Ë»öÇϱ⠽¬¿î À§Ä¡¿¡ »ðÀÔÇÏ´Â ¹æ¹ýÀÌ´Ù. µû¶ó¼ Çؽô °Ë»ö ¹æ¹ýÀ̶ó±âº¸´Ù´Â ºü¸¥ °Ë»öÀ» À§ÇØ ÀڷḦ °ü¸®ÇÏ´Â ±â¹ýÀ̶ó°í º¼ ¼ö ÀÖ´Ù. ½Ç»ýÈ°¿¡¼µµ Çؽà ±â¹ýÀÌ ÈçÈ÷ »ç¿ëµÇ´Âµ¥ ¼öø¿¡ ÁÖ¼Ò·ÏÀ» ÀÛ¼ºÇÒ ¶§ °¡³ª´Ù¼øÀ¸·Î ÆäÀÌÁö¸¦ ¹Ì¸® ºÐ·ùÇÏ°í À̸§ÀÇ Ã¹ ±ÛÀÚ¸¦ ±âÁØÀ¸·Î ÁÖ¼Ò¸¦ Àû´Â ¹æ¹ýÀÌ ¹Ù·Î ÇؽÌÀÌ´Ù.
¼öø¿¡ ¾Æ¹«·¸°Ô³ª ÁÖ¼Ò¸¦ Àû¾î ³õÀ¸¸é »õ ÁÖ¼Ò¸¦ Ãß°¡Çϱâ´Â °£ÆíÇÏÁö¸¸ ´ÙÀ½¿¡ ã±â°¡ ¹«Ã´ ¾î·Á¿öÁú °ÍÀÌ´Ù. ÇÏÁö¸¸ ¼ºº°·Î ºÐ·ùÇØ ³õÀ¸¸é óÀ½¿¡ Á¦ À§Ä¡¸¦ ã¾Æ Àû±â´Â Á» ±ÍÂúÁö¸¸ ´ÙÀ½¿¡ ã¾Æ º¸±â´Â ¾ÆÁÖ ½¬¿öÁø´Ù. ±è°¡, °°¡´Â ¤¡Ä¿¡¼ ã°í Ȳ°¡, ÇÑ°¡´Â ¤¾Ä¿¡¼ ãÀ¸¸é ½±°Ô ãÀ» ¼ö ÀÖ´Ù. ÀÌ·± °Ë»ö ¹æ¹ýÀÌ ¹Ù·Î ÇؽÌÀÌ´Ù.
ÀÚ·á°¡ ÀúÀåµÇ´Â Àüü ÀúÀå¼Ò¸¦ Çؽà Å×À̺í(Hash Table)À̶ó°í ÇÑ´Ù. Çؽà Å×À̺íÀº ¿©·¯ °³ÀÇ ¹öŶ(Bucket)À¸·Î ³ª´©¾îÁö´Âµ¥ ÁÖ¼Ò·Ï ¿¹¿¡¼ ¤¡, ¤¤, ¤§, ¤© °¢ ÆäÀÌÁö°¡ ¹öŶÀÌ´Ù. µ¥ÀÌÅ͸¦ »ðÀÔÇÒ ¶§ µ¥ÀÌÅÍÀÇ °ªÀ¸·ÎºÎÅÍ ÀûÀýÇÑ ¹öŶÀ» ¼±ÅÃÇؼ »ðÀÔÇØ¾ß ÇÑ´Ù. ¹öŶÀº ¶ÇÇÑ ¿©·¯ °³ÀÇ ½½·Ô(Slot)À¸·Î ±¸¼ºµÇ´Âµ¥ ½½·ÔÀº ¹öŶ¿¡ µ¥ÀÌÅÍ°¡ ÀúÀåµÇ´Â ´ÜÀ§ÀÌ´Ù. ÁÖ¼Ò·ÏÀÇ °¢ ÆäÀÌÁöº°·Î ÇÑ ¸í¸¸ ÀûÀ» ¼ö ÀÖ´Â °ÍÀÌ ¾Æ´Ï¶ó ¿©·¯ ¸íÀ» ÀûÀ» ¼ö ÀÖ¾î¾ß Çϴµ¥ À̶§ ÇÑ ¸íÀÇ ÁÖ¼Ò¸¦ Àû´Â ÄÀÌ ½½·ÔÀÌ´Ù.
ÇؽÌÀÇ °¡Àå ±âÃÊÀûÀÎ ¿¬»êÀº ÀÚ·á°¡ »õ·Î ÀÔ·ÂµÉ ¶§ ÀÌ ÀڷḦ ¾î¶² ¹öŶ¿¡ ³ÖÀ»Áö¸¦ °áÁ¤ÇÏ´Â °ÍÀε¥ ÀÌ ¿¬»êÀ» ÇÏ´Â ÇÔ¼ö¸¦ Çؽà ÇÔ¼ö¶ó°í ÇÑ´Ù. Çؽà ÇÔ¼ö´Â ÀÔ·ÂµÈ Å°°ªÀ¸·Î ¹öŶÀÇ ¹øÈ£(Çؽðª)¸¦ ã¾Æ³»´Â ÇÔ¼öÀε¥ »õ·Î ÀڷḦ »ðÀÔÇÒ ¶§ Çؽà ÇÔ¼ö°¡ ¸®ÅÏÇÏ´Â ¹öŶ ¹øÈ£¿¡ ÀڷḦ »ðÀÔÇÑ´Ù. ´ÙÀ½¿¡ ƯÁ¤ ÀڷḦ °Ë»öÇÒ ¶§´Â ´Ù½Ã Çؽà ÇÔ¼ö·Î ¹öŶ ¹øÈ£¸¦ ã¾Æ ¿©±â¿¡ ¿øÇÏ´Â ÀÚ·á°¡ ÀÖ´ÂÁö¸¦ º¸¸é µÈ´Ù.
ÁÖ¼Ò·Ï ¿¹¿¡¼ Çؽà ÇÔ¼ö´Â À̸§ÀÇ Ã¹±ÛÀÚ ÀÚÀ½À¸·ÎºÎÅÍ ¹öŶ ¹øÈ£¸¦ ã´Â´Ù. ±è ¾Æ¹«°³´Â ¤¡Ä¿¡, Àå ¾Æ¹«°³´Â ¤¸ÄÀ» ã¾Æ ¼±ÅÃµÈ ¹öŶ¿¡ ÀڷḦ »ðÀÔÇÏ´Â ½ÄÀÌ´Ù. ÀÌ·¸°Ô °ü¸®µÇ´Â ÁÖ¼Ò·Ï¿¡¼ "À屺"À̶ó´Â »ç¶÷ÀÇ ÁÖ¼Ò¸¦ ¾Ë°í ½Í´Ù¸é "À屺"À» ´Ù½Ã Çؽà ÇÔ¼ö·Î ³Ö¾î ¤¸¹öŶÀ» ã°í ÀÌ ÆäÀÌÁö¸¸ °Ë»öÇÏ¸é ½±°Ô ãÀ» ¼ö ÀÖ´Ù. ´ÙÀ½Àº ÇؽÃÀÇ ±âº» µ¿ÀÛ ¿ø¸®¸¦ º¸¿©ÁÖ´Â ¾ÆÁÖ °£´ÜÇÑ ¿¹Á¦ÀÌ´Ù. Çؽÿ¡ µé¾î°¡´Â ¼ö°¡ ¾çÀÇ Á¤¼ö »ÓÀ̶ó°í °¡Á¤ÇÏ°í 0Àº ¹öŶÀÌ ºñ¾î Àִٴ ƯÀÌ°ªÀ¸·Î »ç¿ëÇÑ´Ù.
¿¹ Á¦ : Hashing |
#include <Turboc.h>
#define BK 10
#define SL 1
int hashtable[BK][SL];
int hash(int key)
{
return key % 10;
}
void AddKey(int key)
{
int bucket;
bucket=hash(key);
if (hashtable[bucket][0] == 0) {
hashtable[bucket][0]=key;
}
}
BOOL FindKey(int key)
{
int bucket;
bucket=hash(key);
return (hashtable[bucket][0]==key);
}
void main()
{
int i,key;
memset(hashtable,0,sizeof(hashtable));
for (i=0;i<5;i++) {
printf("%d¹ø° °ªÀ» ÀÔ·ÂÇϼ¼¿ä : ",i+1);scanf("%d",&key);
AddKey(key);
}
printf("°Ë»öÇÒ Å°¸¦ ÀÔ·ÂÇϼ¼¿ä : ");scanf("%d",&key);
if (FindKey(key)) {
puts("°Ë»öµÇ¾ú½À´Ï´Ù.");
} else {
puts("ÀÔ·ÂÇϽŠ°ªÀº ¾ø½À´Ï´Ù..");
}
}
Çؽà ÇÔ¼ö hash´Â Å°ÀÇ ¸¶Áö¸· ÀÚ¸® ¼ö Çϳª¸¸À¸·Î ÇؽðªÀ» °è»êÇϴµ¥ ÀÌ´Â % ¿¬»êÀÚ·Î ½±°Ô ±¸ÇÒ ¼ö ÀÖ´Ù. 15´Â 5¸¦, 347Àº 7À», 83Àº 3À» ¼±ÅÃÇÒ °ÍÀÌ´Ù. 10À¸·Î ³ª´« ³ª¸ÓÁö¸¦ ÇؽðªÀ¸·Î ¼±ÅÃÇϹǷΠ¹öŶÀº 10°³¸¦ ÁغñÇÏ¸é µÈ´Ù. ±×·¡¼ Çؽà Å×À̺íÀÇ ¹öŶ ¼ö´Â 10À¸·Î Á¤ÀÇÇßÀ¸¸é Ãæµ¹ Çö»óÀ» ½±°Ô °üÂûÇϱâ À§ÇØ ½½·ÔÀº ÀϺη¯ 1·Î Á¤ÀÇÇØ µÎ¾ú´Ù.
AddKey ÇÔ¼ö´Â ÀÔ·ÂµÈ Å°·ÎºÎÅÍ hash ÇÔ¼ö¸¦ È£ÃâÇÏ¿© ÇؽðªÀ» ã°í ÀÌ ¹öŶÀÌ ºñ¾î ÀÖÀ» ¶§ Çؽà Å×ÀÌºí¿¡ µ¥ÀÌÅ͸¦ Ãß°¡ÇÑ´Ù. ¸¸¾à ÀÌ¹Ì ¹öŶÀÌ Á¡·ÉµÇ¾î ÀÖ´Ù¸é °ªÀ» Ãß°¡ÇÒ ¼ö ¾ø´Ù. FindKey ÇÔ¼ö´Â Å°°¡ Çؽà Å×ÀÌºí¿¡ ÀÖ´ÂÁö¸¸ Á¶»çÇϴµ¥ ÇؽðªÀ» ¸ÕÀú ã°í ¹öŶ¿¡ µé¾îÀÖ´Â °ª°ú Å°°ªÀ» ºñ±³ÇÑ °á°ú¸¦ ¸®ÅÏÇÑ´Ù. Á¸Àç ¿©ºÎ¸¸À» Á¶»çÇϵµ·Ï Çߴµ¥ ½ÇÁ¦ ¿¹¿¡¼´Â Å°°¡ µé¾îÀÖ´Â ¹öŶ°ú ½½·Ô ¹øÈ£¸¦ ¸®ÅÏÇÏ´Â °ÍÀÌ ´õ ½Ç¿ëÀûÀÌ´Ù.
main ÇÔ¼ö´Â Çؽà Å×À̺íÀ» 0À¸·Î ¸ðµÎ ÃʱâÈÇÏ¿© ºñ¿ì´Âµ¥ ¸¸¾à ÀÌ Å×ÀÌºí¿¡ 0µµ ÀÔ·ÂµÉ ¼ö ÀÖ´Ù¸é -1 µîÀÇ ´Ù¸¥ ƯÀÌ°ªÀ¸·Î ÃʱâÈÇØ¾ß ÇÒ °ÍÀÌ´Ù. ±×¸®°í ´Ù¼¸ °³ÀÇ °ªÀ» ÀÔ·Â¹Þ¾Æ Çؽà Å×ÀÌºí¿¡ Ãß°¡ÇÏ°í °Ë»öÇÒ Å°¸¦ ÀԷ¹ÞÀº ÈÄ FindKey ÇÔ¼ö·Î ÀÌ °ªÀÌ Çؽà Å×ÀÌºí¿¡ µé¾î ÀÖ´ÂÁö Á¶»çÇÑ´Ù. ¿¹Á¦¸¦ ½ÇÇàÇØ º¸ÀÚ.
1¹ø° °ªÀ» ÀÔ·ÂÇϼ¼¿ä : 7
2¹ø° °ªÀ» ÀÔ·ÂÇϼ¼¿ä : 28
3¹ø° °ªÀ» ÀÔ·ÂÇϼ¼¿ä : 942
4¹ø° °ªÀ» ÀÔ·ÂÇϼ¼¿ä : 69
5¹ø° °ªÀ» ÀÔ·ÂÇϼ¼¿ä : 33
°Ë»öÇÒ Å°¸¦ ÀÔ·ÂÇϼ¼¿ä : 28
°Ë»öµÇ¾ú½À´Ï´Ù.
´Ù¼¸ °³ÀÇ °ªÀ» ÀÔ·ÂÇߴµ¥ °¢ ÀԷ¿¡ ÀÇÇØ AddKey ÇÔ¼ö´Â µÞÀÚ¸® ¹øÈ£¿¡ ÇØ´çÇÏ´Â ¹öŶ¿¡ °ªÀ» ÀúÀåÇÑ´Ù. ÀÔ·ÂÀÌ ¿Ï·áµÈ ÈÄ Çؽà Å×À̺íÀº ´ÙÀ½°ú °°Àº »óÅ°¡ µÉ °ÍÀÌ´Ù.
ÀÌ »óÅ¿¡¼ 28ÀÌ ÀÖ´ÂÁö °Ë»öÇÏ´Â ¹æ¹ýÀº ¾ÆÁÖ °£´ÜÇÏ°í ºü¸£´Ù. Çؽà ÇÔ¼ö·Î 28ÀÌ µé¾î°¥ ¹öŶ ¹øÈ£¸¦ ã°í ÀÌ ¹öŶ¿¡ °ú¿¬ 28ÀÌ µé¾î ÀÖ´ÂÁö¸¸ Á¡°ËÇÏ¸é µÈ´Ù. FindKey´Â 28ÀÌ µé¾î°¥ 8¹ø ¹öŶ¸¸ º¸¸é ÀÌ °ªÀÇ Á¸Àç À¯¹«¸¦ ½±°Ô ¾Ë ¼ö ÀÖ´Ù. Çؽà Å×À̺íÀÌ ¾Æ¹«¸® Å©°í µ¥ÀÌÅÍ°¡ ¸¹´Ù ÇÏ´õ¶óµµ °Ë»ö ½Ã°£Àº »ó¼ö·Î Ç×»ó ÀÏÁ¤ÇÏ´Ù. °Ë»ö ½Ã°£À¸·Î¸¸ º»´Ù¸é Çؽô ¸ðµç °Ë»ö ¾Ë°í¸®Áò Áß¿¡ °¡Àå ºü¸£´Ù.
±×·¯³ª Çؽ̵µ ¿©·¯ °¡Áö ¹®Á¦Á¡ÀÌ Àִµ¥ °¡Àå Å« ¹®Á¦´Â ¹öŶ³¢¸® Ãæµ¹ÇÒ ¼ö ÀÖ´Ù´Â Á¡ÀÌ´Ù. »õ·Î »ðÀÔÇÏ°íÀÚ ÇÏ´Â Å°ÀÇ ¹öŶÀÌ ÀÌ¹Ì Á¡·ÉµÇ¾î ÀÖ´Ù¸é ÀÌ Å°´Â Çؽà Å×ÀÌºí¿¡ Ãß°¡ÇÒ ¼ö ¾ø´Ù. ¿¹¸¦ µé¾î 38ÀÌ 8¹ø ¹öŶ¿¡ ÀÌ¹Ì µé¾î ÀÖÀ» ¶§ 48À̳ª 58ÀÌ ÀԷµǸé ÀÌ °ªÀ» ÀúÀåÇÒ ¹öŶÀÌ ¾ø´Â °ÍÀÌ´Ù. ¹öŶÀÌ ÀÌ¹Ì Á¡·ÉµÇ¾î °ªÀ» Ãß°¡ÇÒ ¼ö ¾ø´Â »óȲÀ» Ãæµ¹(Collision)À̶ó°í ÇÑ´Ù. ÀÌ Ãæµ¹À» ¾î¶»°Ô ÇØ°áÇÒ °ÍÀΰ¡°¡ ÇؽÌÀÇ °ü°ÇÀÌ¸ç ¹°·Ð ´Ù¼öÀÇ ÇÕ¸®ÀûÀÎ ÇØ°á ¹æ¹ýÀÌ ÀÖ´Ù.
¾ÕÀÇ ¿¹Á¦´Â Ãæµ¹ Çö»óÀ» ½±°Ô ¸ñ°ÝÇϱâ À§ÇØ ½½·Ô Å©±â¸¦ ÀϺη¯ 1·Î ¼³Á¤Çߴµ¥ ½½·ÔÀ» ÃæºÐÈ÷ Å©°Ô Àâ±â¸¸ Çصµ Ãæµ¹À» ¸¹ÀÌ ¿ÏȽÃų ¼ö ÀÖ´Ù. ¹öŶÀÇ ½½·ÔÀÌ Ä¿Áö¸é ¼³»ç Ãæµ¹ÀÌ ¹ß»ýÇÏ´õ¶óµµ ´ÙÀ½ ½½·Ô¿¡ µ¥ÀÌÅ͸¦ ÀúÀåÇÒ ¼ö ÀÖÀ¸¹Ç·Î ½½·Ô Å©±â¸¦ ÃÊ°úÇÏ´Â µ¥ÀÌÅÍ°¡ ÀÔ·ÂµÉ ¶§¸¸ ¹®Á¦°¡ ¹ß»ýÇÑ´Ù. ½½·Ô Å©±â¸¦ ´Ã¸®¸é µ¥ÀÌÅ͸¦ Ãß°¡ ¹× °Ë»öÇÏ´Â ÇÔ¼öµµ ´ÙÁß ½½·ÔÀ» Áö¿øÇϵµ·Ï ¼öÁ¤ÇØ¾ß ÇÑ´Ù.
¿¹ Á¦ : MultiSlot |
#include <Turboc.h>
#define BK 10
#define SL 3
int hashtable[BK][SL];
int hash(int key)
{
return key % 10;
}
void AddKey(int key)
{
int i,bucket;
bucket=hash(key);
for (i=0;i<SL;i++) {
if (hashtable[bucket][i]==0) {
hashtable[bucket][i]=key;
break;
}
}
}
BOOL FindKey(int key)
{
int i,bucket;
bucket=hash(key);
for (i=0;i<SL;i++) {
if (hashtable[bucket][i]==key) {
return TRUE;
}
}
return FALSE;
}
====================== mainÀº µ¿ÀÏÇϹǷΠ»ý·« ======================
AddKey ÇÔ¼ö´Â ÀÏ´Ü ÇؽðªÀ» ãÀº ÈÄ ½½·Ô Å©±â¸¸Å ·çÇÁ¸¦ µ¹¸ç ºó ÀÚ¸®¸¦ ã¾Æ »õ·Î¿î Å°¸¦ »ðÀÔÇÑ´Ù. ¹öŶ¿¡ ÀÌ¹Ì °ªÀÌ µé¾î ÀÖ´õ¶óµµ ¿©À¯ ½½·ÔÀÌ ÀÖ´Ù¸é ÀÌ ½½·Ô¿¡ »õ µ¥ÀÌÅ͸¦ Ãß°¡ÇÒ ¼ö ÀÖÀ» °ÍÀÌ´Ù. 12, 76, 542, 126, 96 ¼øÀ¸·Î µ¥ÀÌÅÍ°¡ ÀԷµǾú´Ù¸é Çؽà Å×À̺íÀº ´ÙÀ½°ú °°ÀÌ ±¸¼ºµÈ´Ù.
2¿Í 6ÀÚ¸®¿¡ µ¥ÀÌÅÍ°¡ ¸ô¸®´õ¶óµµ ½½·ÔÀÌ ÃæºÐÇϱ⠶§¹®¿¡ ÀÏ´ÜÀº Ãæµ¹À» ¹æÁöÇÒ ¼ö ÀÖ´Ù. ´Ü, ºó ½½·ÔÀÌ Çϳªµµ ¾ø´Ù¸é À̶§´Â »ðÀÔ¿¡ ½ÇÆÐÇÏ¸ç ¿©ÀüÈ÷ Ãæµ¹ÀÌ ¹ß»ýÇÑ´Ù. À§ ±×¸²¿¡¼ »õ·Î 36ÀÌ ÀԷµȴٸé Ãæµ¹À» ¸éÇÒ ¼ö ¾ø´Ù. ½½·ÔÀÌ ¾Æ¹«¸® ¸¹¾Æµµ ÇÑ ¹öŶ¿¡ ÀԷµǴ µ¥ÀÌÅÍÀÇ ¾çÀÌ ¸¹À¸¸é ¾î¿ ¼ö ¾ø´Â °ÍÀÌ´Ù.
ÁÖ¼Ò·Ï¿¡¼µµ ÀÌ·± Çö»óÀº ½±°Ô ¸ñ°ÝÇÒ ¼ö ÀÖ´Ù. °¡³ª´Ù ¼øÀ¸·Î ÆäÀÌÁö¸¦ ³ª´©¾î »ç¶÷ À̸§À» Àû´Âµ¥ ´Ù¸¥ ÆäÀÌÁö´Â ³²¾Æ µ¹¾Æµµ ¤¡, ¤· ÆäÀÌÁö´Â ±Ý¹æ °¡µæ Â÷¼ ´õ ÀûÀ» µ¥°¡ ¾ø°Ô µÈ´Ù. ½½·ÔÀÌ ÃæºÐÇصµ ÀԷµǴ µ¥ÀÌÅÍ°¡ ¸¹À¸¸é ÀÌ Ãæµ¹Àº ¾î¿ ¼ö ¾ø´Â °ÍÀÌ´Ù. ±×·¡¼ ´ÙÁß ½½·ÔÀº Ãæµ¹À» Áö¿¬½ÃÅ°±â´Â Çصµ ¿Ïº®ÇÏ°Ô ÇØ°áÇÏÁö´Â ¸øÇÑ´Ù. °Ô´Ù°¡ ½½·ÔÀÌ ¸¹¾ÆÁö¸é Ãß°¡, °Ë»ö ÇÔ¼ö°¡ º¹ÀâÇØÁö±â ¶§¹®¿¡ ½ÇÁ¦ ÇؽÌÀ» ÇÒ ¶§´Â ½½·ÔÀº Çϳª¸¸ ¾²°í ´Ù¸¥ ¹æ¹ýÀ» »ç¿ëÇÏ´Â °ÍÀÌ ´õ ÀϹÝÀûÀÌ´Ù.
Çؽà Å×À̺íÀÌ ¾Æ¹«¸® Ä¿µµ Ãæµ¹Àº ¹ß»ýÇÒ ¼ö Àִµ¥ ÀÌ Ãæµ¹À» °¡±ÞÀû ´ÊÃß°í ¹öŶÀ» °ñ°í·ç »ç¿ëÇÏ·Á¸é Å°·ÎºÎÅÍ ÇؽðªÀ» ã´Â Çؽà ÇÔ¼ö°¡ Á¤±³ÇØ¾ß ÇÑ´Ù. ³ª¸ÓÁö ¿¬»êÀÚ·Î ³¡ ÀÚ¸®¸¸ º¸´Â °£´ÜÇÑ ¹æ¹ýÀº ±ÕÀÏÇÑ ÇؽðªÀ» ¸¸µé¾î ³»´Âµ¥´Â ÇÑ°è°¡ ÀÖ´Ù. ¿¹¸¦ µé¾î Çؽà Å×ÀÌºí¿¡ ÀúÀåµÇ´Â µ¥ÀÌÅÍ°¡ Á¡¼ö°ªÀ̶ó°í ÇÏÀÚ. ¹®Á¦°¡ 100°³°¡ ¾Æ´Ñ ÇÑ Á¡¼ö´Â º¸Åë 1´ÜÀ§ÀÎ °æ¿ìº¸´Ù 2³ª 4´ÜÀ§ÀÎ °æ¿ì°¡ ¸¹Àºµ¥ ÀÌ·¸°Ô µÇ¸é ¦¼ö ¹öŶ¿¡¸¸ µ¥ÀÌÅÍ°¡ ¸ô¸®°Ô µÉ °ÍÀÌ°í Ȧ¼ö ¹öŶÀº ÅÖÅÖ ºô °ÍÀÌ´Ù. ÀÌ·¸°Ô µÇ¸é Ãæµ¹ÀÌ ±Ý¹æ ¹ß»ýÇÒ »Ó¸¸ ¾Æ´Ï¶ó ±â¾ï Àå¼Òµµ ³¶ºñµÈ´Ù.
ÁÖ¼Ò·ÏÀÇ °æ¿ìµµ ¸¶Âù°¡Áö·Î ù ±ÛÀÚÀÇ ÀÚÀ½À» ÇؽðªÀ¸·Î ¾²¸é ¤¡, ¤², ¤· ¹öŶÀº ±Ý¹æ ¹Ù´Ú³ª°í ¤©, ¤», ¤¼ ¹öŶÀº ³²¾Æµ¹ °ÍÀÌ´Ù. ¾Ë´Ù½ÃÇÇ ¿ì¸®³ª¶ó¿¡°Ô´Â ±è°¡, ÀÌ°¡, ¹Ú°¡°¡ ƯÈ÷ ¸¹´Ù. ù ±ÛÀÚÀÇ ÀÚÀ½º¸´Ù´Â Áß°£ ±ÛÀÚÀÇ ÀÚÀ½À» º¸´Â ¹æ¹ýÀÌ Â÷¶ó¸® ´õ ÇÕ¸®ÀûÀÎ Çؽà ÇÔ¼ö°¡ µÉ °ÍÀ̸ç Á» ´õ Á¤±³ÇÏ°Ô ¸¸µé¸é ¹®ÀÚ ÄÚµåÀÇ ÃÑÇÕÀ» ±¸ÇØ % ¿¬»êÀ» ÃëÇÏ´Â ¹æ¹ýµµ »ý°¢ÇÒ ¼ö ÀÖ´Ù.
¹Ù¶÷Á÷ÇÑ Çؽà ÇÔ¼ö´Â ÀԷµǴ ÀÓÀÇÀÇ °ªÀ¸·ÎºÎÅÍ ±ÕÀÏÇÑ ÇؽðªÀ» ¸¸µé¾î ³»¾ß ÇÑ´Ù. ¶ÇÇÑ »ðÀÔ°ú °Ë»ö ¼Óµµ¿¡ Á÷Á¢ÀûÀÎ ¿µÇâÀ» ¹ÌÄ¡¹Ç·Î ³Ê¹« º¹ÀâÇؼµµ ¾ÈµÇ¸ç ÇؽðªÀ» ½Å¼ÓÇÏ°Ô °è»êÇÒ ¼ö ÀÖ¾î¾ß ÇÑ´Ù. Çؽà ÇÔ¼ö¸¦ ¸¸µå´Â ¿©·¯ °¡Áö ¿¬»ê ¹æ¹ýµéÀÌ °³¹ßµÇ¾î Àִµ¥ ÀԷ°ªÀ» Á¦°öÇѴٰųª ½¬ÇÁÆ®, ºñÆ® ¿¬»êÀ¸·Î ÀϺΠºñÆ®¸¸ ÃëÇÏ´Â °£´ÜÇÑ ¹æ¹ý¿¡¼ºÎÅÍ ÀԷµǴ °ªµéÀÇ ºÐ»ê, Ç¥ÁØ ÆíÂ÷ µîÀ» È°¿ëÇÏ´Â ¼öÇÐÀûÀÎ ¹æ¹ýµµ ÀÖ´Ù. ´õÇÏ°í °öÇÏ°í ³ª´©°í µ¹¸®°í ºñƲ°í ²¿°í ¾îÂîÇϵ簣¿¡ ±ÕÀÏÇÑ Çؽ𪸸 ¸¸µé¾î ³»¸é µÈ´Ù.
ÇؽðªÀº º¹¿ø °¡´ÉÇÏÁö ¾Ê¾Æµµ »ó°ü¾ø´Ù. Áï ÇؽðªÀ¸·ÎºÎÅÍ Å°¸¦ ´Ù½Ã ãÀ» ¼ö ¾ø´õ¶óµµ ¹®Á¦µÇÁö ¾Ê´Â´Ù. Å°·ÎºÎÅÍ ¾ò´Â ÇؽðªÀÌ ÀÏÁ¤Çϱ⸸ ÇÏ´Ù¸é »ðÀÔÇÑ À§Ä¡ÀÇ ¹öŶ ¹øÈ£¸¦ ¾ðÁ¦µçÁö ãÀ» ¼ö ÀÖ°í ÀÌ ¹öŶ¿¡¼ ÀúÀåµÈ Å°¸¦ ÀÐÀ» ¼ö Àֱ⠶§¹®ÀÌ´Ù. Á¡¼ö µ¥ÀÌÅÍÀÇ °æ¿ì ½ÊÀÚ¸®¿Í ÀÏÀÚ¸®¸¦ ´õÇØ ³ª¸ÓÁö ¿¬»êÀ» Àû¿ëÇϱ⸸ Çصµ ÈξÀ ´õ ±ÕÀÏÇÑ ÇؽðªÀ» ¾òÀ» ¼ö ÀÖ´Ù.
int hash(int score)
{
return (score / 10 + score % 10) % 10;
}
¸ðµç °æ¿ì¿¡ ´ëÇØ Àß µ¿ÀÛÇÏ´Â ±×·± Çؽà ÇÔ¼ö´Â ¾ø´Ù. ÀúÀåÇÏ´Â °ªÀÇ ¼ºÁúÀ» Àß ºÐ¼®ÇÑ ÈÄ¿¡ °ªµéÀ» °ñ°í·ç ºÐ»ê½Ãų ¼ö ÀÖ´Â Çؽà ÇÔ¼ö¸¦ ã¾Æ¾ß ÇÑ´Ù. Á¤±³ÇÑ Çؽà ÇÔ¼ö´Â Ãæµ¹À» ÃÖ¼ÒÈÇÏ°í ±â¾ï Àå¼Ò¸¦ È¿À²ÀûÀ¸·Î »ç¿ëÇÏ´Â ¹æ¹ý Áß ÇϳªÀ̱â´Â ÇÏÁö¸¸ Ãæµ¹À» ±Ùº»ÀûÀ¸·Î ÇØ°áÇÏÁö´Â ¸øÇÑ´Ù.
½½·ÔÀÌ ³Ë³ËÇÏ°í Çؽà ÇÔ¼ö°¡ Á¤±³Çصµ Ãæµ¹Àº ¾ðÁ¦³ª ¹ß»ýÇÒ °¡´É¼ºÀÌ ÀÖ´Ù. ±×·¡¼ Ãæµ¹ÀÌ ¹ß»ýÇÒ ¶§ÀÇ ´ëó »óȲÀ» Á¤ÀÇÇØ¾ß Çϴµ¥ ¼±Çü Ž»ö¹ýÀÌ ±× Áß °¡Àå °£´ÜÇÑ ¹æ¹ýÀÌ´Ù. ¼±Çü Ž»ö¹ý(Linear Probing)Àº Ãæµ¹ÀÌ ¹ß»ýÇÒ °æ¿ì ÀÌ µ¥ÀÌÅ͸¦ ¹ö¸®Áö ¾Ê°í ´Ù¸¥ ¹öŶ¿¡¶óµµ ´ë½Å Áý¾î ³Ö´Â ¹æ¹ýÀÌ´Ù. Áï, ²æ ´ë½Å ´ßÀ» ã´Â ¹æ¹ýÀε¥ ±×·¸´Ù°í Çؼ ¾Æ¹« °÷¿¡³ª ³Ö¾î¼´Â ¾ÈµÇ¸ç °Ë»ö ÇÔ¼ö°¡ ãÀ» ¼ö ÀÖ´Â °÷À̾î¾ß ÇÑ´Ù.
´ëü ¹öŶÀ» ã´Â °¡Àå °£´ÜÇÑ ¹æ¹ýÀº ¹Ù·Î ¿·Ä¿¡ Àû¾î ³õ´Â °ÍÀÌ´Ù. ±×·¯¸é °Ë»ö ÇÔ¼ö°¡ ¹öŶ¿¡¼ ãÁö ¸øÇßÀ» ¶§ ¿·Äµµ °°ÀÌ Ã£¾Æ º¼ °ÍÀÌ´Ù. ÁÖ¼Ò·ÏÀÇ °æ¿ìµµ ¤¡ÄÀÌ ¸ðÀÚ¶ó¸é ¤¤ÄÀ» Àá½Ã ºô·Á ¾µ ¼ö ÀÖ´Ù. À̶§ ¹Ýµå½Ã ¿·Ä¿¡ Àû¾î¾ßÁö ¤», ¤¼°°Àº ¾û¶×ÇÑ °÷¿¡ Àû¾î ³õÀ¸¸é °Ë»öÀº °ÅÀÇ ºÒ°¡´ÉÇØÁú °ÍÀÌ´Ù. ´ÙÀ½ ¿¹Á¦´Â ¼±Çü Ž»öÀÇ ¿¹¸¦ º¸¿©Áִµ¥ Ãæµ¹ÀÇ ÀçÇöÀ» ½±°Ô Çϱâ À§ÇØ ½½·Ô Å©±â´Â ´Ù½Ã 1·Î ¼³Á¤Çß´Ù.
¿¹ Á¦ : LinearProbe |
#include <Turboc.h>
#define BK 10
#define SL 1
int hashtable[BK][SL];
int hash(int key)
{
return key % 10;
}
void AddKey(int key)
{
int bucket;
bucket=hash(key);
while (hashtable[bucket][0]!=0) {
bucket=bucket+1 % BK;
}
hashtable[bucket][0]=key;
}
BOOL FindKey(int key)
{
int bucket;
bucket=hash(key);
while (hashtable[bucket][0]!=0) {
if (hashtable[bucket][0]==key) return TRUE;
bucket=bucket+1 % BK;
}
return FALSE;
}
====================== mainÀº µ¿ÀÏÇϹǷΠ»ý·« ======================
´ÙÀ½Àº ½ÇÇà °á°úÀÌ´Ù.
1¹ø° °ªÀ» ÀÔ·ÂÇϼ¼¿ä : 11
2¹ø° °ªÀ» ÀÔ·ÂÇϼ¼¿ä : 12
3¹ø° °ªÀ» ÀÔ·ÂÇϼ¼¿ä : 22
4¹ø° °ªÀ» ÀÔ·ÂÇϼ¼¿ä : 66
5¹ø° °ªÀ» ÀÔ·ÂÇϼ¼¿ä : 77
°Ë»öÇÒ Å°¸¦ ÀÔ·ÂÇϼ¼¿ä : 22
°Ë»öµÇ¾ú½À´Ï´Ù.
AddKey ÇÔ¼ö´Â ÀÔ·ÂµÈ µ¥ÀÌÅÍÀÇ ¹öŶ ¹øÈ£¸¦ Á¶»çÇÏ¿© ¿©±â¿¡ µ¥ÀÌÅ͸¦ ³ÖµÇ ¸¸¾à ÀÌ ¹öŶÀÌ ºñ¾î ÀÖÁö ¾Ê´Ù¸é ´ÙÀ½ ¹öŶÀ» Á¶»çÇÑ´Ù. ¸¸¾à ´ÙÀ½ ¹öŶµµ ºñ¾î ÀÖÁö ¾Ê´Ù¸é ±× ´ÙÀ½ ºó ¹öŶÀ» °è¼ÓÇؼ ã¾Æ ÃÖÃÊ·Î ºó ¹öŶ¿¡ °ªÀ» ½á ³Ö´Â´Ù. Çؽà Å×À̺í Àüü°¡ °¡µæ Â÷Áö ¾ÊÀº ÇÑ ÀÌ °ªÀÌ µé¾î°¥ ¹öŶÀ» ¾ðÁ¨°¡´Â ã°Ô µÉ °ÍÀÌ´Ù. À§ ½ÇÇà ¿¹¿¡¼ 11, 12±îÁö´Â Á¦ ÀÚ¸®¸¦ ã¾Æ µé¾î °¡Áö¸¸ 22°¡ µé¾î°¥ 2¹ø ¹öŶÀÌ 12¿¡ ÀÇÇØ ÀÌ¹Ì Á¡·É´çÇßÀ¸¹Ç·Î 22´Â ´ÙÀ½ ÄÀÎ 3¹ø ¹öŶ¿¡ µé¾î°£´Ù.
¸¸¾à 3¹ø ¹öŶ¿¡µµ °ªÀÌ µé¾î ÀÖ´Ù¸é ±× ´ÙÀ½ ¹öŶÀ» ãÀ» °ÍÀÌ´Ù. ¶ÇÇÑ 22°¡ 3¹ø ¹öŶ¿¡ µé¾î°¡ ÀÖ´Â »óÅ¿¡¼ 53°°Àº °ªÀÌ ÀԷµȴٸé ÀÌ °ªÀº Á¦ ÀÚ¸®ÀÎ 3¹ø¿¡ µé¾î°¡Áö ¸øÇÏ°í ´ÙÀ½ ¹öŶ¿¡ µé¾î°¡¾ß ÇÑ´Ù. AddKey´Â ÀÌ·± ½ÄÀ¸·Î Ãæµ¹ ¹ß»ý½Ã ´Ü¼øÈ÷ ±× ´ÙÀ½ ÄÀ» »ç¿ëÇÑ´Ù. ¸¸¾à ºó ÄÀÌ Çϳªµµ ¾ø´Ù¸é ¹«ÇÑ ·çÇÁ¿¡ ºüÁ® ¹ö¸®´Â ¹®Á¦°¡ Àִµ¥ ÀÌ ¹®Á¦´Â ÃÖÃÊ ¹öŶÀ» ±â¾ïÇß´Ù°¡ ÀÌ ÀÚ¸®·Î ´Ù½Ã µ¹¾Æ ¿ÔÀ» ¶§ ¿¡·¯ ó¸®ÇÔÀ¸·Î½á ÀÏ´Ü ÇØ°áÇÒ ¼ö ÀÖ´Ù. ±×·¯³ª ¹«ÇÑ ·çÇÁ¸¸ ÇØ°áÇßÀ» »ÓÀÌÁö µ¥ÀÌÅÍ »ðÀÔÀº ½ÇÆÐÇϹǷΠÇؽà Å×À̺íÀ» ´õ Å©°Ô ¸¸µé°Å³ª ¾Æ´Ï¸ç Çؽà Å×ÀÌºíº¸´Ù ´õ ¸¹Àº ÀڷḦ »ðÀÔÇÏÁö ¾Êµµ·Ï ÇÏ´Â °ÍÀÌ ±Ùº»ÀûÀ¸·Î ¿Ç´Ù.
FindKey ÇÔ¼ö´Â ƯÁ¤ Å°°¡ ÀÖ´ÂÁö °Ë»çÇÒ ¶§ Çؽ𪿡 ÇØ´çÇÏ´Â ¹öŶ¸¸ º¸¾Æ¼´Â ¾ÈµÇ¸ç ´ÙÀ½ ¹öŶ°ú ±× ´ÙÀ½ ¹öŶ±îÁöµµ ºÁ¾ß ÇÑ´Ù. ±×·¡¼ ºó ¹öŶÀ» ¸¸³¯ ¶§±îÁö ·çÇÁ¸¦ µ¹¸ç Å°¸¦ ã¾Æ º¸°í ±×·¡µµ ¾øÀ» ¶§¸¸ È®½ÇÇÏ°Ô ¾ø´Ù´Â °á°ú¸¦ ¸®ÅÏÇÑ´Ù. ¼±Çü Ž»ö¹ýÀº »èÁ¦¿¡ ¹«Ã´ Ãë¾àÇÑ ¾Ë°í¸®ÁòÀε¥ FindKey°¡ ºóÄÀ» ãÀ» ¶§±îÁö °Ë»öÀ» Çϵµ·Ï µÇ¾î ÀÖ¾î »èÁ¦ÇÒ ¶§ ºóÄÀ¸·Î ¸¸µé¾î¼´Â ¾ÈµÈ´Ù. ¿¹¸¦ µé¾î 12, 22, 32, 42±îÁö ÀÔ·ÂÇÑ ÈÄ 22¸¦ Áö¿ì°í 32¸¦ ã´Â´Ù°í ÇØ º¸ÀÚ.
22, 32, 42¸¦ »ðÀÔÇÒ ¶§ Ãæµ¹ÀÌ ¹ß»ýÇϹǷΠ±× ´ÙÀ½ Ä¿¡ ÀÌ °ªµéÀ» ±â·ÏÇß´Ù. ÀÌ·¸°Ô ÇÏ´õ¶óµµ FindKey°¡ ¿¬¼ÓµÈ ¿·ÄÀ» ãµµ·Ï µÇ¾î ÀÖÀ¸¹Ç·Î ÀÏ´ÜÀº ¹®Á¦°¡ ¾ø´Ù. ±×·¯³ª 22°¡ »èÁ¦µÇ¾î ¹ö¸®¸é FindKey°¡ ¹öŶ 3¿¡¼ °Ë»öÀ» ÁßÁöÇϹǷΠ32, 42´Â ¾ø´Â °ªÀ¸·Î Ãë±ÞµÇ¾î ¹ö¸± °ÍÀÌ´Ù. ±×·¡¼ »èÁ¦ÇÒ ¶§ ºóÄÀ¸·Î ¸¸µé¾î¼´Â ¾ÈµÇ¸ç -1 µîÀÇ Æ¯ÀÌ°ªÀ¸·Î »èÁ¦µÈ ÄÀÓÀ» ¸í½ÃÇÏ°í FindKey´Â »èÁ¦µÈ Ä ÀÌÈĵµ °è¼Ó °Ë»öÇϵµ·Ï ÇØ¾ß ÇÑ´Ù.
ÀÌ ¿¹Á¦ÀÇ ¼±Çü Ž»ö¹ýÀº Ãæµ¹ ¹ß»ý½Ã ¹Ù·Î ¿À¸¥ÂÊ ÄÀ» »ç¿ëÇϴµ¥ ¹Ýµå½Ã ±×·² ÇÊ¿ä´Â ¾ø´Ù. ¿ÞÂÊ ÄÀ» »ç¿ëÇÒ ¼öµµ ÀÖ°í ÀÏÁ¤Ä¾¿ °Ç³Ê ¶Ù¸é¼ ´ÙÀ½ ¹öŶÀ» ãÀ» ¼öµµ ÀÖ´Ù. ÇÑ ¹öŶÀÌ ³ÑÄ¡¸é ÁÖº¯ ¹öŶµµ ³ÑÄ¥ È®·üÀÌ ³ôÀ¸·Î¹Ç ¸î ľ¿ °Ç³Ê ¶Ù¸é Ãæµ¹À» Á» ´õ ÃÖ¼ÒÈÇÒ ¼ö ÀÖÀ» °ÍÀÌ´Ù.
ÀçÇؽõµ ¼±Çü Ž»ö¹ý°ú ±âº»ÀûÀ¸·Î À¯»çÇÑ ¹æ¹ýÀÌ´Ù. ¼±Çü Ž»ö¹ýÀº Ãæµ¹ ¹ß»ý½Ã »ê¼úÀûÀÎ ¿¬»êÀ¸·Î ´Ù¸¥ ÄÀ» ãÁö¸¸ ÀçÇؽùýÀº ´ëü ÄÀ» ã´Â Çؽà ÇÔ¼ö¸¦ º°µµ·Î Çϳª ´õ µÎ´Â ¹æ¹ýÀÌ´Ù. ´ÙÀ½ ¿¹Á¦¸¦ º¸ÀÚ.
¿¹ Á¦ : ReHash |
#include <Turboc.h>
#define BK 10
#define SL 1
int hashtable[BK][SL];
int hash(int key)
{
return key % 10;
}
int hash2(int key)
{
return (key/10 + key%10) % 10;
}
void AddKey(int key)
{
int bucket;
bucket=hash(key);
if (hashtable[bucket][0] != 0) {
bucket=hash2(key);
}
if (hashtable[bucket][0] == 0) {
hashtable[bucket][0]=key;
}
}
BOOL FindKey(int key)
{
int bucket;
bucket=hash(key);
if (hashtable[bucket][0]==key) {
return TRUE;
}
bucket=hash2(key);
if (hashtable[bucket][0]==key) {
return TRUE;
}
return FALSE;
}
====================== mainÀº µ¿ÀÏÇϹǷΠ»ý·« ======================
hash2¶ó´Â ÇÔ¼ö¸¦ Çϳª ´õ Á¤ÀÇÇÏ°í Àִµ¥ ÀÌ ÇÔ¼ö´Â ÀÏÀÚ¸®¿Í ½ÊÀÚ¸®¼ö¸¦ ´õÇÑ °ªÀ» 10À¸·Î ³ª´©±â ¿¬»êÇؼ ¹öŶÀ» ã´Â´Ù. ¿¹¸¦ µé¾î 23Àº 5¸¦, 89´Â 7À» ãÀ» °ÍÀÌ´Ù. AddKey ÇÔ¼ö´Â ¸ÕÀú hash ÇÔ¼ö·Î ÇؽðªÀ» ãµÇ ÀÌ ÀÚ¸®°¡ Á¡·ÉµÇ¾î ÀÖ´Ù¸é hash2 ÇÔ¼ö·Î ´ëü ¹öŶÀ» ã¾Æ ¿©±â¿¡ °ªÀ» ±â·ÏÇÑ´Ù. ¸¸¾à ÀçÇؽø¦ Çߴµ¥µµ Ãæµ¹ÀÌ ¹ß»ýÇÑ´Ù¸é À̶§´Â ¾î¿ ¼ö ¾ø´Ù.
AddKey ÇÔ¼ö°¡ µÎ °³ÀÇ Çؽà ÇÔ¼ö¸¦ »ç¿ëÇϹǷΠFindKey ÇÔ¼ö´Â µÎ Çؽà ÇÔ¼ö°¡ °è»êÇÏ´Â ÇؽðªÀ» ´Ù Á¡°ËÇØ¾ß ÇÑ´Ù. µÑ Áß Çϳª¶óµµ °ªÀÌ Á¸ÀçÇϸé ÀÖ´Â °ÍÀÌ°í µÑ ´Ù ¾ø´Ù¸é Å°°¡ Á¸ÀçÇÏÁö ¾Ê´Â´Ù´Â °ÍÀ» ¾Ë ¼ö ÀÖ´Ù. ÀçÇؽà ¹æ¹ýÀº ¼±Çü Ž»ç¿Í ¸¶Âù°¡Áö·Î Ãæµ¹ ¹ß»ý½Ã ´ëüÄÀ» ã´Â ¹æ¹ýÀε¥ ÇÊ¿äÇÏ´Ù¸é Çؽà ÇÔ¼ö¸¦ ´õ ¸¹ÀÌ µÑ ¼öµµ ÀÖ´Ù. 3Â÷, 4Â÷ Çؽà ÇÔ¼ö±îÁö µÐ´Ù¸é Ãæµ¹ ¹ß»ý È®·üÀº Áö±ØÈ÷ ¶³¾îÁú °ÍÀÌ´Ù.
´Ü, À̶§ ÀçÇؽà ÇÔ¼ö´Â ¿ø·¡ Çؽà ÇÔ¼ö¿Í´Â °¡±ÞÀû ´Ù¸¥ ÇؽðªÀ» °è»êÇϵµ·Ï ÀÛ¼ºÇØ¾ß ÇÑ´Ù. ¸¸¾à À§ ¿¹¿¡¼ hash2 ÇÔ¼ö¸¦ Å°ÀÇ Á¦°ö¿¡ ´ëÇÑ 10ÀÇ ³ª¸ÓÁö¸¦ °è»êÇϵµ·Ï return (key*key)%10À¸·Î ÀÛ¼ºÇÑ´Ù¸é 5³ª 6À¸·Î ³¡³ª´Â Å°¿¡ ´ëÇÑ ÀçÇؽà °á°ú´Â ¿ø·¡¿Í °°¾ÆÁ® ¹ö·Á º° ¼Ò¿ëÀÌ ¾øÀ» °ÍÀÌ´Ù.
µ¿Àû ½½·ÔÀº ½½·ÔÀÇ °³¼ö¸¦ °¡º¯ÀûÀ¸·Î °ü¸®ÇÏ´Â ¹æ¹ýÀÌ´Ù. ¼±Çü Ž»ç³ª ÀçÇؽð¡ Ãæµ¹À» ȸÇÇÇÏ´Â ¹æ¹ýÀ̶ó¸é µ¿Àû ½½·ÔÀº Ãæµ¹¿¡ Àû±ØÀûÀ¸·Î ´ëóÇÏ´Â ¹æ¹ýÀ̶ó°í ÇÒ ¼ö ÀÖ´Ù. ÃÖÃÊ ÀÏÁ¤ÇÑ Å©±âÀÇ ½½·ÔÀ» ÁغñÇ쵂 ¸¸¾à ¹öŶÀÌ °¡µæÂû Á¤µµ·Î µ¥ÀÌÅÍ°¡ µé¾î ¿Â´Ù¸é ½½·Ô Å©±â¸¦ ½ÇÇàÁß¿¡ ´Ã¸°´Ù. ÀÌ·¸°Ô ÇÏ¸é ´ëü ¹öŶÀ» ãÀ» ÇÊ¿äµµ ¾ø°í »èÁ¦ÇÏ´Â ¹æ¹ýµµ ¹ø°Å·ÓÁö ¾Ê´Ù.
½½·ÔÀº ½ÇÇàÁß¿¡ Å©±â¸¦ ´Ã¸± ¼ö ÀÖ¾î¾ß ÇϹǷΠµ¿Àû ¹è¿À̳ª ¿¬°á ¸®½ºÆ®·Î ÀÛ¼ºÇØ¾ß ÇÑ´Ù. µ¿Àû ¹è¿À» ¾´´Ù¸é Çؽà Å×À̺íÀº Æ÷ÀÎÅÍ ¹è¿ÀÌ µÉ °ÍÀÌ´Ù. ¿¬°á ¸®½ºÆ®¶ó¸é °¢ ¹öŶÀÌ ½½·Ô ¿¬°á ¸®½ºÆ®ÀÇ ÁøÀÔÁ¡ÀÎ head¸¦ ÀúÀåÇØ¾ß ÇÒ °ÍÀÌ´Ù. ¹öŶ ³»¿¡¼ÀÇ °Ë»öÀº ¼øÂ÷ °Ë»öÀ» »ç¿ëÇ쵂 ¸¸¾à µ¿Àû ½½·ÔÀÇ Å©±â°¡ ¹«Ã´ Ä¿Áú ¼ö ÀÖ´Ù¸é À̺Р°Ë»öÀ» ¾²´Â °ÍÀÌ ´õ À¯¸®ÇÒ °ÍÀÌ´Ù. À̶§´Â ¹°·Ð ¹è¿·Î¸¸ ÀÛ¼ºÇØ¾ß ÇÑ´Ù.
ÀÌ»óÀ¸·Î Çؽ̿¡ ´ëÇØ ¾Ë¾Æ ºÃ´Âµ¥ ÇؽÌÀº °Ë»ö ¹æ¹ýÀ̶ó±â º¸´Ù´Â ºü¸¥ °Ë»öÀ» À§ÇÑ ÀÚ·á °ü¸® ¾Ë°í¸®ÁòÀ̶ó°í ÇÒ ¼ö ÀÖ´Ù. ¿¹Á¦¿¡¼´Â Ãæµ¹ Çö»óÀ» ½±°Ô ¸ñ°ÝÇϱâ À§ÇØ Çؽà Å×ÀÌºíµµ ÀÛ°Ô ¸¸µé°í ½½·Ôµµ ÀÛ°Ô ¸¸µé¾ú´Âµ¥ ½ÇÁ¦ ÇÁ·ÎÁ§Æ®¿¡¼´Â Çؽà Å×À̺íÀ» °¡±ÞÀû Å©°Ô ¸¸µé¾î¾ß ÇÑ´Ù. Á¤¼ö¸¦ ÀúÀåÇÑ´Ù¸é ¹öŶÀÌ 10°³ÀÎ °æ¿ìº¸´Ù 100°³ÀÎ °æ¿ì Ãæµ¹ÀÌ ÈξÀ ´ú ÇÒ °ÍÀÌ°í 1000°³ÀÌ¸é ´õ ÁÁ´Ù. ¿©±â¿¡ ½½·Ôµµ ´Ù¼¸ °³ Á¤µµ ÁغñÇÏ¸é °ÅÀÇ Ãæµ¹ÀÌ ¾øÀ» °ÍÀÌ°í Ȥ½Ã¶óµµ Ãæµ¹ÀÌ ¹ß»ýÇÒ ¶§¸¦ ´ëºñÇؼ ÀçÇؽà ÇÔ¼ö¸¦ Çϳª Á¤µµ µÎ¸é µÈ´Ù.
ÇؽÌÀº Çؽà ÇÔ¼ö·ÎºÎÅÍ ¹öŶ À§Ä¡¸¦ ¹Ù·Î ãÀ» ¼ö ÀÖÀ¸¹Ç·Î °Ë»ö ¼Óµµ°¡ ´ë´ÜÈ÷ ºü¸¥ ¾Ë°í¸®ÁòÀÌÁö¸¸ ¹Ý¸é ¸Þ¸ð¸®´Â ±²ÀåÈ÷ ¸¹ÀÌ ¼Ò¸ðÇÑ´Ù. Å©±â¿Í ¼Óµµ°¡ Ç×»ó ¹Ýºñ·Ê¶ó´Â °ÍÀ» Àß ÀÔÁõÇÏ´Â ¾Ë°í¸®ÁòÀÌ´Ù. Á» ´õ »¡¶óÁö°í ½Í´Ù¸é ÃæºÐÇÑ ¸Þ¸ð¸®¸¦ ÁغñÇØ¾ß ÇÏ°í ¸Þ¸ð¸®°¡ ³Ë³ËÇÏÁö ¾ÊÀ¸¸é ÀæÀº Ãæµ¹·Î ÀÎÇØ ´À·ÁÁú ¼ö¹Û¿¡ ¾ø´Ù.