Robert  E.  Tarjan

 

ÄÄÇ»Å͸¦ ¸¸µç 15 ÀÎÀÇ °úÇÐÀÚ : Dennis Shasha. Cathy Lazere °øÀú, ¹Ú¿µ¼÷ ¿Å±è, ¼¼Á¾¿¬±¸¿ø, 1998 (¿ø¼­ : Out of Their Minds : 1995)

 

±×·¡ÇÁ°¡ Æò¸éÀ¸·Î ±×·ÁÁú ¼ö ÀÖÀ»±î?

±íÀÌ ¿ì¼± °Ë»öÀÇ Àû¿ë

ÇÕÁýÇÕ Ã£±â (union-find) ¿Í »ó°¢ (amortization)

³×Æ®¿öÅ© ÃÖ´ë À¯·®

°æÀï

¿µ¼ÓÀû ÀÚ·á ±¸Á¶

¿¬±¸ È°µ¿¿¡¼­ÀÇ ÆÐÅÏ

 

 

ÄÄÇ»ÅÍ °úÇÐ ºÐ¾ß¿¡¼­´Â ÈǸ¢ÇÑ ¾ÆÀ̵ð¾î°¡ ¼¼ °¡Áö Ư¡À» °¡Áø´Ù. ±×°ÍÀº ¿ì¼± ½ÇÁ¦·Î ÈçÈ÷ »ç¿ëµÈ´Ù´Â Á¡, ÀÏÂïºÎÅÍ ÀþÀº ÄÄÇ»ÅÍ °úÇÐÀڵ鿡°Ô °¡¸£Ä£´Ù´Â Á¡, ¸¶Áö¸·À¸·Î ¿¬±¸ÀÇ ±æÀ» Á¦½ÃÇÑ´Ù´Â Á¡ÀÌ´Ù. ÀÌ·¯ÇÑ ±âÁØ¿¡ ºñÃß¾î º¼ ¶§ ·Î¹öÆ® ¾Óµå·¹ ŸÀÜ (Robert Endre Tarjan) Àº ¼ö¸¹Àº ÁÁÀº ¾ÆÀ̵ð¾îµéÀ» ³»³õ¾Ò´Ù.

±×°¡ ½ºÅÄÆÛµå ´ëÇп¡¼­ Á¸ È©Å©·ÎÇÁÆ® (John Hopcroft) ¿Í ÇÔ²² ÇÑ ¹Ú»ç °úÁ¤ÀÇ ¿¬±¸´Â Æò¸é °Ë»ç (planarity testing) ¿Í ±× ¹ÛÀÇ ±×·¡ÇÁ ¾Ë°í¸®Áòµé¿¡ ´ëÇÑ °ÍÀ¸·Î¼­, º¸´Ù È¿À²ÀûÀΠĨ ·¹À̾ƿô¿¡¼­ º¸´Ù ³ªÀº µµÇü (map) ·¹À̾ƿô¿¡ À̸£±â±îÁö ´Ù¾çÇÑ ÀÀ¿ë ÇÁ·Î±×·¥À» ź»ý½ÃÄ×´Ù. ÀÌµé ¾Ë°í¸®ÁòÀº ¸ðµç ÇкλýµéÀÌ ¹è¿ì°Ô µÇ´Â '±íÀÌ ¿ì¼± °Ë»ö (depth-first search)' À̶ó´Â ÇÁ·Î±×·¡¹Ö ±â¼úÀÇ À§·ÂÀ» °­Á¶ÇÑ´Ù. ¶ÇÇÑ, ±íÀÌ ¿ì¼± °Ë»öÀº °ÔÀÓÀ̳ª ½ºÇÁ·¹µå ½ÃÆ®, ±×·¡ÇÈ ÇÁ·Î±×·¥ µîÀÇ ºÐ¾ß¿¡¼­µµ ÇÏ·ç¿¡ ¼ö½Ê¾ï Â÷·Ê¾¿ »ç¿ëµÇ°í ÀÖ´Ù. ÀÌÈÄ Å¸ÀÜÀÌ ´í ½½¸®ÅÍ (Dan Sleator), ¾Øµå·ù °ñµå¹ö±× (Andrew Goldberg) ¿Í ÇÔ²² ÁøÇàÇÏ¿´´ø È¿À²ÀûÀÎ ³×Æ®¿öÅ© È帧¿¡ ´ëÇÑ ¿¬±¸´Â ¼³°èÀÚµéÀÌ ¿¬¾ÈÀÇ ¼®À¯¿¡¼­ ÀüÈ­ ÅëÈ­¿¡ À̸£±â±îÁö ¸ðµç °ÍÀÇ È帧À» °³¼±Çϱâ À§Çؼ­´Â ³×Æ®¿öÅ©¿¡¼­ °¢°¢ÀÇ ¿¬°á¿¡ ¾ó¸¶³ª ¸¹Àº ¿ë·®À» ºÎ¿©ÇØ¾ß ÇÏ´ÂÁö¸¦ ¾Ë¾Æ³»´Â µ¥ µµ¿òÀ» ÁÖ¾ú´Ù. »Ó¸¸ ¾Æ´Ï¶ó, »óÇâ Æ®¸® (up-tree) ¿Í »ç¼± Æ®¸® (splay-tree) ¶ó°í ¾Ë·ÁÁ® ÀÖ´Â ÇÑ ½ÖÀÇ ´Ü¼øÇÑ ÀÚ·á ±¸Á¶¿¡ ´ëÇÑ ±×ÀÇ ¿¬±¸´Â ¾Ë°í¸®ÁòÀÇ È¿À²¼ºÀ» ÃøÁ¤ÇÏ´Â »õ·Î¿î ±â¹ýÀ» µµÀÔ½ÃÄ×´Ù.

´Ò »ç³ªÅ© (Neil Sarnak), ½½¸®ÅÍ, Á¦ÀÓ½º µå¸®½ºÄÝ (James Driscoll) µî°ú ÇÔ²² ÇÑ ¶Ç ´Ù¸¥ ¿¬±¸´Â ÇöÀç »Ó¸¸ ¾Æ´Ï¶ó °ú°Å¿¡ ´ëÇÑ Á¤º¸±îÁö º¸À¯ÇÒ ¼ö ÀÖ´Â ÀÚ·á ±¸Á¶¸¦ ¾ÆÁÖ È¿À²ÀûÀÎ ÇüÅ·ΠÁ¦½ÃÇÏ¿´´Ù. ±×ó·³ '¿µ¼ÓÀûÀÎ' ÀÚ·á ±¸Á¶´Â ¿À´Ã³¯ ·Îº¿ °øÇаú µ¥ÀÌÅÍ º£À̽º ½Ã½ºÅÛ ºÐ¾ß¿¡¼­ Á¡Á¡ ´õ »ç¿ëÀÌ ´Ã°í ÀÖ´Ù.

ŸÀÜÀº ¶ÇÇÑ ÄÄÇ»ÅÍ °úÇÐÀÇ ¿¬±¸¿¡ ¹®È­Àû º¯È­¸¦ °¡Á®¿Ô´Ù. ±×°ÍÀº ÀûÀýÇÑ 'Å« ¾ÆÀ̵ð¾î (big idea)' ¸¦ ¾òÀº ´ÙÀ½, ±×°ÍÀ» °¡Àå È¿À²ÀûÀ¸·Î Áö¿øÇÒ ÀÚ·á ±¸Á¶¸¦ ¸¸µé¾î ³»´Â ¹æ½ÄÀÌ´Ù. ±×¸¦ ºñ·ÔÇØ ¿©·¯ »ç¶÷ÀÌ ±×·¯ÇÑ Àü·«À¸·Î ´ÙÀÌÅ©½ºÆ®¶óÀÇ ÃÖ´Ü °æ·Î ¾Ë°í¸®Áò°ú ¶Ç ´Ù¸¥ ±âº» ¾Ë°í¸®Áòµé¿¡¼­ Áß´ëÇÑ °³¼±À» ¹Ð¾îºÙ¿´´Ù.

±×ÀÇ ¿¬±¸´Â ¹Ì´Ï¸Ö¸®Áò (minimalism), ¼¼·ÃµÊ, ±×¸®°í º¸Æí¼ºÀ» ÇâÇÑ ¹«¾ðÀÇ Ãß±¸ µîÀ¸·Î Ư¡ÁöÀ» ¼ö ÀÖ´Ù.

ÁÁÀº ¾ÆÀ̵ð¾î´Â º¸´Ù ´Ü¼øÇØÁ® ¿ø·¡ ¸ñÇ¥Çß´ø °Í ÀÌ¿ÜÀÇ ¹®Á¦µé±îÁö ÇØ°áÇÒ ¼ö ÀÖ´Â ¹æ¹ýÀ» °¡Áö°í ÀÖ½À´Ï´Ù.

·Î¹öÆ® ¾Óµå·¹ ŸÀÜÀº 1948 ³â Ķ¸®Æ÷´Ï¾Æ ÁÖ Æ÷¸ð³ª¿¡¼­ ž´Ù. ¾î¸° ³ªÀ̺ÎÅÍ ±×´Â °úÇп¡ Èï¹Ì¸¦ ´À²¼´Ù.

¾Æ¸¶ 7 ÇгâÂë µÇ¾úÀ» ¶§ÀÏ °Ì´Ï´Ù. ³­ ¡º»çÀ̾ðƼÇÈ ¾Æ¸Þ¸®Ä­ Scientific American¡»Áö¿¡ ½Ç¸° ¸¶Æ¾ °¡µå³Ê (Martin Gardner) ÀÇ Ä®·³À» ÀÐÀ¸¸é¼­ ¼öÇп¡ Èï¹Ì¸¦ ´À³¢°Ô µÇ¾ú½À´Ï´Ù. ±× ÀÌÀü¿¡´Â õ¹®Çп¡ °ü½ÉÀÌ ÀÖ¾úÁö¿ä. ³­ È­¼º¿¡ ¹ßÀ» ³»µó´Â ÃÖÃÊÀÇ »ç¶÷ÀÌ µÇ°í ½Í¾ú½À´Ï´Ù.

¼Ò¾ÆÁ¤½Å°ú¿¡¼­ Á¤½Å Áöü ºÐ¾ß Àü¹®ÀÇ¿´´ø ŸÀÜÀÇ ¾Æ¹öÁö´Â ÁÖ¸³ º´¿øÀ» ¿î¿µÇÏ°í ÀÖ¾ú´Ù. ŸÀÜÀº ÁßÇб³ ½ÃÀý ±× °÷¿¡¼­ ÀÏÀÚ¸®¸¦ ¾ò¾î ±×°¡ '¿¹ºñ ÄÄÇ»ÅÍ (precomputer)' ¶ó ºÒ·¶´ø IBM õ°ø Ä«µå Á¶ÇÕ±âµé¿¡ ´ëÇÑ ÀÛ¾÷À» ÇÏ¿´´Ù. 1964 ³â ÁßÇÐ °úÁ¤¿¡ À̾îÁø ÇÏ°è°úÇÐ ÇÁ·Î±×·¥¿¡¼­ ŸÀÜÀº óÀ½À¸·Î ½ÇÁ¦ ÄÄÇ»Å͵éÀ» °¡Áö°í ÀÛ¾÷À» ÇÏ°Ô µÇ¾ú´Ù.

´ç½ÃÀÇ ¹ß»óÀº ÇϳªÀÇ ¼ÒÇ༺À» °üÂûÇÏ°í ±×°ÍÀÇ ±Ëµµ¸¦ °è»êÇÏ´Â °ÍÀ̾ú½À´Ï´Ù. ¿ì¸®´Â UCLA ¿¡¼­ ÄÄÇ»Å͸¦ Á÷Á¢ »ç¿ëÇØ º¼ ±âȸ¸¦ °¡Á³°í ±×·¸°Ô Çؼ­ ³­ Æ÷Æ®¶õÀ» ¹è¿ì°Ô µÇ¾úÁö¿ä.

±× ¹«·Æ ÁÖ¸³ º´¿ø¿¡¼­µµ ¾ÆÁÖ ÀÛÀº ÄÄÇ»Å͸¦ ÇÑ ´ë °®°Ô µÇ¾ú½À´Ï´Ù. ±×·¡¼­ ³­ ¿©¸§À̸é ĶÅ×Å©¸¦ ¶°³ª ±× ÄÄÇ»Å͸¦ °¡Áö°í ȯÀÚµéÀ» ¸ðÁý´ÜÀ¸·Î ÇÑ Åë°èÀû ¿¬±¸ÀÇ ÇÁ·Î±×·¡¹ÖÀ» ½ÇÇàÇÏ¿´½À´Ï´Ù.

ĶÅ×Å©¿¡¼­ ŸÀÜÀº ¼öÇÐÀ» Àü°øÇÏ¿´Áö¸¸, ÄÄÇ»ÅÍ °úÇÐÂÊ¿¡¼­µµ ´ëÇпø»ýµé¿¡°Ô °³¼³µÈ °úÁ¤Àº ºüÁü¾øÀÌ ¼ö°­ÇÏ¿´´Ù.

³­ º¸´Ù ÀÀ¿ë·Â ÀÖ´Â À¯ÇüÀÇ ¼öÇÐÀ̶ó´Â ÀÌÀ¯ ¶§¹®¿¡ ÄÄÇ»ÅÍ °úÇÐÀ» ÇÏ°í ½Í¾ú½À´Ï´Ù. ´ëü·Î ³í¸®¿Í Á¤¸® Áõ¸íÀÇ Ãø¸é¿¡¼­ ÀΰøÁö´É¿¡ Èï¹Ì¸¦ ´À²¼Áö¿ä. ÇÏÁö¸¸ Á¤ÀÛ ½ºÅÄÆ۵忡 µé¾î°¡ AI °úÁ¤À» ½ÃÀÛÇÏ°Ô µÇ¾úÀ» ¶§¿¡´Â ±×°ÍÀÌ ¾ÆÁÖ ¸ðÈ£ÇÑ °ÍÀ̶ó´Â °á·ÐÀ» ³»·È½À´Ï´Ù.

½ºÅÄÆÛµå´Â µµ³Îµå Å©´©½º¿Í Á¸ ¸ÅÄ¿½Ã¸¦ Æ÷ÇÔÇØ ÄÄÇ»ÅÍ °úÇÐÀÇ ¼±±¸Àû Àι°µéÀ» ¹èÃâÇß´Ù´Â °ÍÀ» ÀÚ¶û½º·´°Ô ¿©±â°í ÀÖ¾ú´Ù.

Å©´©½º´Â ¿ì¼± °í¹«ÀûÀ̾ú½À´Ï´Ù. ±×°¡ ¾ÆÁÖ ±¸Ã¼ÀûÀÎ ºÐ¼®¿¡ °ü½ÉÀÇ ÃÊÁ¡À» µÎ¾ú´Ù´Â Á¡¿¡¼­ °í¹«ÀûÀ̾úÁö¿ä. ±×´Â Ç×»ó Á¤È®ÇÑ °á°ú¸¦ ¾ò¾î³»´Â ¼öÇÐÀÇ ¾ö¹Ð¼º¿¡ Èï¹Ì¸¦ º¸ÀÌ°í ÀÖ¾ú½À´Ï´Ù.

¶Ç ÇѸíÀÇ °í¹«ÀûÀÎ Àι°Àº ÄÚ³Ú¿¡¼­ ¾È½Ä³âÀ» ¸Â¾Æ ½ºÅÄÆ۵忡 ¿Í ÀÖ¾ú´ø Á¸ È©Å©·ÎÇÁÆ®¿´´Ù. ±×´Â ŸÀÜÀÌ ´ëÇпø 2 Çг⠰úÁ¤À» ½ÃÀÛÇϱâ ÀüÀ̾ú´ø ¿©¸§¿¡ ±× °÷¿¡ µµÂøÇÏ¿© ±×ÀÇ ¿·¹æ¿¡ µé¾î¿Ô´Ù. ±× µÎ »ç¶÷Àº °ð °øµ¿ ¿¬±¸¸¦ ½ÃÀÛÇÏ¿© ¸¶Ä§³» 1986 ¿¡´Â Æ©¸µ»óÀ» ¼ö»óÇϱ⿡ À̸¥´Ù.

³­ ¸ÅÄ¿½ÃÀÇ ±âÈ£ ó¸® °úÁ¤À» ÅÃÇß½À´Ï´Ù. ±× °­ÀÇ´Â ´ëºÎºÐ ¸®½ºÇÁ¿¡ ´ëÇÑ ³»¿ëÀ̾úÁö¿ä. ±×´Â Çлýµé¿¡°Ô ±×·¡ÇÁ°¡ Æò¸éÀÎÁö ¾Æ´ÑÁö¸¦ ½Äº°ÇÏ´Â ÇÁ·Î±×·¥À» ¾²µµ·Ï Á¦¾ÈÇÏ¿´½À´Ï´Ù.

³­ ¾Æ¹«·± ±â´ëµµ °®°í ÀÖÁö ¾Ê¾Ò½À´Ï´Ù. ´ÜÁö Èï¹Ì·Î¿î ¹®Á¦µéÀ» Ç®·Á°í ¾Ö¾²´Â ÇÑ ¸íÀÇ ´ëÇпø»ýÀÏ »ÓÀ̾úÁö¿ä.

±×·¡ÇÁ°¡ Æò¸éÀ¸·Î ±×·ÁÁú ¼ö ÀÖÀ»±î?

±×·¡ÇÁ´Â ³ëµå (node) µé°ú ³ëµå »çÀ̸¦ ¿¬°áÇÏ´Â °£¼± (edge) µéÀÇ ÁýÇÕÀÌ´Ù. (±×¸² 1 ÀÇ ±×·¡ÇÁ¿¡¼­ ³ëµå´Â ÀÛÀº ¿øÀ» °¡¸®Å°¸ç °£¼±Àº ±×°ÍÀ» ¿¬°áÇÏ´Â Á÷¼±µéÀÌ´Ù.) ±×·¡ÇÁ´Â °¢±â ´Ù¸¥ ½ÇÁ¦ ¼¼°èÀÇ ¸¹Àº Çö»óµéÀ» Ç¥ÇöÇÏ´Â µ¥ »ç¿ëµÈ´Ù. ¿¹¸¦ µé¾î, ³ëµå°¡ ºÐÀÚ¸¦ ³ªÅ¸³»°í °£¼±ÀÌ ºÐÀÚ °áÇÕÀ» ³ªÅ¸³»´Â °æ¿ìµµ »ý°¢ÇØ º¼ ¼ö ÀÖ°í, ³ëµå°¡ ÀÖÀ¸¸ç, ³ëµå°¡ ±³Â÷·Î¸¦ ³ªÅ¸³»°í °£¼±Àº µµ·ÎµéÀ» ³ªÅ¸³¾ ¼öµµ ÀÖ´Â °ÍÀÌ´Ù.

±×¸² 1  Æò¸é ±×·¡ÇÁ

    ±×·¡ÇÁ´Â A ´Â ±×·¡ÇÁ B ¿¡¼­ º¸ÀÌ´Â °Íó·³ °£¼±µéÀÌ °ãÄ¡Áö ¾ÊÀ¸¸é¼­ ±× ¿¬°á °ü°è´Â ±×´ë·Î À¯ÁöµÇµµ·Ï ´Ù½Ã ±×·ÁÁú ¼ö ÀÖ´Ù.

ƯÁ¤ÇÑ ÀÀ¿ë »ç·Ê¿¡¼­´Â °£¼±ÀÌ °ãÄ¡Áö ¾Êµµ·Ï ÇÏ´Â °ÍÀÌ Áß¿äÇÏ´Ù. ¿¹¸¦ µé¾î, ¹è¼±µµÀÇ ·¹À̾ƿôÀÎ °æ¿ì °£¼± (¹è¼±) ÀÇ Áߺ¹Àº ´©ÀüÀ» ÃÊ·¡ÇÒ ¼ö ÀÖ´Ù. µû¶ó¼­, ¾î¶² ±×·¡ÇÁ¸¦ ÀÛ¼ºÇÒ ¶§ °ú¿¬ ±× ¿¬°á »óÅ´ ±×´ë·Î À¯ÁöÇϸ鼭 °£¼±µéÀÌ °ãÄ¡Áö ¾Êµµ·Ï ±×¸± ¼ö Àִ°¡ ÇÏ´Â Áú¹®ÀÌ ÀÚ¿¬½º·´°Ô Á¦±âµÉ °ÍÀÌ´Ù. ±×¿Í °°Àº ±×·¡ÇÁ¸¦ 'Æò¸é (planar)' ±×·¡ÇÁ¶ó°í ºÎ¸¥´Ù. ±×¸² 1 ÀÇ ±×·¡ÇÁ A ¿¡¼­´Â °£¼±µéÀÌ °ãÃÄÀÖÁö¸¸, ±× ±×·¡ÇÁ¸¦ ÆîÃļ­ ±×·¡ÇÁ B ¿Í °°ÀÌ °£¼±µéÀÌ Áߺ¹µÇÁö ¾Ê°Ô ¸¸µé ¼ö ÀÖ´Ù.

±×·¡ÇÁ°¡ Æò¸éÀÎÁö ¾Æ´ÑÁö¸¦ °¡¸®´Â °Ë»çÀÇ ±â¿øÀº 18 ¼¼±âÀÇ ¿ÀÀÏ·¯ (Euler) ±îÁö °Å½½·¯ ¿Ã¶ó°£´Ù. ±× ½ºÀ§½º ¼öÇÐÀÚ´Â ³ëµåÀÇ ¼ö°¡ N ÀÏ ¶§ N ÀÌ ÃÖ¼ÒÇÑ 3 ÀÌ»óÀ̶ó¸é °£¼±ÀÇ ¼ö°¡ 3N - 6 ÀÌ»óÀÌ µÇ´Â ±×·¡ÇÁ´Â ÀÖÀ» ¼ö ¾øÀ½À» º¸¿© ÁÖ¾ú´Ù.

1930 ³â Æú¶õµåÀÇ ¼öÇÐÀÚ Äí¶óÅäÇÁ½ºÅ° (Kuratowski) ´Â ¸ðµç ºñÆò¸é ±×·¡ÇÁ´Â ±×¸² 2 ¿¡ Á¦½ÃµÈ ±×·¡ÇÁ °¡¿îµ¥ ÇϳªÀÇ ¿¬°á °ü°è¸¦ °¡Áø ±×·¡ÇÁ¸¦ Æ÷ÇÔ 'Çؾ߸¸' ÇÑ´Ù´Â »ç½ÇÀ» º¸¿© ÁÖ¾ú´Ù. ¸ÅÄ¿½Ã´Â Çлýµé¿¡°Ô Äí¶óÅäÇÁ½ºÅ°ÀÇ Á¶°ÇÀ» ÇÁ·Î±×·¥¿¡ »ç¿ëÇϵµ·Ï Á¦¾ÈÇÏ¿´´Ù. ŸÀÜÀº °ð ±×·¸°Ô ¸¸µé¾îÁö´Â ¾Ë°í¸®ÁòÀº ³Ê¹«µµ ºñÈ¿À²ÀûÀÏ °ÍÀ̶ó´Â °á·ÐÀ» ³»·È´Ù. Äí¶óÅäÇÁ½ºÅ°ÀÇ °Ë»ç°¡ ¾Ë°í¸®ÁòÀ¸·Î º¯È¯µÉ ¼ö´Â ÀÖÁö¸¸, °Å±â¿¡ ¿ä±¸µÇ´Â ½Ã°£Àº ²ÀÁöÁ¡ ¼öÀÇ 6 Á¦°ö¿¡ ºñ·ÊÇÑ´Ù´Â ÀÌÀ¯ ¶§¹®À̾ú´Ù. ±×°ÍÀº ¸¸ÀÏ ²ÀÁöÁ¡ÀÇ ¼ö°¡ 100 °³ °¡·®ÀÎ ±×·¡ÇÁÀÇ °æ¿ì 1012 ¸¸Å­ÀÇ ´Ü°è°¡ ÇÊ¿äÇÏ°Ô µÈ´Ù´Â °ÍÀ» ¾Ï½ÃÇÑ´Ù.

±×¸² 2  ¸ðµç ºñÆò¸é ±×·¡ÇÁ´Â ¿©±â¼­ º¸¿© ÁÖ´Â °Í °¡¿îµ¥ Çϳª¿Í °°Àº ±¸Á¶ (ºÎºÐ ±×·¡ÇÁ) ¸¦ °¡Á®¾ß¸¸ ÇÑ´Ù.

 

±×·¡¼­ ³ª´Â ÀÌ¹Ì Æò¸é °Ë»ç¿¡ °üÇØ »ý°¢ÇÏ°í ÀÖ¾ú½À´Ï´Ù È©Å©·ÎÇÁÆ®°¡ µµÂøÇÏ¿´À» ¶§ ¿ì¸®´Â ¾Ë°í¸®Áò°ú È¿À²¼º¿¡ °üÇØ ³íÀÇÇϱ⠽ÃÀÛÇÏ¿´Áö¿ä.

È©Å©·ÎÇÁÆ®´Â ÀÌÁß °áÇÕ ¿ä¼ÒµéÀ» ã±â À§ÇÑ ¾Ë°í¸®ÁòÀ» Á¦½ÃÇÏ¿´´Âµ¥, ±×°Í¸¸À¸·Î ½ÃÀÛÀ» Çϱ⿡´Â ´Ù¼Ò ¾û¼ºÇÑ ½ºÄÉÄ¡¿´½À´Ï´Ù. ÇÏÁö¸¸ ½ÇÁ¦·Î ±× ¾Ë°í¸®ÁòÀÇ ¼º°ÝÀº ±íÀÌ ¿ì¼± °Ë»öÀ̾úÁö¿ä. ³­ ±×°Í¿¡ ´ëÇØ »ý°¢ÇØ º» µÚ ±×ÀÇ ¾Ë°í¸®Áò¿¡¼­ ÁøÇàµÇ´Â »çÇ×ÀÇ ¿øÄ¢À» º¸´Ù ¾ö¹ÐÇÏ°Ô ¸¸µé±â À§ÇÑ ½Ãµµ¸¦ ÇÏ¿´½À´Ï´Ù.

±íÀÌ ¿ì¼± °Ë»öÀÇ Àû¿ë

±íÀÌ ¿ì¼± °Ë»öÀº Àΰø Áö´ÉÀÇ ¹®Á¦µé¿¡ ´ëÇÑ ÇعýÀ» ã´Â µ¥ ³Î¸® »ç¿ëµÇ°í ÀÖ¾ú´Ù. ±× ºÐ¾ß¿¡¼­´Â À̸¦ '¿ªÇà (backtracking)' À̶ó ºÒ·¶´Ù. ¿ªÇàÀº ¹®Á¦¸¦ ÇØ°áÇÏ´Â µ¥ ÀÖ¾î ¾î¶² ÇÑ °¡Áö Á¢±Ù ¹æ½ÄÀ» ¹Ýº¹ÇÏÁö ¾ÊÀ¸¸é¼­ »óÀÌÇÑ Á¢±Ù ¹æ½ÄµéÀ» °ËÅäÇÑ´Ù. AI ºÐ¾ß¿¡¼­´Â ÀÌ°ÍÀÌ °ÔÀÓ¿¡¼­ ÀÏ·ÃÀÇ ¿îµ¿°ú ¹Ý´ë ¿îµ¿µé »çÀÌ¿¡ ü°èÀûÀÎ °Ë»öÀ» ½ÇÇàÇÏ´Â µ¥ »ç¿ëµÇ¾ú´Ù. ŸÀÜ°ú È©Å©·ÎÇÁÆ®´Â ±íÀÌ ¿ì¼± °Ë»öÀ» ±×·¡ÇÁ ¿¬±¸ÀÇ ¹æ¹ýÀ¸·Î »ç¿ëÇÏ¿´´Ù. [±íÀÌ ¿ì¼± °Ë»ö¿¡¼­ ´ÜÀÏÀÇ Á¢±Ù ¹æ½ÄÀº ´Ù¸¥ Á¢±Ù ¹æ½ÄÀÌ ½ÃµµµÇ±â Àü¿¡ ±× °á·ÐÀÌ µû¶ó ³ª¿Â´Ù. '³Êºñ ¿ì¼± (breadth-first)' À̶ó°í ÇÏ´Â ¶Ç ÇϳªÀÇ Àü·«¿¡¼­´Â ¾î¶² ¹®Á¦¸¦ ÇØ°áÇÏ´Â µ¥ ´ëÇÑ ¼ö¸¹Àº Á¢±Ù ¹æ½ÄµéÀÌ µ¿½Ã¿¡ ÀÛ¿ëÇÑ´Ù. ¾î¶² Á¢±Ù ¹æ½ÄÀÌ »ç¿ëµÇ´Â°¡´Â ¹®Á¦¿¡ µû¶ó ´Þ¶óÁø´Ù.]

±íÀÌ ¿ì¼± °Ë»öÀº ±×·¡ÇÁÀÇ ³ëµå n ¿¡¼­ ½ÃÀÛÇÏ¿©, n À» ±âÁ¡À¸·Î ±×¾îÁø °£¼±À» ¼±ÅÃÇÑ´Ù. °£¼± ¿îÇà (traverse) Àº »õ·Î¿î ³ëµå¿¡ À̸£°Ô ÇÑ´Ù. ÀϹÝÀûÀ¸·Î ÇÁ·Î±×·¥Àº °¡Àå ÃÖ±Ù¿¡ ¹æ¹®ÇÑ ³ëµå¿¡¼­ Ãâ¹ßÇÏ´Â ¾ÆÁ÷ °Ë»çµÇÁö ¾ÊÀº °£¼±À» ¼±ÅÃÇÏ¿© ¿îÇàÇÑ´Ù. ±íÀÌ ¿ì¼± °Ë»öÀº ¾î¶°ÇÑ °£¼±µµ ÇÑ ¹ø ÀÌ»ó ¿îÇàµÇÁö ¾Êµµ·Ï º¸ÀåÇÑ´Ù.

È©Å©·ÎÇÁÆ®¿Í ŸÀÜÀº ±íÀÌ ¿ì¼± °Ë»öÀ» »ç¿ëÇÏ¿©, 1961 ³â ¿À½½·£´õ (L. Auslander) ¿Í ÆÄÅÍ (S. V. Parter) °¡ °³Ã´ÇØ 1963 ³â °ñµå½ºÅ¸ÀÎ (A. J. Goldstein) ÀÌ ¼öÁ¤ÇÑ Àü·«À» ½ÇÇàÇÏ¿´´Ù. ¿À½½·£´õ, ÆÄÅÍ, °ñµå½ºÅ¸ÀÎ ¼¼ »ç¶÷ÀÌ Á¦¾ÈÇÑ ¾Ë°í¸®ÁòÀº Äí¶óÅäÇÁ½ºÅ°ÀÇ ºñÆò¸é °Ë»ç¿Í´Â Á÷Á¢ÀûÀÎ Åä´ë·Î »ï°í ÀÖ´Ù. ±× ±âº» ´Ü°èµéÀº ´ÙÀ½°ú °°´Ù.

ƯÁ¤ÇÑ ´Ù¸®ÀÇ ½ÖµéÀº ¼­·Î Ãæµ¹Çϱ⠶§¹®¿¡ °¢°¢ ¿øÀÇ ¹Ý´ëÆí¿¡ ÁöÁ¤µÇ¾î¾ß ÇÑ´Ù.

ÀÌ ¾Ë°í¸®ÁòÀ» È¿À²ÀûÀÎ °ÍÀ¸·Î ¸¸µå´Â ¿­¼è´Â Æ÷ÇÔµÈ ±×·¡ÇÁµé (Á¤½Ä ¿ë¾î´Â ºÎºÐ ±×·¡ÇÁ) ÀÇ Æò¸é °Ë»ç¸¦ ºñ·ÔÇØ Àüü °è»êÀ» ´ÜÀÏÇÑ ±íÀÌ ¿ì¼± °Ë»ö¸¸À¸·Î ¼öÇàÇÏ´Â °ÍÀÌ´Ù. ±¸Ã¼ÀûÀÎ »çÇ×µéÀº ±â¼úÀûÀÎ ¹®Á¦À̸ç, ±×µéÀÇ ³í¹® 'È¿À²ÀûÀÎ Æò¸é °Ë»ç (Efficient Planarity Testing)' ´Â ¾ÆÁÖ ¹Ðµµ ÀÖ´Â ¡º°è»ê ±â°è Çùȸ Àú³Î Journal of the Association for Computing Machinery¡»¿¡¼­µµ 20 ÆäÀÌÁö¿¡ ´ÞÇÏ´Â ºÐ·®À¸·Î ´Ù·ç¾îÁ³´Ù. ÇÏÁö¸¸ ±× ±âº» ±¸Á¶´Â ±×¸² 3 ¿¡¼­ º¼ ¼ö ÀÖ´Ù. °Å±â¿¡¼­´Â ±×¸² 1 ÀÇ ±×·¡ÇÁ A ¸¦ ¾à°£ ´Ü¼øÇÏ°Ô º¯Çü½ÃŲ ÇÑ Æò¸é ±×·¡ÇÁÀÇ ±íÀÌ ¿ì¼± °Ë»öÀ» º¸¿© ÁØ´Ù. ½Ç¼± È­»ìÇ¥´Â ±×·¡ÇÁÀÇ ³ëµåµéÀ» °Ë»çÇÏ´Â ÇÑ °¡Áö °¡´ÉÇÑ Á¢±Ù ¹æ¹ýÀ» ³ªÅ¸³»¸ç, Á¡¼± È­»ìÇ¥µéÀº ½Ç¼± È­»ìÇ¥·Î ¼³¸íµÇÁö ¾ÊÀº ±×·¡ÇÁÀÇ °£¼±µéÀ» ³ªÅ¸³½´Ù. ¿¹¸¦ µé¾î, 4 ¿¡¼­ 1 ·Î ÇâÇÏ´Â °£¼±À̳ª 5 ¿¡¼­ 6 À¸·Î ÇâÇÏ´Â °£¼±Àº ±×·¡ÇÁ»ó¿¡´Â ³ªÅ¸³ªÁö¸¸ Æ®¸®¿¡¼­´Â Á÷Á¢ Ç¥ÇöµÇÁö ¾Ê´Â´Ù. ±×·¡¼­ Á¡¼±À¸·Î Ç¥½ÃµÈ °ÍÀÌ´Ù. '¿ª °£¼± (back edge)' À̶ó ºÎ¸£´Â ÀÌ Ãß°¡ÀÇ °£¼±µéÀÌ Æ®¸®¿¡¼­ Á¶»óÀ» °¡¸®Å²´Ù´Â »ç½ÇÀº ŸÀÜ°ú È©Å©·ÎÇÁÆ®°¡ ±íÀÌ ¿ì¼± °Ë»ö¿¡ ´ëÇØ ¹ß°ßÇÑ ¸¹Àº ÈǸ¢ÇÑ Æ¯¼ºµé °¡¿îµ¥ ÇϳªÀÌ´Ù.

±×¸² 3  ±íÀÌ ¿ì¼± °Ë»ö Æò¸é °Ë»ç

    ¿ÞÂÊ ±×·¡ÇÁÀÇ ±íÀÌ ¿ì¼± °Ë»öÀº ¸¹Àº »óÀÌÇÑ Æ®¸®µéÀ» ¸¸µé¾î ³¾ ¼ö ÀÖ´Ù. ¿À¸¥ÂÊÀÇ ´ÙÀ̾î±×·¥¿¡¼­ ½Ç¼± °£¼±À¸·Î Ç¥½ÃµÈ Æ®¸®´Â ±× Áß ÇÑ °¡Áö °¡´É¼ºÀÌ´Ù. Á¡¼±À¸·Î ±×·ÁÁø ¿ÞÂÊ ±×·¡ÇÁ»ó¿¡´Â ³ªÅ¸³ª ÀÖÁö¸¸, ÀÌ Æ¯Á¤ÇÑ Æ®¸® Ç¥Çö¿¡´Â Æ÷ÇÔµÇÁö ¾Ê´Â °£¼±µé¿¡ ÇØ´çµÈ´Ù.

±×¸² 3 ¿¡ Á¦½ÃµÈ ±×·¡ÇÁÀÇ °æ¿ì ¾Ë°í¸®ÁòÀÇ µÎ ¹ø° ´Ü°è¿¡¼­ ¹ß°ßµÇ´Â ¼øȯÀº 1 ¡æ 6 ¡æ 3 ¡æ 2 ¡æ 5 ¡æ 4 ¡æ 1 ÀÌ µÉ °ÍÀÌ´Ù. À§¿¡¼­ ¾ð±ÞÇÑ ´Ù¼¸ ¹ø° (°Ë»ç) ´Ü°è´Â ³ª¸ÓÁö µÎ °³ÀÇ Á¡¼± °£¼±, Áï 4 ¢¡ 3 °ú 5 ¢¡ 6 ÀÌ Æò¸é»ó¿¡¼­ Çϳª´Â ¿øÀÇ ³»ºÎ¿¡, Çϳª´Â ¿øÀÇ ¿ÜºÎ¿¡ ÀÓº£µù (embedding) µÉ ¼ö ÀÖ´Ù´Â °ÍÀ» °üÂûÇÏ´Â µ¥ ÀÖ´Ù. ÀÌ°ÍÀº ±× ±×·¡ÇÁ°¡ Æò¸éÀÓÀ» ÀǹÌÇÑ´Ù.

ŸÀÜ°ú È©Å©·ÎÇÁÆ®ÀÇ Àü·«Àº ±íÀÌ ¿ì¼± °Ë»ö Æ®¸®¿¡ ¿ª °£¼±µéÀ» ´õÇÑ °ÍÀÌ Æò¸éÀÎÁö ¿©ºÎ¸¦ ÆǺ°ÇÏ´Â °ÍÀ¸·Î, Æò¸é ¹®Á¦ÀÇ ¹üÀ§¸¦ Á¼Çô ÁØ´Ù. ÀÌ°ÍÀº ¾ÆÁÖ È¿À²ÀûÀ¸·Î ¼öÇàµÉ ¼ö ÀÖ´Ù.

ÀÌ ¹®Á¦¿¡ ´ëÇÑ ÀÌÀüÀÇ ¸ðµç Á¢±Ù ¹æ½Äµé°ú ´Þ¸®, È©Å©·ÎÇÁÆ®-ŸÀÜ ¾Ë°í¸®ÁòÀº ¼±Çü ½Ã°£ (Áï, ±×·¡ÇÁÀÇ Å©±â¿¡ ºñ·ÊÇÏ´Â ½Ã°£) ³»¿¡ ½ÇÇàµÈ´Ù. ÀÌ´Â ¹®Á¦ÀÇ Å©±â¸¦ µÎ ¹è·Î ´ÃÀÏ ¶§ ±×°ÍÀ» ÇØ°áÇÏ´Â µ¥ µå´Â ½Ã°£µµ ´ÜÁö µÎ ¹è·Î¸¸ ´Ã¾î³­´Ù´Â °ÍÀ» ÀǹÌÇÑ´Ù. ¹Ý¸é¿¡, Äí¶óÅäÇÁ½ºÅ°ÀÇ ±âÁØÀ» »ç¿ëÇÒ ¶§ ¹®Á¦ÀÇ Å©±â¸¦ µÎ ¹è·Î È®´ëÇÏ¸é ½Ã°£Àº 60 º¸´Ù Å« ºñÀ²·Î ´Ã¾î³¯ ¼ö ÀÖ´Ù.

Æò¸é ¹®Á¦¿¡ ´ëÇؼ­´Â ¸ðµç »ç¶÷ÀÌ Á¤¸» ¾î·Á¿î ¹®Á¦À̹ǷΠ½Ã°£À» ¸¹ÀÌ Àâ¾Æ¸ÔÀ» °ÍÀ̶ó »ý°¢Ç߱⠶§¹®¿¡ Å« ³í¶õÀ» ºÒ·¯ ÀÏÀ¸Ä×½À´Ï´Ù. ÇÏÁö¸¸ ³»°¡ ¿ì¸®ÀÇ Æò¸é °Ë»ç ¾Ë°í¸®ÁòÀ» ½ÇÇà½ÃÄ×À» ¶§ ±×°ÍÀº ¾ÆÁÖ ¹Ù¸£°Ô ÁøÇàµÇ¾ú½À´Ï´Ù. º¹ÀâÇÑ ¾Ë°í¸®ÁòÀ» »ç¿ëÇؼ­ ƯÁ¤ÇÑ ¹®Á¦µéÀ» ÈξÀ ´õ »¡¸® ÇØ°áÇÒ ¼ö ÀÖ´Ù´Â »ç½ÇÀÌ ¸í¹éÇØÁø °ÍÀÌÁö¿ä.

1970 ³â´ë ÃÊ¿¡´Â ÀÌ°ÍÀÌ ¼Ò¼öÆÄÀÇ °ßÇØ¿¡ ºÒ°úÇß´Ù. °è»êÀ» ¼öÇàÇÏ´Â µ¥ µå´Â ½Ã°£ÀÇ ¼öÇÐÀû ¿¬±¸¸¦ ½ÃÀÛÇÑ Áö ºÒ°ú 10 ¿©³â¹Û¿¡ µÇÁö ¾ÊÀº ½ÃÁ¡À̾ú´ø °ÍÀÌ´Ù. ±×¿Í °°Àº ¿¬±¸´Â 1959 ³â ¸¶ÀÌŬ ¶óºóÀ¸·ÎºÎÅÍ ½ÃÀÛµÇ¾î µµ³Îµå Äí´©½º, Á긮½º ÇÏÆ®¸¶´Ï½º (Juris Hartmanis), ½ºÆ¼ºê Äî, ·¹¿À´Ïµå ·¹ºó µîÀÌ ±× µÚ¸¦ À̾ú´Ù. ÇÏÁö¸¸ ¾î¶² ¹æ¹ý¿¡ µå´Â ºñ¿ëÀÌ ±× ¹æ¹ýÀ¸·Î ¹®Á¦¸¦ ÇØ°áÇÏ´Â µ¥ ÇÊ¿äÇÑ ¿¬»êÀÇ ¼ö¿¡ µû¶ó ´Þ¶óÁø´Ù´Â ¹ß»óÀº ¾ÆÁ÷±îÁö ½Ç¹« ÇÁ·Î±×·¡¸ÓµéÀÇ ÀÇ½Ä ¼Ó¿¡ ÆÄ°í µéÁö ¸øÇÏ°í ÀÖ¾ú´Ù.

´ë½Å ½Ç¹«ÀÚµé°ú ¸¹Àº ÇÐÀÚµéÀº Á÷Á¢ ÀڽŵéÀÇ ÄÄÇ»ÅÍ¿¡¼­ ±×µéÀÇ ¾Ë°í¸®ÁòÀ» ½ÇÇàÇÏ¿©, ÀÌÀüÀÇ ÄÄÇ»Å͵鿡¼­ °ø½ÄÀûÀ¸·Î ¹ßÇ¥µÈ ¾Ë°í¸®ÁòµéÀ» »ç¿ëÇÏ´Â °æ¿ì¿Í ½Ã°£À» ºñ±³ÇØ º¸¾Ò´Ù. ÀÌ°ÍÀº °í¼ÓÀÇ ÄÄÇ»ÅÍ¿¡¼­ ÁúÀÌ ³·Àº ¾Ë°í¸®ÁòÀ» ¼öÇàÇÏ´Â °ÍÀÌ Àú¼ÓÀÇ ÄÄÇ»ÅÍ¿¡¼­ ¿ì¼öÇÑ ¾Ë°í¸®ÁòÀ» ¼öÇàÇÏ´Â °Íº¸´Ù ³ªÀº °ÍÀ¸·Î º¸ÀÏ °ÍÀ̶ó´Â °á°ú¸¦ ³º¾Ò´Ù!

È©Å©·ÎÇÁÆ®¿Í ŸÀÜÀº Æò¸é ¹®Á¦¸¦ ´Ù·é ³í¹®¿¡¼­ Çй®Àû ¾ß¸¸¼ºÀ» º¸ÀÌ´Â Çö´ëÀÇ °üÇà¿¡ ´ëÇØ ´ÙÀ½°ú °°Àº ŵµ¸¦ ¹àÇû´Ù. "ÇÏÁö¸¸ Áö±Ý±îÁö ¾Ë°í¸®Áò ½ÇÇà ½Ã°£ÀÇ ¾ö¹ÐÇÑ ºÐ¼®À» À§ÇØ ÇàÇØÁø ¿¬±¸´Â ³î¶ö¸¸Å­ ¹Ì¹ÌÇÑ ¼öÁØ¿¡ Áö³ªÁö ¾ÊÀ¸¸ç, ¾Ë°í¸®ÁòµéÀº °è¼ÓÇؼ­ ÀÌÀü¿¡ °ø½ÄÈ­µÈ ¾Ë°í¸®Áòµé¿¡ ºñÇØ ¸í¹éÈ÷ ¿­µîÇÑ °ÍÀ¸·Î ³ªÅ¸³ª°í ÀÖ½À´Ï´Ù."

È©Å©·ÎÇÁÆ®¿Í ŸÀÜÀº ±× ´ë½Å °¡»ê, ºñ±³, °£¼± ¿îÇà µî°ú °°ÀÌ ¾Ë°í¸®Áò¿¡ ¿ä±¸µÇ´Â ±âº» ¿¬»êÀÇ ¼ö¸¦ Åä´ë·Î ¾Ë°í¸®ÁòÀÇ ¼Óµµ¸¦ ÃøÁ¤ÇÒ °ÍÀ» ÁÖâÇÏ¿´´Ù. Æò¸é ¾Ë°í¸®ÁòÀÇ ½ÇÁúÀûÀÎ ¼º°ø¿¡ µû¶ó, ÀÌ Á¢±Ù ¹æ½ÄÀº °ð ÄÄÇ»ÅÍ °úÇÐÀÇ ÀÌ·Ð»Ó ¾Æ´Ï¶ó ½ÇÇàÀÇ Ãø¸é¿¡¼­µµ ¼ÒÁßÇÑ °ÍÀ¸·Î ¹Þ¾Æµé¿©Áö°Ô µÇ¾ú´Ù. ¶ÇÇÑ, º§ ¿¬±¸¼Ò (Bell Labs) ÀÇ ¾Ë ¾ÆÈ£ (Al Aho) ¿Í È©Å©·ÎÇÁÆ®, ±×¸®°í ÇÁ¸°½ºÅÏ ´ëÇÐÀÇ Á¦ÇÁ ¿ï¸Õ (Jeff Ullman) µîÀÌ 1974 ³â ¾Ë°í¸®Áò¿¡ ´ëÇØ ³Î¸® »ç¿ëµÈ ±³À縦 ÁýÇÊÇÏ´Â µ¥¿¡µµ Ʋ¸²¾øÀÌ µµ¿òÀ» ÁÖ¾úÀ» °ÍÀÌ´Ù. ±× Ã¥¿¡¼­´Â ¹Ù·Î ÀÌ ¹æ¹ýÀ» »ç¿ëÇØ ¾Ë°í¸®ÁòÀÇ ¼Óµµ¸¦ ÃøÁ¤ÇÏ¿´´Ù.

È¿À²ÀûÀÎ Æò¸é °Ë»ç¸¦ ÅëÇØ ¾ò°Ô µÈ ¶Ç ÇϳªÀÇ ºÎ¼öÀû È¿°ú´Â ±íÀÌ ¿ì¼± °Ë»ö ÀÚü°¡ ³Î¸® ÀÀ¿ëµÈ´Ù´Â »ç½ÇÀ» ÀνÄÇÏ°Ô µÈ °ÍÀ̾ú´Ù. È©Å©·ÎÇÁÆ®¿Í ŸÀÜÀÌ Æ©¸µ»óÀ» ¼ö»óÇÑ ÀÚ¸®¿¡¼­ ±× ÇØÀÇ ÃÖ°í ÄÄÇ»ÅÍ Ã¼½º ÇÁ·Î±×·¥À¸·Î ¼±Á¤µÇ¾ú´ø »ç¶÷Àº ÀÚ½ÅÀÇ ÇÁ·Î±×·¥ÀÌ Ã¼½º °ÔÀÓÀ» ÇÏ´Â µ¿¾È ±íÀÌ ¿ì¼± °Ë»öÀ» 4 õ¸¸ ¹ø ÀÌ»ó »ç¿ëÇÏ¿´´Ù°í ¹àÇû´Ù.

ŸÀÜÀº 1971 ³â ¹Ú»ç ÇÐÀ§¸¦ ¹ÞÀº ÈÄ, ÄÚ³ÚÀÇ Á¶±³¼ö·Î °¬´Ù. ±×°÷¿¡¼­µµ ¾Ë°í¸®ÁòÀÇ È¿À²¼º¿¡ ´ëÇÑ ±×ÀÇ °ü½ÉÀº »ç±×¶óµéÁö ¾Ê¾Ò´Ù.

ÇÕÁýÇÕ Ã£±â (union-find) ¿Í »ó°¢ (amortization)

ÄÚ³Ú¿¡ µµÂøÇÑ ÈÄ Å¸ÀÜÀº °ð 'ÇÕÁýÇÕ Ã£±â (union-find)' ¶ó°í ÇÏ´Â ±â¸¸ÀûÀ¸·Î ´Ü¼øÇÑ ¹®Á¦¿¡ ´ëÇÑ ¿¬±¸¿¡ Âø¼öÇÏ¿´´Ù. ±× ÀÛ¾÷ÀÌ È¿À²ÀûÀ¸·Î ½ÇÇàµÇ¸é ¾ÆÁÖ ´Ù¾çÇÑ ¹üÀ§ÀÇ ´Ù¸¥ ¹®Á¦µéÀ» º¸´Ù »¡¸® ÇØ°áÇÒ ¼ö ÀÖµµ·Ï ¸¸µé¾î ÁÙ °ÍÀ̾ú´Ù.

¸¹Àº ±×·¡ÇÁ ¾Ë°í¸®Áò¿¡¼­ ³ëµå´Â 'ºÐÇÒ (partition)' À̶ó°í ÇÏ´Â »óÀÌÇÑ ÁýÇÕµé·Î ±¸ºÐµÇ¾î¾ß ÇÑ´Ù. ¾Ë°í¸®ÁòÀÌ ÁøÇàµÇ´Â °úÁ¤¿¡¼­ ±× »óÀÌÇÑ ºÐÇÒµéÀº ÇÕº´µÇ¾î º¸´Ù Å« ºÐÇÒÀ» ÀÌ·ê °ÍÀÌ´Ù.

¿¹¸¦ µé¾î, ¾î¶² ¹®Á¦°¡ ´ÜÀÏ ºÐÇÒ ³»ÀÇ ¸ðµç ³ëµå´Â ¿¬°áµÇ¾î ÀÖ¾î¾ß ÇÑ´Ù°í ÁöÁ¤ÇÑ´Ù´Â °¡Á¤À» ÇØ º¸ÀÚ. ±× ºÐÇÒ ³»¿¡´Â °¢°¢ÀÇ ¸ðµç ³ëµå¿¡¼­ ±× ¹ÛÀÇ ¸ðµç ³ëµå·Î ¿¬°áµÇ´Â ÇϳªÀÇ °æ·Î°¡ Á¸ÀçÇÒ °ÍÀÌ´Ù.

±× ¹®Á¦¸¦ ÇØ°áÇÏ´Â ¾Ë°í¸®ÁòÀÇ ÇÑ ´Ü°è¿¡¼­ ºÐÇÒ A ¿¡ µé¾î ÀÖ´Â ¾î¶² ³ëµå¿Í ºÐÇÒ B ÀÇ ¾î¶² ³ëµå°¡ °£¼±À¸·Î ¿¬°áµÇ¾î ÀÖÀ½À» ¹ß°ßÇÑ´Ù°í °¡Á¤ÇØ º¸ÀÚ. ±×·² °æ¿ì, ±× µÎ °³ÀÇ ºÐÇÒÀº ¹Ýµå½Ã Çϳª·Î ÇÕº´µÇ¾î ±× ¾ÈÀÇ ¸ðµç ¸â¹ö°¡ ºÐÇÒ A ÀÇ ¿ø¼Ò¿Í ºÐÇÒ B ÀÇ ¿ø¼ÒµéÀÇ ÇÕÁýÇÕÀÌ µÇµµ·Ï ÇØ¾ß ÇÑ´Ù.

±×¸² 4 ´Â ±× ÇÑ ¿¹¸¦ º¸¿© ÁØ´Ù. óÀ½¿¡´Â °¢°¢ÀÇ ¿ä¼ÒµéÀÌ ´Üµ¶À¸·Î °í¸³µÈ ÇϳªÀÇ ÁýÇÕÀ» ÀÌ·ç°í ÀÖ´Ù (±×¸² 4 ÀÇ a ºÎºÐ ÂüÁ¶). ÀÌ ¿¹¿¡¼­ ºÐÇÒ A ´Â ÁýÇÕ {1, 2, 4} ÀÌ°í ºÐÇÒ B ´Â ÁýÇÕ {3, 6} À̸ç, °á°úÀûÀ¸·Î ¸¸µé¾îÁö´Â ºÐÇÒÀº {1, 2, 4, 3, 6} ÀÇ ¿ø¼ÒµéÀ» °¡Áø´Ù.

±×¸² 4  ÇÕÁýÇÕ Ã£±â

µÎ °³ÀÇ ÁýÇÕÀÌ Çϳª·Î ÇÕº´µÉ ¶§¸¶´Ù ÇϳªÀÇ 'Á¤±Ô ³ëµå' ¿¡¼­ ´Ù¸¥ ÇϳªÀÇ Á¤±Ô ³ëµå·Î È­»ìÇ¥°¡ ±×·ÁÁö¸ç, ±× È­»ìÇ¥´Â ´ëü·Î ÀÛÀº ÁýÇÕ¿¡¼­ Å« ÂÊÀ» ÇâÇÑ´Ù (±×¸² 4 ÀÇ b ºÎºÐ¿¡¼­, 6 ¿¡¼­ 2 ¸¦ ÇâÇØ Á¡¼±À¸·Î ±×·ÁÁø °£¼±). ¾î¶² ÁýÇÕÀÇ 'Á¤±Ô ³ëµå (canonical node)' ¶õ ±×°ÍÀ» ±âÁ¡À¸·Î Ãâ¹ßÇÏ´Â °£¼±ÀÌ Çϳªµµ ¾ø´Â ³ëµå¸¦ ¸»ÇÑ´Ù. ÀÌ°ÍÀÌ ¹Ù·Î ÇÕÁýÇÕ Ã£±â ¾Ë°í¸®ÁòÀÇ ÇÕÁýÇÕ ¿¬»êÀÌ´Ù.

°¢ ºÐÇÒÀÇ ¿ø¼Ò ±¸¼ºÀº ½Ã°£¿¡ µû¶ó ´Þ¶óÁö±â ¶§¹®¿¡, ÈǸ¢ÇÑ ÀÚ·á ±¸Á¶¶ó¸é ±× ¾Ë°í¸®ÁòÀÌ Æ¯Á¤ÇÑ ½ÃÁ¡¿¡ ¾î¶² µÎ °³ÀÇ ³ëµå°¡ µ¿ÀÏÇÑ ºÐÇÒ¿¡ ¼ÓÇØ ÀÖ´ÂÁö ¿©ºÎ¸¦ ½±°Ô ¾Ë¾Æ³¾ ¼ö ÀÖµµ·Ï ÇØ ÁÖ¾î¾ß ÇÑ´Ù.

±×¸² 4 ÀÇ b ºÎºÐ¿¡¼­ º¸¿©Áö´Â ±¸Á¶´Â '»óÇâ Æ®¸® (up-tree)' ÀÇ ÇÑ ¿¹ÀÌ´Ù. »óÇâ Æ®¸®¶ó´Â ¿ë¾î´Â 1964 ³â °¶·¯ (B. A. Galler) ¿Í ÇǼŠ(M. J. Fischer) °¡ ºÐÇÒ ³»¿¡¼­ ¿¬°áµÈ °£¼±ÀÌ Çϳªµµ ¾ø´Â ³ëµå°¡ ¹Ù·Î ºÐÇÒ ½Äº°ÀÚ°¡ µÇ´Â ±¸Á¶¸¦ ³ªÅ¸³»±â À§ÇØ Á¦¾ÈÇÑ °³³äÀÌ´Ù. µÎ ³ëµå´Â ºÐÇÒ ½Äº°ÀÚ¸¦ ÇâÇØ °ðÀå À§·Î ±×·ÁÁø °£¼±µéÀ» ´Ù¶ó°¨À¸·Î½á, ÀڽŵéÀÌ µ¿ÀÏÇÑ ºÐÇÒ¿¡ ¼ÓÇØ ÀÖ´ÂÁö ¿©ºÎ¸¦ ¾Ë¾Æ³¾ ¼ö ÀÖ´Ù. ´Ù½Ã ¸»ÇØ, µÎ ³ëµå°¡ µ¿ÀÏÇÑ ÁýÇÕ¿¡ ¼ÓÇØ ÀÖ´ÂÁö¸¦ È®ÀÎÇÒ ¶§¿¡´Â ´ÜÁö ±×µéÀÌ µ¿ÀÏÇÑ Á¤±Ô ³ëµå¸¦ °¡Áö°í ÀÖ´ÂÁö¸¸ ¾Ë¾Æ º¸¸é µÇ´Â °ÍÀÌ´Ù. ÀÌ°ÍÀÌ ÇÕÁýÇÕ Ã£±â ¾Ë°í¸®ÁòÀÇ 'ã±â (find)' ¿¬»êÀÌ´Ù. µû¶ó¼­, ã±â (3) = 2 ÀÌ°í ã±â (1) = 2 À̹ǷΠ±×µéÀº µ¿ÀÏÇÑ ÁýÇÕ¿¡ ¼ÓÇÏ´Â ¹Ý¸é, ã±â (5) = 5 (°Å±â¼­ Ãâ¹ßÇÏ´Â °£¼±ÀÌ Çϳªµµ ¾ø±â ¶§¹®¿¡) À̹ǷΠ5 ´Â 6 À̳ª 3 °ú ´Ù¸¥ ÁýÇÕ¿¡ ¼ÓÇØ ÀÖÀ½À» ¾Ë ¼ö ÀÖ´Ù.

°¢°¢ÀÇ Ã£±â ¿¬»êÀº ºÐÇÒ ½Äº°ÀÚ·Î ¿¬°áµÇ´Â °æ·Î¸¦ °¡´ÉÇÑ ÇÑ ¸¹ÀÌ ´ÜÃà½ÃŲ´Ù. '°æ·Î ¾ÐÃà (path compression)' À̶ó°í ºÎ¸£´Â ÀÌ Ãß°¡ ÀÛ¾÷À» ÇàÇØ ÀÌÈÄÀÇ ÇÕÁýÇÕ ¿¬»êÀ̳ª ã±â ¿¬»êÀÇ ¼Óµµ¸¦ ³ô¿©ÁÖ´Â °ÍÀÌ´Ù. ±×¸² 4 ÀÇ c ºÎºÐÀº È©Å©·ÎÇÁÆ®-¿ï¸Õ ¾Ë°í¸®ÁòÀÌ 3 ¿¡¼­ 2 ·Î °¡´Â °æ·Î¸¦ ´ÜÃàÇϱâ À§ÇØ ¾î¶»°Ô °æ·Î ¾ÐÃàÀ» »ç¿ëÇÏ°í ÀÖ´ÂÁö¸¦ º¸¿© ÁØ´Ù. ÀÌ·± ½ÄÀ¸·Î ÇÏ¸é ¾ÕÀ¸·Î´Â 3 ¿¡¼­ ã±â¸¦ ½ÇÇàÇÒ ¶§ ¿ÀÁ÷ ÇÑ ´Ü°è¸¸À» ÇÊ¿ä·ÎÇÏ°Ô µÉ °ÍÀÌ´Ù.

¸¹Àº ¾Ë°í¸®Áò¿¡¼­ ÇÕÁýÇÕ Ã£±â°¡ ÇÏ´Â ¿ªÇÒÀº ¸¶Ä¡ ¸¶Ãµ·ç¿¡¼­ ¿¤¸®º£ÀÌÅÍÀÇ ¿ªÇÒ°ú °°´Ù. ºü¸¥ ¿¤¸®º£ÀÌÅÍ ¾øÀ̵µ °Ç¹°À» ¼¼¿ï ¼ö´Â ÀÖÁö¸¸, »ç¶÷µéÀ» ¸¸Á·½Ãų ¼ö´Â ¾øÀ» °ÍÀÌ´Ù. ±×·¯ÇÑ ÀÌÀ¯¿¡¼­ °¡´ÉÇÑ ÇÑ °¡Àå ºü¸¥ ÇÕÁýÇÕ Ã£±â ¾Ë°í¸®ÁòÀ» ã¾Æ ³»´Â °ÍÀº ÇʼöÀûÀ̾ú´Ù. ±×·¸°Ô ÇÏ´Â µ¥¿¡´Â ¾ÆÁÖ ÁÖÀÇ ±íÀº ŸÀÌ¹Ö ºÐ¼®ÀÌ ¿ä±¸µÈ´Ù. ŸÀÜÀÌ Å©°Ô ±â¿©ÇÑ ¹Ù´Â ¹Ù·Î ÀÌ°°Àº ºÐ¼®À» ¼öÇàÇÑ °ÍÀ̾ú´Ù.

±×¿¡ ¾Õ¼­ È©Å©·ÎÇÁÆ®¿Í ¿ï¸ÕÀº Çʽà ¼±Çü ½Ã°£ÀÇ »óÇÑÀ» Áõ¸íÇÏ¿´À» °ÍÀÌ´Ù. ¼±Çü ½Ã°£ÀÇ »óÇÑÀº Æò¸é ¹®Á¦¿¡¼­ ó·³ ¹®Á¦ÀÇ Å©±â¸¦ µÎ ¹è·Î È®´ëÇÏ¸é ½Ã°£ÀÌ ¹è°¡ °É¸°´Ù´Â °ÍÀ» ÀǹÌÇÑ´Ù. 1973 ³â ¾Ë°í¸®ÁòÀ» ÁÖÁ¦·Î ¿­¸° IBM ÀÇ ÇÑ ¿öÅ©¼ó¿¡¼­ ¿¹ÀÏ´ëÀÇ ¸¶ÀÌÅ© ÇǼŴ ȩũ·ÎÇÁÆ®-¿ï¸ÕÀÇ Áõ¸íÀÌ Áö´Ñ ÇÑ °¡Áö °áÇÔÀ» ÁöÀûÇÏ¿´´Ù. ŸÀÜÀº ±× ¹®Á¦¿¡ ´ëÇØ »ý°¢Çϱ⠽ÃÀÛÇß´Ù. ±×´Â ½Ã°£ Á¦ÇÑÀÌ »ç½Ç»ó Ãʼ±ÇüÀû (superlinear) À̶ó´Â °Í, Áï Å©±â°¡ µÎ ¹è·Î Ä¿Áø ¹®Á¦¿¡ µÎ ¹è°¡ ³Ñ´Â ½Ã°£ÀÌ ¿ä±¸µÉ °ÍÀ̶ó´Â °É º¸¿© ÁÖ´Â ¾î¶² ÁÁÁö ¾ÊÀº ±¸¼ºÀÇ »ç·ÊµéÀÌ ÀÖ¾ú´ÂÁö¸¦ ÀǽÉÇÏ¿´´Ù. ŸÀÜÀº ½ÇÁ¦·Î ¼±ÇüÀÌ µÉ ¼ö ÀÖ´Â ¾Ë°í¸®ÁòÀº Çϳªµµ ¾ø´Ù´Â °ÍÀ» ¾Ï½ÃÇϸ鼭, ¿ª ¾ÖÄ¿¸¸ ÇÔ¼ö (inverse Ackermann's function) ¸¦ Á¦°øÇÏ´Â ÀÌÁß Àç±ÍÀû ±¸¼º (doubly recursive construction) À» ±× ¹®Á¦¿¡ ´ëÇÑ ÇÏÇÑÀ¸·Î Á¦½ÃÇÏ¿´´Ù. ³ªÁß¿¡ ±×´Â À̸¸Å­ÀÇ ½Ã°£ÀÌ °É¸®´Â ¾Ë°í¸®ÁòÀ» ½ÇÁ¦·Î º¸¿©ÁÜÀ¸·Î½á ±× ÇÏÇÑÀÌ ¶ÇÇÑ ÇϳªÀÇ »óÇÑÀÓÀ» Áõ¸íÇÏ¿´´Ù.

µû¶ó¼­, ´Ù¼Ò ³­ÇØÇÑ ÀÌ ÇÔ¼ö´Â ÀÌó·³ ¾ÆÁÖ ´Ü¼øÇÑ ÀÚ·á ±¸Á¶ÀÇ ºÐ¼®¿¡¼­ °íÀ¯ÇÑ ¾ç½ÄÀ¸·Î ³ªÅ¸³³´Ï´Ù. ¹Ù·Î ±× Á¡ÀÌ ÀÌ ¹®Á¦¿Í °ü·ÃÇÏ¿© ³î¶ó¿î »ç½ÇÀ̾úÁö¿ä. ±×°ÍÀ» ¿¹ÃøÇÒ ¼ö ÀÖ´Â ¹æ¹ýÀº ÀüÇô ¾ø¾ú½À´Ï´Ù. ´ëºÎºÐÀÇ »ç¶÷µéÀÌ ¾Ë°í¸®ÁòÀÇ ½ÇÇà ½Ã°£Àº ¼±ÇüÀ̶ó°í ¹Ï¾úÁö¿ä.

ÀÌ·¯ÇÑ ¹ÏÀ½Àº »ç½Ç»ó Áø½Ç¿¡ °¡±î¿ü´Ù. ¾ÖÄ¿¸¸ ÇÔ¼ö´Â ¿ø·¡ ¼øȯ ÀÌ·ÐÀ̶ó°í ¾Ë·ÁÁ® ÀÖ´Â ¼öÇÐÀÇ ¹ßÀüµÈ ºÎ¹®¿¡¼­ ÇϳªÀÇ ¿¹·Î °í¾ÈµÈ °ÍÀ̾ú´Ù. ±× ÇÔ¼ö´Â ¾ÆÁÖ ±Þ¼ÓÇÏ°Ô Áõ°¡ÇÑ´Ù. ÀÌ´Â ´Ù½Ã ¿ª ¾ÖÄ¿¸¸ ÇÔ¼ö´Â ¾î¶°ÇÑ ¿ø°Ý ½ÇÇà ÀÀ¿ë ÇÁ·Î±×·¥¿¡ ´ëÇؼ­µµ °áÄÚ 5 ÀÌ»óÀÌ µÉ ¼ö ¾øÀ» ¸¸Å­ ¾ÆÁÖ ´À¸®°Ô Áõ°¡ÇÑ´Ù´Â °ÍÀ» ÀǹÌÇÑ´Ù.

±×·¯³ª Æò¸é ¹®Á¦¿¡¼­Ã³·³ ±× °á°ú´Â ³î¶ó¿î °ÍÀ̾ú´Ù. ´©±¸µµ ¾ÖÄ¿¸¸ ÇÔ¼ö°¡ ½Ç»ýÈ°¿¡¼­ ÀÀ¿ëµÉ °ÍÀ̶ó°í´Â »ý°¢ÇÏÁö ¸øÇß¾ú±â ¶§¹®ÀÌ´Ù. ÀÌ·Î ÀÎÇØ ¿¬±¸ÀÚµéÀº ŸÀÜÀÌ °í¾ÈÇÏ¿´´ø »õ·Î¿î ºÐ¼® ½Ã¹ýÀ» °ËÅäÇÏ°Ô µÇ¾ú´Ù.

ÇÕÁýÇÕ Ã£±âÀÇ ºÐ¼®Àº ¾î·Æ´Ù. ã±â ¿¬»êÀº ÀÏ´Ü °æ·Î°¡ ¾ÐÃàµÇ±â¸¸ Çϸé (±×¸² 4 ÀÇ c ºÎºÐ) Æ÷ÀÎÅÍ ¿îÇàÀ» ´Ü ÇÑ ¹ø¸¸ ¿ä±¸ÇÏ°Ô µÇÁö¸¸, °æ·Î°¡ ¾ÐÃàµÇÁö ¾Ê¾ÒÀ» °æ¿ì ±ä ¿îÇàÀ» ÇÊ¿ä·ÎÇÏ°Ô µÉ °ÍÀ̱⠶§¹®ÀÌ´Ù.

´ÜÀÏÇÑ Ã£±â ¿¬»êÀº ¸¹Àº ¿¬»êµéÀ» ÃëÇÒ ¼ö ÀÖ´Ù. ±× ´ç½Ã±îÁö Á¸ÀçÇÑ ºÐ¼® ±â¹ýµé (È©Å©·ÎÇÁÆ®¿Í ŸÀÜÀÌ Æò¸é ¹®Á¦¿¡ ´ëÇØ »ç¿ëÇÑ °Íµé±îÁö Æ÷ÇÔÇÏ¿©) À» »ìÆì º¸¸é, ¿¬±¸ÀÚµéÀº ÃÖ¾ÇÀÇ °æ¿ì ¿¬»êÀÇ ¼ö¿Í ´ÜÀÏ ¿¬»ê¿¡ µå´Â ½Ã°£À» °öÇÏ´Â ¹æ½ÄÀ¸·Î ¾Ë°í¸®ÁòÀÇ ³­À̵µ¸¦ ÃøÁ¤ÇÏ¿´´Ù. ³Î¸® ÀÎÁ¤µÇ´Â ¹Ù¿Í °°ÀÌ ÀÌ º¸¼öÀûÀÎ ¹æ¹ýÀº ´ëü·Î À¯¿ëÇÏ¿´´Ù. ÇÏÁö¸¸ ŸÀÜÀº ±× Ç¥ÁØÀûÀÎ ºÐ¼® ±â¹ýÀÌ ÀÌ ¹®Á¦¿¡ ÀûÀýÄ¡ ¸øÇÏ°Ô ¸¹Àº ½Ã°£À» ºÎ¿©ÇÑ´Ù´Â °ÍÀ» ÀνÄÇÏ¿´´Ù.

¾î¶² ´ÜÀÏÇÑ Ã£±â ¿¬»ê¿¡´Â ±ä ½Ã°£ÀÌ °É¸®´Â ¹Ý¸é, ±× ±æÀ» µû¶ó °æ·Î ¾ÐÃàÀ» ¼öÇàÇÔÀ¸·Î½á ¾ÕÀ¸·ÎÀÇ Ã£±â ¿¬»êµé¿¡ µå´Â ½Ã°£Àº ÁÙÀÏ ¼ö°¡ ÀÖ´Ù. Áï, ¸î ³â ÈÄ Å¸ÀÜ°ú ±×ÀÇ Á¦ÀÚ ´ë´Ï ½½¸®ÅÍ (Danny Sleator) °¡ ȸ°è ºÐ¾ß¿¡¼­ ºô¾î ¿Â ¿ë¾î¸¦ »ç¿ëÇϸé, ã±â ¿¬»ê Çϳª¸¦ Ãß°¡ÇÏ´Â ÀÛ¾÷Àº ±×°ÍÀ¸·Î ÇýÅÃÀ» ¹Þ´Â ¸¹Àº ã±â ¿¬»êµé¿¡¼­ '»ó°¢ (amortized)' µÇ´Â °ÍÀÌ´Ù.

¿äÁ¡Àº ¾î¶² ÀÚ·á ±¸Á¶»ó¿¡¼­ ±æ°Ô À̾îÁö´Â ÀÏ·ÃÀÇ ¿¬»êµéÀ» °®°Ô µÈ´Ù´Â °ÍÀÔ´Ï´Ù. °³º° ¿¬»êµé¿¡´Â »ó°ü ¾øÀÌ, ±× ¼ø¼­ Àü¹Ý¿¡ °ÉÄ£ ¿¬»êÀÇ Æò±Õ ½Ã°£¿¡ °ü½ÉÀ» °¡Á®¾ß ÇÕ´Ï´Ù.

¸¶Ä¡ ±íÀÌ ¿ì¼± °Ë»öÀÌ Ç¥ÁØÀûÀÎ ¾Ë°í¸®Áò ±â¹ýÀÌ µÇ¾ú´ø °Íó·³, »ó°¢Àº Ç¥ÁØÀûÀÎ ºÐ¼® ±â¹ýÀ¸·Î ÀÚ¸®Àâ°Ô µÇ¾ú´Ù. ±× °á°ú ÇϳªÀÇ ¿¬»êÀÌ ±× µ¿·á ¿¬»êµé¿¡ ´ëÇØ ÀÌŸÀûÀ¸·Î ÇൿÇÏ´Â ¼ö¸¹Àº ¾Ë°í¸®ÁòÀÌ ¸¸µé¾îÁö°Ô µÇ¾ú´Ù.

³×Æ®¿öÅ© ÃÖ´ë À¯·®

1973 ³â ÀÌ»çÄ«¿¡¼­ µÎ ¹ø°·Î ¸ÂÀÌÇÑ È¤µ¶ÇÑ °Ü¿ïÀº ŸÀÜÀ¸·Î ÇÏ¿©±Ý ¹öŬ¸®¿¡¼­ º¸³»¿Â Á¦¾ÈÀ» ¹Þ¾ÆµéÀÌ°Ô ¸¸µé¾ú´Ù. ±×´Â ±×°÷À¸·Î °¡¼­ 2 ³âÀ» º¸³½ ÈÄ, 1975 ³â ´Ù½Ã ½ºÅÄÆÛµå·Î µ¹¾Æ°¬´Ù. °Å±â¼­ ±×°¡ °¡¸£Ä£ ´ëÇпø»ýµé Áß Çϳª°¡ ¹Ù·Î ´ë´Ï ½½¸®ÅÍ¿´´Ù. »ó°¢µÇ´Â ½Ã°£¿¡ ´ëÇÑ ¹ß»óÀº ŸÀÜ°ú ½½¸®ÅÍ°¡ ³×Æ®¿öÅ©ÀÇ ÃÖ´ë À¯·®À̶ó´Â ¹®Á¦¿¡ ´ëÇÑ ¿¬±¸¸¦ ÁøÇàÇϸ鼭 ´Ù½Ã ºÎ°¢µÇ¾ú´Ù.

´ç½Å¿¡°Ô °£¼±ÀÌ ¿ëÀûÀ» °¡Áö´Â À¯Çâ ±×·¡ÇÁ (directed graph) ¿Í ÇÔ²² ¿ø½Ã (source) ¿Í Á¾Âø (sink) ÀÌ ÁÖ¾îÁ³½À´Ï´Ù. ±× °£¼±µéÀº ÆÄÀÌÇÁ¸¦ ³ªÅ¸³»¸ç, ´ç½ÅÀº ±× ÆÄÀÌÇÁµéÀ» ÅëÇØ ¹«¾ð°¡¸¦ ÆßÇÁ·Î Æۿø®°í ÀÖ´Ù°í °¡Á¤ÇØ º¾½Ã´Ù. ´ç½ÅÀº ¿ø½Ã¿¡¼­ Á¾Âø±îÁö ±× ³»¿ë¹°ÀÇ ÃÖ´ë·®À» °¡Á®¿À°í ½Í¾îÇÕ´Ï´Ù.

±×¸² 5  ³×Æ®¿öÅ©ÀÇ ÃÖ´ë À¯·®

±×¸² 5 ÀÇ ±×·¡ÇÁ A ´Â ¼®À¯ ¼ö¼Û¸ÁÀ» Ç¥ÇöÇÑ ±×·¡ÇÁÀÌ´Ù. ¿©±â¼­ °¢°¢ÀÇ ÆÄÀÌÇÁ (°£¼±) ´Â ¿ë·® (¼ýÀڷΠǥ½ÃµÈ) À» °¡Áö°í ÀÖÀ¸¸ç, ±×°ÍÀº ±× ÆÄÀÌÇÁ (°£¼±) ¸¦ ÅëÇØ À̵¿ÇÒ ¼ö ÀÖ´Â ÃÖ´ë À¯·®À» ³ªÅ¸³½´Ù. ±×·¡ÇÁ B ´Â ±× ¿ë·®µé°ú s ¿¡¼­ t ±îÁöÀÇ ÃÑÀ¯·® 115 °¡ ÁÖ¾îÁ³À» ¶§ ±× ¼ö¼Û¸Á ÀüüÀÇ ÃÖ´ë À¯·®À» º¸¿© ÁØ´Ù. ³×Æ®¿öÅ© À¯·®ÀÇ ¹®Á¦´Â ÁÖ¾îÁø ³×Æ®¿öÅ© ÀüüÀÇ ÃÖ´ë·®À» ¹ß°ßÇÏ´Â °ÍÀ¸·Î ±¸¼ºµÈ´Ù.

1956 ³â Æ÷µå (L. R. Ford) ¿Í ǮĿ½¼ (D. R. Fulkerson) Àº ±× ¹®Á¦¸¦ Ç®¾î ³¾ ù ¹ø° ¾Ë°í¸®ÁòÀ» Á¤½ÄÀ¸·Î ¹ßÇ¥ÇÏ¿´´Ù.

Æ÷µå¿Í ǮĿ½¼ µÎ »ç¶÷ÀÌ ½º½º·Î ÁöÀûÇß´ø ¹Ù¿Í °°ÀÌ, ±× ¾Ë°í¸®ÁòÀº ƯÁ¤ÇÑ »ç·Ê¿¡ ´ëÇؼ­´Â ºñÈ¿À²ÀûÀ̾ú´Ù. ´õ¿í ¹®Á¦°¡ µÇ´Â °ÍÀº ¿ë·®ÀÌ ºÒÇÕ¸®ÇÒ °æ¿ì Á¤È®ÇÑ ´ä¿¡ À̸¦ ¼ö ¾ø´Ù´Â °ÍÀ̾ú´Ù. 10 ¿© ³âÀÌ Áö³­ 1969 ³â ¿¡µå¸ÕÁî (J. Edmonds) ¿Í Ä«ÇÁ (R. M. Karp) ´Â ±× ¹®Á¦¸¦ Ǫ´Â ¾Ë°í¸®ÁòÀ» »õ·Ó°Ô ´Ùµë¾î ÈξÀ ´õ È¿À²ÀûÀ¸·Î ¸¸µé °ÍÀ» Á¦¾ÈÇÏ¿´´Ù. ±× ¾ÈÀº °£¼±ÀÇ ¼ö°¡ °¡Àå ÀûÀº Áõ°¡ °æ·Î¸¦ ¼±ÅÃÇÑ´Ù´Â °ÍÀ̾ú´Ù. ÀÌ ¹æ¹ýÀº ½ÇÇà ½Ã°£ÀÌ ³ëµåÀ¸ ¼ö¿¡ °£¼±ÀÇ ¼öÀÇ Á¦°öÀ» °öÇÑ °ª¿¡ ºñ·ÊÇÏ´Â ¾Ë°í¸®ÁòÀ» Á¦°øÇÏ¿´´Ù.

1970 ³â¿¡´Â µ¶ÀÚÀûÀ¸·Î ¿¬±¸ È°µ¿À» ÇÏ°í ÀÖ´ø ¼Òºñ¿¡Æ®ÀÇ ¼öÇÐÀÚ µð´Ð (E. A. Dinic) ÀÌ ¿¡µå¸ÕÁî¿Í Ä«ÇÁ°¡ Á¦½ÃÇß´ø °Í°ú ¶È°°Àº ¹ß°ßÀ» ÇÏ¿´´Ù. ÇÏÁö¸¸ µð´ÐÀº µ¿ÀÏÇÑ ¼ýÀÚ¸¦ °¡Áø ¸ðµç Áõ°¡ °æ·ÎµéÀ» ÇÑ ¹ø¿¡ ¹èÄ¡ÇÏ´Â ¹æ¹ýÀ» ã¾Æ³¿À¸·Î½á ÇÑ °ÉÀ½ ´õ ³ª¾Æ°£ °á°ú¸¦ º¸¿© ÁÖ¾ú´Ù. µÚÀ̾î Àεµ, À̽º¶ó¿¤, ¼Òºñ¿¡Æ®, ¹Ì±¹ µîÁöÀÇ ¿¬±¸ÀÚµéÀÌ Á¦¾ÈÇÑ ¾Ë°í¸®ÁòÀº ¸ðµÎ ÀÌ ¾ÆÀ̵ð¾î¸¦ ±âÃÊ·Î ÇÏ¿´´Ù. ŸÀÜ°ú ½½¸®ÅÍÀÇ ¾Ë°í¸®ÁòÀº »õ·Î¿î ÀÚ·á ±¸Á¶ÀÇ °í¾ÈÀ» ÅëÇØ º¸´Ù ºü¸¥ ¾Ë°í¸®ÁòÀ» ¾ò¾î³½ °ÍÀÌ´Ù.

±× ¹®Á¦¿¡¼­ °¡Àå Áß¿äÇÑ Á¡Àº ÇϳªÀÇ ¹®Á¦¸¦ ÇØ°áÇϱâ À§ÇÑ È¿À²ÀûÀÎ ÀÚ·á ±¸Á¶¸¦ ¾ò¾î ³»´Â °Í (°£¼±µéÀ» Æ÷È­ »óÅ·Π¹Ð¾î ºÎÄ¡¸é¼­) À̾úÀ½ÀÌ ÀÔÁõµÇ¾úÁö¿ä. µ¿Àû Æ®¸® (dynamic tree) ¶ó°í ¾Ë·ÁÁ® ÀÖ´Â ÀÚ·á ±¸Á¶°¡ ½½¸®ÅÍÀÇ ¹Ú»ç ÇÐÀ§ ³í¹®ÀÇ ±âÃÊ°¡ µÇ¾ú½À´Ï´Ù.

1980 ³â ŸÀÜ°ú ½½¸®ÅÍ´Â ´ºÀúÁö ÁÖ ¸Ó·¹ÀÌ Èú¿¡ ÀÖ´Â º§ ¿¬±¸¼Ò·Î °¬´Ù. ±×µéÀº ´Ù½Ã µ¿Àû Æ®¸®¿¡ ´ëÇÑ ¿¬±¸¸¦ ½ÃÀÛÇÏ¿´´Ù.

¿ì¸®´Â ¸¶Ä§³» ÃÖ¾ÇÀÇ °æ¿ì¿¡ ÃÊÁ¡À» µÎÁö ¾Ê°í ±×Àú ÀÌ·± ½ÄÀÇ ½Ã°£ Æò±Õ°ª ±¸Çϱâ (»ó°¢) ¿¡¸¸ ¸Å´Þ¸°´Ù¸é, ½ÇÁ¦·Î ÀÌ ÀÚ·á ±¸Á¶¸¦ ´Ü¼øÈ­ÇÒ ¼ö ÀÖÀ» °ÍÀ̶ó´Â »ç½ÇÀ» ±ú´Þ¾Ò½À´Ï´Ù.

¿ì¸®´Â »ó°¢ÀÇ °³³ä¿¡ °üÇØ º¸´Ù ü°èÀûÀÎ ¹æ½ÄÀ¸·Î »ý°¢Çϱ⠽ÃÀÛÇß½À´Ï´Ù. ±×¸®°í´Â ÀÚü Á¶Àý (self-adjusting) ÀÚ·á ±¸Á¶ÀÇ ¹ß»óÀ» ³»³õ¾Ò½À´Ï´Ù. ±×°ÍÀº ÃÖ¾ÇÀÇ °æ¿ì¿£ È¿À²ÀûÀÎ °ÍÀÌ µÉ ¼ö ÀÖ¾ú½À´Ï´Ù. ¿ì¸®´Â ÀÚü Á¶Àý ÀÚ·á ±¸Á¶¸¦ ¸¸µé¾î '»ç¼± Æ®¸® (splay tree)' ¶ó´Â À̸§À» ºÙ¿´½À´Ï´Ù. ±×°Ç Á¤¸» ¸ÚÁø ¼Ó¼ºµéÀ» °¡Áö°í ÀÖÁö¿ä.

°æ·Î ¾ÐÃà°ú ¸¶Âù°¡Áö·Î Æ®¸®¸¦ »ç¼±À¸·Î ¸¸µå´Â °Í ¿ª½Ã Æ®¸®»ó¿¡¼­ ¾ÆÁ÷ 󸮵ÇÁö ¾ÊÀº ¿¬»êµé¿¡ ÀÌÀÍÀ» ÁÖ±â À§ÇØ ÇϳªÀÇ ¿¬»êÀ» ¼öÇàÇÏ´Â ÀÛ¾÷ÀÌ´Ù. ÇÏÁö¸¸ »ç¼±È­ ÀÚü¿¡ ¸¹Àº ºñ¿ëÀÌ ÃÊ·¡µÉ ¼ö Àֱ⠶§¹®¿¡, ŸÀÜ°ú ½½¸®ÅÍ´Â °Å±â¼­ ¾ò¾îÁö´Â ÀÌÀÍÀÌ ºñ¿ëÀ» µéÀÏ ¸¸ÇÑ °¡Ä¡°¡ ÀÖÀ½À» º¸¿© ÁÖ±â À§ÇØ »ó°¢ ±â¹ýÀ» »ç¿ëÇØ¾ß Çß´Ù.

°æÀï

Æò¸é¼º°ú ³×Æ®¿öÅ© À¯·®À» ºñ·ÔÇØ Å¸ÀÜÀÌ 1980 ³â´ë ÃʹݱîÁö °ËÅäÇØ ¿Â ¿©·¯ °¡Áö ¹®Á¦µéÀº ¸ðµÎ ¸íÈ®ÇÏ°Ô Á¤ÀÇµÈ Á¤È®ÇÑ ÇØ´äÀ» °¡Áö°í ÀÖ¾ú´Ù. ±×·¡ÇÁ´Â Æò¸éÀ̰ųª ȤÀº Æò¸éÀÌ ¾Æ´Ï¸ç, À¯·®Àº ÃÖ´ëÀ̰ųª ȤÀº ÃÖ´ë°¡ ¾Æ´Ï´Ù. ÀÌ¿Í ´ëÁ¶ÀûÀ¸·Î ƯÁ¤ÇÑ ¹®Á¦µéÀº ´ÜÁö ÀåÁ¡ÀÇ ºñ±³ °³³ä¿¡¸¸ °ü¿©ÇÒ »Ó, ¸í¹éÇÏ°Ô ¿Ç°Å³ª ±×¸©µÈ ´äÀ» µµÃâÇØ ³»Áö´Â ¾Ê´Â´Ù.

ÇÑ °¡Áö À¯»çÇÑ ¿¹¸¦ »ìÆì º¸¸é ÀÌÇØ¿¡ µµ¿òÀÌ µÉ °ÍÀÌ´Ù. ¿ì¸®´Â ¾î¶² ÅõÀÚ Á¤º¸ÁöÀÇ ÇÊÀÚ°¡ ÁÁÀº ÁÖ½ÄÀ» Á¦¾ÈÇÒ °æ¿ì ±×°¡ ÈǸ¢ÇÏ´Ù°í ¹Ï´Â´Ù. ¿©±â¼­ ÁúÀ» Æò°¡ÇÒ ¼ö ÀÖ´Â ÇÑ °¡Áö ±âÁØÀº ¾î¶² ÅõÀÚÀÚ°¡ ¹Ì·¡¸¦ ¿Ïº®ÇÏ°Ô ³»´Ù º¸´Â õ¸®¾ÈÀ» °¡Áø »ç¶÷ÀÇ Ãæ°í¿¡ µû¸£´Â °Í¿¡ ºñÇØ ±× ÇÊÀÚÀÇ Ãæ°í¸¦ µû¸¦ ¶§ ¾ó¸¶³ª È¿°úÀûÀ¸·Î ÅõÀÚ¸¦ ÇÒ ¼ö Àִ°¡¸¦ º¸´Â °ÍÀÌ´Ù. õ¸®¾ÈÀ» Áö´Ñ Á¶¾ðÀÚ°¡ ½ÇÀç·Î Á¸ÀçÇÏ´Â °ÍÀº ºÒ°¡´ÉÇÒÁö¶óµµ, ÁÁÀº ºñ±³ ±âÁØÀ» Á¦°øÇØ ÁÖ´Â °ÍÀº »ç½ÇÀÌ´Ù. ŸÀÜ°ú ½½¸®ÅÍ´Â ¹öÆÛ °ü¸®ÀÇ ±âº»ÀûÀÎ ¹®Á¦¿¡ ´ëÇØ ¹Ù·Î ÀÌ¿Í °°Àº ºñ±³ ±âÁØÀ» Á¦½ÃÇÏ¿´´Ù.

ÄÄÇ»ÅÍ´Â ·¥ (RAM), Áï ÀÓÀÇ Á¢±Ù ±â¾ï ÀåÄ¡ (random access memory) ¶ó´Â °í¼Ó ¸Þ¸ð¸®¿Í À̺¸´Ù 1000 ¹è³ª ´À¸° 'µð½ºÅ© (disk)' ¶ó´Â ¶Ç ÇÑ °¡Áö ±â¾ï ÀåÄ¡¸¦ °¡Áö°í ÀÖ´Ù. ·¥Àº ÀϹÝÀûÀ¸·Î »ç¿ëÀÚ°¡ °ü½ÉÀ» °¡Áö´Â ¸ðµç ÀڷḦ ÀúÀåÇÒ ¼ö°¡ ¾ø±â ¶§¹®¿¡, ¹öÆÛ °ü¸®ÀÇ ¸ñÇ¥´Â °ð »ç¿ëµÉ °ÍÀ¸·Î º¸ÀÌ´Â ÀڷḸÀ» ·¥ ¹öÆÛ¿¡ µÎ´Â °ÍÀÌ´Ù. ¾î¶°ÇÑ ¾Ë°í¸®Áòµµ Àå·¡¸¦ ¿¹ÃøÇÒ ¼ö´Â ¾ø±â ¶§¹®¿¡, ½ÇÁ¦ ¾Ë°í¸®ÁòÀº ±â·ÏÀ» Åä´ë·Î ÇÑ ÃßÃø¿¡ ÀÇÇØ ÀÌ ¸ñÇ¥¸¦ ´Þ¼ºÇÑ´Ù. ±×¿Í °°Àº ¾Ë°í¸®ÁòÀ¸·Î °¡Àå ÀαⰡ ÀÖ´Â °ÍÀº ¼ÒÀ§ 'ÃÖ¼Ò ÃÖ±Ù »ç¿ë (least recently used)' À̶ó°í ºÒ¸®´Â °ÍÀÌ´Ù.

°¢°¢ÀÇ ÆäÀÌÁö¿¡ ´ëÇØ °¡Àå ÃÖ±Ù¿¡ °ËÅäµÈ ½Ã°£À» ÃßÀûÇÕ´Ï´Ù. ±×·¸°Ô Çؼ­ °¡Àå ¿À·¡µÈ ÆäÀÌÁö°¡ ¹ö·ÁÁö´Â °ÍÀÌÁö¿ä.

ÃÖ¼Ò ÃÖ±Ù »ç¿ëÀÇ Åä´ë¸¦ ÀÌ·ç´Â °ÍÀº ±× »ç¿ëÀÚÀÇ ÇÁ·Î±×·¥ÀÌ °¡Àå ÃÖ±Ù¿¡ Á¢ÃËÇÑ ÆäÀÌÁöµéÀÌ ¹Ù·Î ¾ó¸¶ ¾È ÀÖ¾î ´Ù½Ã Á¢Ã赃 °ÍÀ¸·Î ¿¹»óµÈ´Ù´Â °¡¼³ÀÌ´Ù. °ú°Å´Â ¹Ì·¡ÀÇ °Å¿ïÀÎ °ÍÀÌ´Ù.

´ç½ÅÀÌ ¹Ì·¡¸¦ ¾È´Ù°í °¡Á¤ÇØ º¾½Ã´Ù. Áï, ÆäÀÌÁö°¡ ¿ä±¸µÇ´Â Àüü ¼ø¼­¸¦ ¾Ë°í ÀÖ´Ù°í º¸´Â °ÍÀÌÁö¿ä. ±×·¸´Ù¸é ¾î¶² ½ÄÀ¸·Î °¡´ÉÇÑ ÃÖ¼±ÀÇ ÆäÀÌÁö Àü·«À» ¼¼¿ï ¼ö ÀÖÀ»±î¿ä? 1960 ³â´ë¿¡ IBM ÀÇ º§·¹µð (L. A. Belady) °¡ ÀÌ ¹®Á¦¸¦ ´Ù·ç¾ú½À´Ï´Ù. ±× ¾Ë°í¸®ÁòÀº ´ÙÀ½ ¹ø¿¡ »ç¿ëµÉ ½Ã±â°¡ °¡Àå ¸Õ ÆäÀÌÁö¸¦ °È¾îÂ÷ ¹ö¸®´Â °ÍÀ̾ú½À´Ï´Ù. ÇÏÁö¸¸ ¿ì¸° ¹Ì·¡¸¦ ¾ËÁö ¸øÇϱ⠶§¹®¿¡ ÀÌ°°Àº ¿ÀÇÁ¶óÀÎ½Ä (ÅëÂû·Â ÀÖ´Â) Àü·«Àº ½ÇÇà¿¡ ¿Å±æ ¼ö ¾ø½À´Ï´Ù. ¿©±â¼­ Á¦±âµÇ´Â ¹®Á¦´Â °¡´ÉÇÑ ÃÖÀû ¿ÀÇÁ¶óÀÎ½Ä Àü·«¿¡ ºñÇÒ ¼ö ÀÖ´Â ´Ü¼øÇÑ ¿Â¶óÀÎ½Ä Àü·«À» ¾ó¸¶³ª ÈǸ¢ÇÏ°Ô ´Ù·ê ¼ö Àִ°¡ÇÏ´Â Á¡ÀÔ´Ï´Ù.

½½¸®ÅÍ´Â '°æÀïÀû (competitive)' À̶ó´Â ´Ü¾î¸¦ ¸¸µé¾î ³Â½À´Ï´Ù. ¿Â¶óÀÎ ¾Ë°í¸®ÁòÀº ±× ¼º´ÉÀÌ °¡´ÉÇÑ ÃÖÀû ¿ÀÇÁ¶óÀÎ ¾Ë°í¸®ÁòÀÇ »ó¼ö ¹è ³»¿¡ ÀÖÀ» ¶§ °æÀï·ÂÀ» °¡Áý´Ï´Ù.

ŸÀÜ°ú ½½¸®ÅÍ´Â ÀÌ·¯ÇÑ ±âÁØ¿¡¼­ ÃÖ¼Ò ÃÖ±Ù »ç¿ë ¾Ë°í¸®ÁòÀÌ »ó´çÈ÷ ÈǸ¢ÇÏ°Ô Á¦ ¸òÀ» ÇÒ °ÍÀÓÀ» º¸¿© ÁÖ¾ú´Ù. Å©±â S ÀÇ ¹öÆÛ¿¡ ´ëÇÑ ÃÖ¼Ò ÃÖ±Ù »ç¿ëÀº, °¡·É ¾î¶² ÅëÂû·Â ÀÖ´Â ¾Ë°í¸®ÁòÀÌ Å©±â S/2 ÀÇ ¹öÆÛ¸¦ °¡Áö°í ÀÖÀ» ¶§ ¹ö¸®´Â °Í¿¡ ºñÇØ ±â²¯ÇØ¾ß µÎ ¹è¿¡ ÇØ´çµÇ´Â ÆäÀÌÁö¸¦ Â÷³» ¹ö¸± °ÍÀÌ´Ù. ÀÌ ÀÛ¾÷Àº ±× ÀÚü¸¸À¸·Îµµ Áß¿äÇÒ »Ó ¾Æ´Ï¶ó, ½ºÄÉÁÙ¸µÀ̳ª ÀÚ¿ø ºÐ¹è ¹× °ü·ÃµÈ ¹®Á¦µé¿¡ ´ëÇÑ ¿Â¶óÀÎ ¾Ë°í¸®ÁòÀ» ÇÕ¸®ÀûÀÎ ±âÁØÀ¸·Î Æò°¡ÇÑ´Ù.

¿µ¼ÓÀû ÀÚ·á ±¸Á¶

80 ³â´ë ÃÊ º§ ¿¬±¸¼Ò¿¡ ÀûÀ» µÎ°í ÀÖ´Â µ¿¾È ŸÀÜÀº ´º¿å ´ëÇÐ (NYU) ¿¡¼­ Á¶±³¼ö·Î ÇлýµéÀ» °¡¸£ÃÆ´Ù. ±×´Â NYU ÀÇ ´ëÇпø»ý ´Ò »ç³ªÅ© (Neil Sarnak) ¿Í Ä«³×±â ¸á·±ÀÇ Çлý Áö¹Ì µå¸®½ºÄÝ (Jimmy Driscoll) À» µ¥¸®°í ¿À·§µ¿¾È Áö¼ÓµÇ´Â ÀÚ·á ±¸Á¶µéÀ» °ËÅäÇϱ⠽ÃÀÛÇß´Ù.

¹®Á¦´Â ÀÌÀüÀÇ ¹öÀüµéµµ ÃÖ±ÙÀÇ ¹öÀü¸¸Å­ Á¦´ë·Î ÃßÀûÇÒ ¼ö ÀÖ´Â ÀÚ·á ±¸Á¶¸¦ ¸¸µå´Â °ÍÀ̾ú½À´Ï´Ù. ¶ÇÇÑ, Àüü ÀÚ·á ±¸Á¶¸¦ º¹»çÇÏÁö ¾ÊÀ¸¸é¼­ ±× ÀÏÀ» È¿À²ÀûÀ¸·Î Çس»´Â °Íµµ °ü°ÇÀ̾úÁö¿ä.

'ÀÚ·á ±¸Á¶ (data structure)' ¶õ ÀÚ·á¿¡ º¸´Ù »¡¸® Á¢±ÙÇÒ ¼ö ÀÖµµ·Ï ÄÄÇ»ÅÍÀÇ ¸Þ¸ð¸®¿¡ ÀúÀåÇØ ³õÀº ±×·¡ÇÁ ±¸Á¶¸¦ ¸»ÇÑ´Ù. ÀϹÝÀûÀ¸·Î ÀÚ·á ±¸Á¶´Â Æ®¸®ÀÇ ÇüŸ¦ Áö³à, ÇÁ·Î±×·¥µéÀÌ ÇÊ¿äÇÑ ÀÚ·á¿¡ »¡¸® À̸£µµ·Ï ÇØ ÁØ´Ù. ¿¹¸¦ µé¾î, µ¥ÀÌÅÍ º£À̽º ½Ã½ºÅÛ¿¡¼­ °¡Àå ³Î¸® »ç¿ëµÇ´Â ÀÚ·á ±¸Á¶ÀÎ B-Æ®¸®´Â µ¶ÀÏÀÇ ÄÄÇ»ÅÍ °úÇÐÀÚ ·çµ¹ÇÁ ¹ÙÀÌ¿¡¸£ (Rudolf Bayer) ¿Í ¹Ì±¹ÀÇ ¸ÆÅ©¶óÀÌÆ® (E. M. McCreight) °¡ 970 ³â´ë Àü¹Ý º¸À×»ç ±Ù¹« ½ÃÀý¿¡ °í¾ÈÇØ ³½ °ÍÀ¸·Î¼­, 0.01 ÃÊ ¹Ì¸¸ÀÇ ½Ã°£ ³»¿¡ 1 õ¾ï °¡ÁöÀÇ »ç½Çµé Áß¿¡¼­ ¿ä±¸µÇ´Â »ç½ÇÀ» ã¾Æ³¾ ¼ö°¡ ÀÖ´Ù. ÀÌ°ÍÀº °¢°¢ÀÇ »ç½Çµé Áß¿¡¼­ ¿ä±¸µÇ´Â »ç½ÇÀ» ã¾Æ³¾ ¼ö°¡ ÀÖ´Ù. ÀÌ°ÍÀº °¢°¢ÀÇ »ç½ÇÀ» ÇÑ ¹ø¿¡ Çϳª¾¿ °Ë»öÇØ¾ß ÇÏ´Â °æ¿ì¿Í ºñ±³ÇÒ ¶§ ´ë·« 1 ¸¸ ¹è °¡·® ºü¸¥ ¼ÓµµÀÌ´Ù. ŸÀÜ°ú ±×ÀÇ µ¿·áµéÀº ÀڽŵéÀÌ °³¹ßÇÑ Àå±âÀûÀÎ ÀÚ·á ±¸Á¶¸¦ '¿µ¼ÓÀû ÀÚ·á ±¸Á¶ (persistent data structure)' ¶ó À̸§ºÙ¿´´Ù. ¿µ¼ÓÀû ÀÚ·á ±¸Á¶µéÀº °ÅÀÇ ÇöÀçÀÇ ÀÚ·á¿¡ ´ëÇÑ Á¤±ÔÀûÀÎ ÀÚ·á ±¸Á¶µé ¸¸Å­À̳ª ¼Óµµ°¡ ºü¸£´Ù. »Ó¸¸ ¾Æ´Ï¶ó, ÀÌ ±¸Á¶´Â ÇÁ·Î±×·¥µéÀÌ (±×¸®°í, µû¶ó¼­ »ç¿ëÀڵ鵵) °ÅÀÇ Ãß°¡ ºñ¿ëÀ» µéÀÌÁö ¾ÊÀ¸¸é¼­ °ú°ÅÀÇ ÀÚ·á »óÅ¿¡±îÁö Á¢±ÙÇÒ ¼ö ÀÖµµ·Ï ¸¸µé¾î ÁØ´Ù.

±×¸² 6  Å¸ÀÜ°ú »ç³ªÅ©ÀÇ ¿µ¼ÓÀû ÀÚ·á ±¸Á¶

±×¸² 6 Àº ŸÀÜ°ú »ç³ªÅ©°¡ Á¦½ÃÇÑ ¿µ¼ÓÀû ÀÚ·á ±¸Á¶ÀÇ ÇÑ ¿¹¸¦ º¸¿© ÁØ´Ù. ±×¸²¿¡¼­ ³ëµå X ·Î Ç¥½ÃµÈ ÀڷḦ °»½ÅÇØ¾ß ÇÒ °æ¿ì, ±× °»½ÅÀ» ¼öÇàÇÏ´Â °¡Àå È¿À²ÀûÀÎ ¹æ¹ýÀº X ¸¦ »õ·Î¿î °ª X' ·Î ´ëüÇÏ´Â °ÍÀÌ´Ù. ±× Á¢±Ù ¹æ½ÄÀÇ ¹®Á¦´Â ´õ ÀÌ»ó ½Ã°£ 1 ¿¡¼­ÀÇ µ¥ÀÌÅÍ º£À̽º »óŸ¦ ÀçÇö (recall) ÇÏ´Â °ÍÀÌ ºÒ°¡´ÉÇÏ´Ù´Â Á¡ÀÌ´Ù. ŸÀÜ-»ç³ªÅ© ¹æ¹ýÀ» »ç¿ëÇϸé ÇÁ·Î±×·¥ÀÌ ½Ã°£ 1 ÀÇ ·çÆ®¿¡¼­ ½ÃÀÛÇÏ¿© ½Ã°£ 1 ¿¡¼­ÀÇ »óŸ¦ ¾ò°í, ½Ã°£ 2 ÀÇ ·çÆ®¿¡¼­ ½ÃÀÛÇÏ¿© ½Ã°£ 2 ¿¡¼­ÀÇ »óŸ¦ ȹµæÇÒ ¼ö ÀÖ´Ù.

´ëºÎºÐÀÇ ÀÚ·á°¡ ½Ã°£ 1 °ú ½Ã°£ 2 »çÀÌ¿¡¼­ º¯°æµÇÁö ¾Ê¾Ò±â ¶§¹®¿¡, ½Ã°£ 2 ÀÇ ÀÚ·á ±¸Á¶´Â ±× Â÷À̸¸ Àû¿ë½ÃŲ´Ù. Áï, X ¸¦ X' ·Î ´ëüÇϸ鼭 ±â·ÏÀ» ÀÒ¾î ¹ö¸®´Â ´ë½Å, ÇÁ·Î±×·¥ÀÌ X' ¸¦ ¼ö¿ëÇÒ »õ·Î¿î ³ëµå¸¦ ¸¸µé°í À̾ X' ÀÇ ¸ðµç Á¶»óµé¿¡ ´ëÇؼ­µµ »õ·Î¿î ³ëµå¸¦ ±¸¼ºÇÏ´Â °ÍÀÌ´Ù. ´ëºÎºÐÀÇ ±¸Á¶¿¡¼­´Â ÀÌ ¹æ¹ýÀ» »ç¿ëÇÑ´Ù°í Çؼ­ X ÀÇ À§Ä¡¸¦ ã¾Æ X' ·Î ´ëüÇÏ´Â ¹æ¹ý¿¡ ºñÇØ ÈξÀ ¸¹Àº ÀÛ¾÷ÀÌ ¿ä±¸µÇÁö´Â ¾Ê´Â´Ù.

ÀÌ·¯ÇÑ ¾ÆÀ̵ð¾î´Â °è»ê ±âÇÏÇаú º´·Ä ÇÁ·Î¼¼½Ì ºÐ¾ß¿¡¼­ ÀÀ¿ëµÇ¾î ¿ÔÁö¸¸, ±×°ÍÀÇ ÁÖ¿äÇÑ Àå±â (long-term) ÀÀ¿ë ÇÁ·Î±×·¥Àº ¼ÒÀ§ 'ÀÌ·Â µ¥ÀÌÅÍ º£À̽º (temporal database)' ¶ó ºÎ¸£´Â °ÍÀÌ´Ù. ±×°ÍÀº °ú°ÅÀÇ ½º³À¼ôµéÀ» ºü¸£°í È¿À²ÀûÀ¸·Î Àç»ýÇϱâ À§ÇØ °í¾ÈµÈ µ¥ÀÌÅÍ º£À̽ºµéÀÌ´Ù.

¿¬±¸ È°µ¿¿¡¼­ÀÇ ÆÐÅÏ

ŸÀÜÀº ÀÚ½ÅÀÌ ¼±ÅÃÇØ ¿Â ¼ö¸¹Àº ¾Ë°í¸®ÁòÀÇ ¹®Á¦¿¡¼­ ¾î¶² ÆÐÅÏÀ» º»´Ù.

½Î¿òÀÇ Àý¹ÝÀº ÇعýÀ» Á¦½ÃÇÏ´Â °úÁ¤ÀÌ ¾Æ´Ï¶ó ¹®Á¦¸¦ ¼±ÅÃÇÏ´Â °úÁ¤¿¡¼­ ÀÌ·ç¾îÁý´Ï´Ù. ´ç½ÅÀÌ ¸¸ÀÏ ÀûÀýÇÑ ¹®Á¦¸¦ ¾ò°í ÀûÀýÇÑ Áú¹®À» ÇÑ´Ù¸é ±× Çعý¿¡ À̸£´Â ±ä ¿©Á¤¿¡ µé¾î ¼± °ÍÀÌÁö¿ä.

ÀÀ¿ë ºÐ¾ßµé °¡¿îµ¥¿¡¼­ ºÎ»óÇÏ´Â ¹®Á¦µéÀ» ãÀ¸½Ê½Ã¿À. ¿©±â¼­ À§ÇèÇÑ °ÍÀº ÀÚü ÁÖÀÔ½Ä (self-feeding) ÀÌ µÇ¾î ¹ö¸®´Â ÀÌ·ÐÀÇ ¾î¶² ¾ÆÁÖ ÀÛÀº °¡Áö¿¡ ¸Å´Þ·Á ½ÇÁ¦ ¼¼°è¿¡ ±â¹ÝÀ» µÎÁö ¾Ê´Â °ÍÀÔ´Ï´Ù. ³­ Ç×»ó ¾î´À Á¤µµ ½ÇÁ¦ÀûÀÎ Á߿伺À» °¡Áö´Â ¹®Á¦µé, Áï ½Ç¿ëÀûÀ¸·Î »ç¿ëµÇ´Â ¾Ë°í¸®ÁòÀ» ¾òÀ» ¼ö ÀÖÀ¸¸®¶ó°í »ý°¢µÇ´Â ¹®Á¦µéÀ» ¿¬±¸ÇÏ·Á°í ³ë·ÂÇÏ¿´½À´Ï´Ù.

(ÇÑÆí), ¾î¶² °í¸³µÈ ¿µ¿ª¿¡¼­ »ý¼ºµÈ ¾î¶² ¾ÆÀ̵ð¾î°¡ ¹«¾ð°¡ ´Ù¸¥ °Í¿¡ ¿¬°üµÈ °ÍÀ¸·Î ÆǸíµÇ´Â ½Ã±â¸¦ ¾Ë ¼ö´Â ¾ø½À´Ï´Ù. ¼öÇаú ÀÌ·ÐÀû ÄÄÇ»ÅÍ °úÇÐÀÇ ¸¶¼úÀº ¸ðµç ¿¹ÃøµÇÁö ¾Ê´Â ¿¬°á °ü°èµéÀÔ´Ï´Ù. ¿©·¯ºÐÀº ÀϹÝÀûÀÎ ¿øÄ¢µéÀ» ã±â ½ÃÀÛÇÏ¸é ºÒ°¡»çÀÇÇÑ ¿¬°á °ü°èµéÀÌ ³ªÅ¸³³´Ï´Ù. ´©±¸µµ ±× ¿øÀÎÀ» ¸»ÇÒ ¼ö ÀÖ´Â »ç¶÷Àº ¾øÁö¿ä.

ŸÀÜÀº ÀÚ½ÅÀÇ ¼º°ø¿¡ ´ëÇÑ »çȸÀû ÆÐÅϵµ ÀÌÇØÇÏ°í ÀÖ´Ù.

»óÈ£ ÀÛ¿ëÀº ¸Å¿ì Áß¿äÇϸç Çù·ÂÀÇ Á¤½ÅÀ» °¡Áö°í ÀÖ½À´Ï´Ù. ±³¼ö°¡ µÊÀ¸·Î½á ¾ò¾îÁö´Â °¡Àå Å« ±â»Ý °¡¿îµ¥ Çϳª´Â ´ëÇпø»ýµéÀ» °®°Ô µÈ´Ù´Â °ÍÀÔ´Ï´Ù. ¿¬±¸¸¦ ½ÇÇàÇÏ´Â µ¥ ÀÖ¾î ¾öû³­ È°µ¿·ÂÀ» È®º¸ÇÒ ¼ö ÀÖÀ» »Ó ¾Æ´Ï¶ó, ½Å¼±ÇÏ°í °³¹æÀûÀÎ »ç°í¿Í ¹è¿ò¿¡ ´ëÇÑ ¿­ÀǸ¦ °¡Áø »ç¶÷µé°ú ÇÔ²² Çϸ鼭 ¾ÆÁÖ Å« µ¿±â ºÎ¿©¸¦ ¹ÞÀ» ¼öµµ Àֱ⠶§¹®ÀÔ´Ï´Ù.

ÇÏÁö¸¸ °á±¹ ¿¬±¸´Â °ÅÀÇ°¡ °³ÀÎÀûÀÎ ³ë·ÂÀÌ´Ù. ŸÀÜÀÇ °æ¿ì¶ó Çصµ ÁøÀü¾øÀÌ ¸¹Àº ³¯µéÀ» ÇãºñÇØ ¹ö¸± ¼ö ÀÖ´Ù.

¼º°øÀ» À§ÇØ ÇÊ¿äÇÑ °ÍÀº ¹«¾ùÀϱî¿ä? ¹°·Ð µÎ³ú°¡ ÀÖ¾î¾ß ÇÏ°ÚÁö¸¸, ²ö±âµµ ÇÊ¿äÇÕ´Ï´Ù. ¾î¶² Çعý¿¡ ´ëÇØ ¼ö¸¹Àº ½Ãµµ°¡ ½ÇÆзΠ³¡³ª ¹ö¸± ¼ö ÀÖÁö¸¸, ±×·¯´Ù°¡ ¸¶Áö¸· ½Ãµµ¿¡¼­ ¾î¶² ¸¶¼ú °°Àº ÀÏÀÌ ÀϾ ¼ö Àֱ⠶§¹®ÀÔ´Ï´Ù.