°ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹Ö
Value-Oriented Programming

À̱¤±Ù
ÇÁ·Î±×·¥ ºÐ¼®½Ã½ºÅÛ ¿¬±¸´Ü
KAIST

[¸¶ÀÌÅ©·Î ¼ÒÇÁÆ®¿þ¾î], 2002³â 6¿ùÈ£
[nML°ú ÇÔ²²ÇÏ´Â ÇÁ·Î±×·¡¹Ö ¿©Çà, Á¦1Æí]

[PDF/Postscript]


"value-oriented programming"Àº Andrew Appel ÀÌ 1994³â¿¡ Bell Lab¿¡¼­ ÁøÇàÇÑ ¼¼¹Ì³ª¿¡¼­ óÀ½À¸·Î »ç¿ëÇÏ¿´°í, ±× ÈÄ ``object-oriented programming''°ú ´ëºñµÇ¼­ ³Î¸® Åë¿ëµÇ´Â ¿ë¾îÀÌ´Ù.

ÇÁ·Î±×·¡¹ÖÀ» Áö¹èÇÏ´Â ÇÁ·Î±×·¡¹Ö ¾ð¾î

»ý°¢ÀÌ ¹Ù²î¸é ¾î·Á¿ü´ø ¹®Á¦°¡ ½±°Ô Ç®¸°´Ù. ¹®Á¦¸¦ ¹Ù¶óº¸´Â ½Ã°¢ÀÌ Á¶Á¤µÇ´Â ¼ø°£¿¡, ¿¹Àü¿¡ ¾î·Æ°Ô º¸¿´´ø ¹®Á¦°¡ ½±°Ô Ç®¸®´Â °ÍÀÌ´Ù.
  • [¹®Á¦ ¿¹1] 50ų·Î¹ÌÅÍ ¶³¾îÁ® ÀÖ´Â ÀÚÀü°Å µÎ´ë°¡ ¸¶ÁÖº¸¸ç ½Ã¼Ó 25ų·Î·Î ´Þ¸®±â ½ÃÀÛÇß´Ù. ¸¶ÁÖ´Þ¸®´Â µÎ´ëÀÇ ÀÚ°Ç°Å »çÀ̸¦ ºÎÁö·±È÷ ¿Õº¹ÇÏ´Â Æĸ®°¡ ÀÖ´Ù. Æĸ®´Â ½Ã¼Ó 50ų·Î·Î ºñÇàÇÑ´Ù. ÀÚÀü°Å°¡ ºÎµóÈú ¶§ ±îÁö, Æĸ®°¡ ºñÇàÇÑ °Å¸®´Â?
    • [ö¼öÀÇ ´ä] ö¼ö´Â ¼ö¿­°ú ±ØÇÑ, ¹ÌºÐ°ú ÀûºÐÀ» ÀÌ¿ëÇÑ´Ù. µû¶ó¼­ À§ÀÇ ¹®Á¦´Â, ÀÚÀü°Å »çÀÌÀÇ ÆøÀÇ º¯È­, ±× º¯È­ÇÏ´Â ÆøÀ» ¿Õº¹ÇÏ´Â Æĸ®ÀÇ ºñÇà°Å¸®¸¦ ³ªÅ¸³»´Â ¹«ÇÑ ¼ö¿­ÀÇ ÇÕÀ¸·Î ÇØ°áÇÑ´Ù. ¼ö¿­°ú ±ØÇÑ, ¹ÌºÐ°ú ÀûºÐÀÌ Ã¶¼ö°¡ °¡Áø ÇÁ·Î±×·¡¹Ö ¾ð¾îÀÎ °ÍÀÌ´Ù.
    • [¼øÀÌÀÇ ´ä] ¼øÀÌ°¡ °¡Áø ÇÁ·Î±×·¡¹Ö ¾ð¾î´Â ´Ù¸£´Ù. ö¼ö °°ÀÌ °Å¸®¸¦ ±¸Ã¼ÀûÀ¸·Î ±Ã¸®ÇÏ´Â ¾ð¾î¸¦ »ç¿ëÇÏÁö ¾Ê´Â´Ù. ¼øÀÌÀÇ ÇÁ·Î±×·¥Àº »õ·Î¿î °¢µµ¿¡¼­ °£´ÜÈ÷ °í¾ÈµÈ´Ù: Æĸ®°¡ ºñÇàÇÏ´Â °Å¸®ÀÇ º¯È­¶ó´Â º¹ÀâÇÑ °úÁ¤¿¡¼­ ´«À» ¶¼¼­, Æĸ®°¡ ºñÇàÇÑ ÃÑ ½Ã°£À» °è»êÇÑ´Ù. ±× ½Ã°£Àº ÀÚÀü°Å Ãæµ¹¶§±îÁöÀÇ ½Ã°£°ú °°´Ù. ±× ½Ã°£Àº 1½Ã°£ÀÌ°í, µû¶ó¼­ Æĸ®ÀÇ ÃÑ ºñÇà°Å¸®´Â 50ų·Î¹ÌÅÍÀÌ´Ù. ¼øÀÌ´Â ¹®Á¦¸¦ ÇØ°áÇÏ´Â µ¥ ÇÊ¿äÇÑ ¸¸Å­ÀÇ »óÀ§ÀÇ ¼öÁØ¿¡¼­ »óȲÀ» Á¤ÀÇÇÏ°í ÇØ°áÇÏ´Â ¾ð¾î¸¦ ±¸»çÇÏ´Â °ÍÀÌ´Ù.
  • [¹®Á¦ ¿¹2] À°°¢Çü Á¤¼ö´Â 1, 7, 19, 37, 61, 91, 127 µîÀε¥, Á¤À°°¢Çü ¸ð¾çÀÌ µÇµµ·Ï ¹ÙµÏÆÇ À§¿¡ ³õ¾Æ¾ß ÇÒ ¹ÙµÏ¾ËµéÀÇ °¹¼öµéÀÌ´Ù(±×¸² 1). ÀÌ·¯ÇÑ À°°¢Çü Á¤¼öµéÀ» óÀ½ºÎÅÍ ÇÕÇØ°¡¸é Ç×»ó ¾î´ÀÁ¤¼öÀÇ 3½ÂÀÌ µÈ´Ù°í ÇÑ´Ù. »ç½ÇÀΰ¡?


    ±×¸² 1. À°°¢Çü¼ö

     

    • [ö¼öÀÇ ´ä] ö¼ö°¡ ±¸»çÇÏ´Â ¾ð¾î´Â n¹ø° À°°¢Çü Á¤¼ö¸¦ Á¤ÀÇÇÏ´Â ½ÄÀ» µµÃâÇÏ°í, ±× ½ÄµéÀ» 1¹ø°ºÎÅÍ n¹ø°±îÁö ´õÇؼ­ ¸¸µé¾î³»´Â Á¤¼ö°¡ Ç×»ó ¾î¶² ¼öÀÇ 3½ÂÀÌ µÈ´Ù´Â °ÍÀ» Áõ¸íÇÑ´Ù. Áõ¸íÀº ¹°·Ð ±Í³³¹ýÀÌ´Ù. Á¡È­½Ä ¼ö¿­°ú ±× ÇÕ, ±×¸®°í ±Í³³¹ýÀÌ Ã¶¼ö°¡ °¡Áø ÇÁ·Î±×·¡¹Ö ¾ð¾îÀÎ °ÍÀÌ´Ù.
    • [¼øÀÌÀÇ ´ä] ¼øÀÌ´Â À̹ø¿¡µµ ö¼öº¸´Ù »óÀ§ÀÇ ¼öÁØ¿¡¼­ ´äÀ» ¸¸µå´Â ¾ð¾î¸¦ ±¸»çÇÑ´Ù. ¼øÀÌ´Â À°°¢Çü Á¤¼öµéÀÇ ±×¸²Àº Á¤À°¸éüÀÇ ÇѲ¨Ç®¿¡ ÇØ´çÇÏ°í, ±× ÇѲ¨Ç®µéÀÌ Â÷°îÂ÷°î ½×À̸é Ç×»ó ²Ë Âù Á¤À°¸éü¸¦ ¸¸µç´Ù´Â °ÍÀ» º¸ÀδÙ(±×¸² 2). µû¶ó¼­, À°°¢Çü Á¤¼öµéÀ» Â÷·Ê´ë·Î ÇÕÇϸé, Á¤È®ÇÏ°Ô ¾î¶² Á¤À°¸éü¸¦ ²Ëä¿ì´Â ¾Ë°»À̵éÀÇ °¹¼ö°¡(Áï, ¾î¶²¼öÀÇ 3½ÂÀÌ) µÇ´Â °ÍÀÌ´Ù. 2Â÷¿ø°ú 3Â÷¿øÀÇ µµÇüÀÌ ¼øÀÌ°¡ »ç¿ëÇÑ ÇÁ·Î±×·¡¹Ö ¾ð¾îÀÎ °ÍÀÌ´Ù.

       

      ±×¸² 2. À°°¢Çü¼ö´Â Á¤À°¸éüÀÇ ÇѲ¨Ç®. À§ ±×¸²°ú °°ÀÌ 3¸éüÀÇ ÇÑ ²¨Ç®¾¿À» ½×¾Æ°¡¸é ²ËÂù Á¤À°¸éü¸¦ ¸¸µé ¼ö Àִµ¥, °¢°¢ÀÇ 3¸éü¸¦ ¿À¸¥ÂÊ Áß¾ÓÀÇ ²ÀÁöÁ¡À» Áß½ÉÀ¸·Î º¸¸é ¹Ù·Î À°°¢Çü¼ö(¿À¸¥ÂÊ ¾Æ·¡) ÀÌ´Ù. ÂüÁ¶: What is Intelligence?, Jean Khalfa (ed.), Cambridge University Press, 1994

ÀÌ·¸µíÀÌ, ¹®Á¦¸¦ Á¤ÀÇÇÏ°í ´äÀ» ±Ã¸®ÇÏ´Â »ý°¢ÀÇ Æ²À» ÀûÀýÈ÷ ¼±ÅÃÇÒ ÇÊ¿ä°¡ ÀÖ´Ù. ±×·¯¸é, ¸¸µé¾îÁö´Â ÇØ´äÀº ÀÛ°í °£´ÜÇØÁö°í ÀÌÇØÇϱ⠽¬¿öÁö±â ¶§¹®ÀÌ´Ù. ±×·¸´Ù¸é, ÄÄÇ»ÅÍ ÇÁ·Î±×·¡¹ÖÀÇ ¼¼°è¿¡¼­ ¹®Á¦¸¦ Á¤ÀÇÇÏ°í ´äÀ» ±Ã¸®ÇÏ´Â »ý°¢ÀÇ Æ²Àº ¹«¾ùÀ¸·Î °áÁ¤µÉ±î? ´Ù¸¥ ¸¹Àº °ÍµéÀÌ ÀÖ°ÚÁö¸¸, Å©°Ô ¿µÇâÀ» ¹ÌÄ¡´Â °ÍÀÌ ÇÁ·Î±×·¡¹Ö ¾ð¾îÀÏ °ÍÀÌ´Ù.

À̹ø [nML°ú ÇÔ²²ÇÏ´Â ÇÁ·Î±×·¡¹Ö ¿©Çà] ½Ã¸®Áî¿¡¼­´Â ÇÁ·Î±×·¡¸ÓÀÇ »ý°¢ÀÇ Æ²À» ´Ù¾çÇÏ°Ô ÇØ ÁÖ´Â ÇÁ·Î±×·¡¹Ö ¾ð¾î·Î nMLÀ̶õ °ÍÀ» ¼Ò°³ÇÏ·Á°íÇÑ´Ù. À̹ø ù ±â»ç¿¡¼­´Â nMLÀÌ ¾È³»ÇÏ´Â »ý°¢ÀÇ Æ²Àº ¾î¶² °ÍÀÎÁö¸¦ ¿ì¼± »ìÆ캸µµ·Ï ÇÑ´Ù. Á¦¸ñ¿¡¼­ ´«Ä¡Ã«°ÚÁö¸¸, ±×°ÍÀº °ªÁß½ÉÀ¸·Î »ý°¢ÇϱâÀÌ´Ù(value-oriented programming).

°ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹Ö

¾Æ·¡ÀÇ ÇÁ·Î±×·¥À» »ý°¢ÇØ º¸ÀÚ.

                a := 1;

                b := 2;

                c := a + b;

                d := a + b;

À§ÀÇ ÇÁ·Î±×·¥ÀÌ ½ÇÇàµÇ¾ú´Ù°í ÇÏ°í, ¸î°¡Áö Áú¹®À» ´øÁ®º¸ÀÚ.

  • c ÀÇ 3 ÀÌ d ÀÇ 3 Àΰ¡?
  • a ¸¦ ¹Ù²Ù¸é c µµ ¹Ù²ð±î?
  • d ¸¦ ¹Ù²Ù¸é c µµ ¹Ù²ð±î?
  • e := c ¸¦ ¼öÇàÇÏ·Á¸é c ¸¦ º¹»çÇØ¾ß Çϴ°¡?
  • c °®°í ÀÏ ºÃÀ¸¸é, ±× 3 À» ¾ø¾Öµµ µÇ´Â°¡?
  ÀÌ·¯ÇÑ Áú¹®µéÀº ½Ì°Ì±â ±×Áö¾ø´Ù. ´äÇϱ⠽¬¿î ÀÌÀ¯´Â À§ÀÇ ÇÁ·Î±×·¥¿¡¼­ ´Ù·ç´Â °ªÀÌ °£´ÜÇÑ °Í(Á¤¼ö)À̱⠶§¹®ÀÌ´Ù. c ÀÇ 3 Àº d ÀÇ 3°ú °°´Ù. ÇÁ·Î±×·¥ ¼öÇàÈÄ¿¡ a ¸¦ ¹Ù²Û´Ù°í Çؼ­ c°¡ ¹Ù²îÁö´Â ¾Ê´Â´Ù. c´Â 3À̶ó´Â °ªÀ» °è¼Ó °¡Áö°í ÀְԵȴÙ. ¸¶Âù°¡Áö·Î d¸¦ ¹Ù²Û´Ù°í Çؼ­ c°¡ °¡Áø °ª 3ÀÌ ¹Ù²îÁö´Â ¾Ê´Â´Ù. e := c¸¦ ¼öÇàÇϸé 3À̶ó´Â cÀÇ °ªÀÌ e¿¡ ÀúÀåµÈ´Ù. c °®°í ÀÏ ºÃÀ¸¸é, c°¡ °¡Áø °ª 3Àº Áö¿ö¹ö·Áµµ µÈ´Ù.

ÀÌÁ¦, Á¤¼öº¸´Ù´Â º¹ÀâÇÑ(ÄÄÇ»ÅÍ¿¡ ±¸ÇöÇÏ·ÁÇÒ ¶§ ÇÒ ÀÏÀÌ ¸¹Àº) °ªÀ» ´Ù·ç´Â ÇÁ·Î±×·¥¿¡ ´ëÇؼ­ ºñ½ÁÇÑ Áú¹®À» Çغ¸ÀÚ. ÁýÇÕÀ» ´Ù·ç´Â ÇÁ·Î±×·¥À» »ý°¢ÇÏÀÚ. ¾Æ·¡ ÇÁ·Î±×·¥¿¡¼­, set(1,2,3)Àº 1,2,3À¸·Î ±¸¼ºµÈ ÁýÇÕÀ» ¸¸µé°í, setUnion(x,y)´Â ÁýÇÕ x¿Í yÀÇ ÇÕÁýÇÕÀ» ¸¸µç´Ù.

                a := set(1,2,3);

                b := set(4,5,6);

                c := setUnion(a,b);

                d := setUnion(a,b);

À§ÀÇ ÇÁ·Î±×·¥ÀÌ ½ÇÇàµÈ ÈÄ, ÀÌÀü°ú °°Àº Áú¹®À» ÇØ º¸ÀÚ.

  • À§ÀÇ ÇÁ·Î±×·¥¿¡¼­ cÀÇ ÁýÇÕÀÌ dÀÇ ÁýÇÕ°ú °°Àº°¡?
  • aÀÇ ÁýÇÕÀ» ¹Ù²Ù¸é cÀÇ ÁýÇÕµµ ¹Ù²ð±î?
  • dÀÇ ÁýÇÕÀ» ¹Ù²Ù¸é cÀÇ ÁýÇÕµµ ¹Ù²ð±î?
  • e := c ¸¦ ¼öÇàÇÏ·Á¸é c¸¦ º¹»çÇØ¾ß Çϴ°¡?
  • c °®°í ÀÏ ºÃÀ¸¸é, ±× ÁýÇÕÀ» ¾ø¾Öµµ µÇ´Â°¡?
  ÀÌÁ¦ C³ª Java°è¿­ÀÇ ¾ð¾î·Î ÇÁ·Î±×·¡¹Ö ÇÏ´Â µ¥¿¡ Àͼ÷ÇÑ µ¶ÀÚ¶ó¸é ¸Ó¸®°¡ º¹ÀâÇØ Áö±â ½ÃÀÛÇßÀ» °ÍÀÌ´Ù. ¿Ö³ÄÇϸé, À§ÀÇ Áú¹®µé¿¡ ´ëÇÑ ´äµéÀº, ÇÁ·Î±×·¥¿¡¼­ set°ú setUnionÀ» ¾î¶»°Ô ±¸ÇöÇß´À³Ä¿¡ µû¶ó ´Þ¶óÁö±â ¶§¹®ÀÌ´Ù.

  • Ç×»ó °øÀ¯Çϵµ·Ï ±¸ÇöÇÏ´Â °æ¿ì: ÁýÇÕÀ» ¸¸µé ¶§ ¸¶´Ù Áö±Ý±îÁö ÀÖ¾ú´ø ´Ù¸¥ ÁýÇÕÀÇ ¿ø¼Ò¿Í ÃÖ´ëÇÑ °øÀ¯ÇÒ ¼ö ÀÖµµ·Ï ±¸ÇöÇÏ´Â °ÍÀÌ´Ù. À§ÀÇ ÇÁ·Î±×·¥¿¡¼­ ¼¼¹ø° ÁÙÀÇ setUnion(a,b)´Â a¿Í b°¡ ¸Þ¸ð¸®¿¡ °¡Áö°í ÀÖ´Â ÁýÇÕ ±¸Á¶¹°À» °øÀ¯Çϸ鼭 ÇÕÇØÁø ÁýÇÕÀ» ¸¸µå´Â °ÍÀÌ´Ù (±×¸² 3).


    ±×¸² 3. ``Ç×»ó °øÀ¯Çϱâ''¹æ½ÄÀÇ ÁýÇÕ Ç¥Çö

    ÀÌ·¸°Ô µÇ¸é, aÀÇ ÁýÇÕÀ» ¹Ù²Ù¸é ±×°ÍÀ» °øÀ¯ÇÏ´Â cÀÇ ÁýÇÕµµ ¹Ù²î°Ô µÉ °ÍÀÌ´Ù. µû¶ó¼­, À§ÀÇ Áú¹®¿¡ ´ëÇÑ ´äÀº, c¿Í dÀÇ ÁýÇÕÀº °°Àº °ÍÀÌ°í, a³ª dÀÇ ÁýÇÕÀ» ¹Ù²Ù¸é cÀÇ ÁýÇÕÀÌ ¹Ù²î´Â ¿©ÆÄ°¡ »ý±â°í, e := c¸¦ ¼öÇàÇÒ ¶§ cÀÇ ÁýÇÕÀÌ º¹»çµÇ´Â °ÍÀÌ ¾Æ´Ï°í e¿Í °°ÀÌ °øÀ¯ÇÏ°Ô µÈ´Ù. ¸¶Áö¸·À¸·Î c¸¦ °¡Áö°í ÇÒÀÏÀÌ ¸ðµÎ ³¡³µ´Ù°í Çصµ ±× ÁýÇÕÀ» ¾ø¾Ù ¼ö ´Â ¾ø´Ù. a, b, d¿Í °øÀ¯ÇÏ°í Àֱ⠶§¹®ÀÌ´Ù. ÀÌ·¸°Ô Ç×»ó °øÀ¯Çϸ鼭 ¾ôÈ÷°í ¼³Å°µµ·Ï ÁýÇÕµéÀ» ±¸ÇöÇÑ´Ù¸é, ÇÁ·Î±×·¡¸Ó´Â ¸Å¿ì Á¶½É½º·¯¿ö Áø´Ù. ¹º°¡¸¦ º¯°æ½ÃÅ°¸é, ±×°ÍÀ» °øÀ¯ÇÏ´Â ¸ðµç °ÍµéÀÌ º¯°æµÇ´Â ¿©ÆÄ°¡ Àֱ⠶§¹®ÀÌ´Ù. ÀÌ ¹æ½ÄÀº ¸Þ¸ð¸®¸¦ Àû°Ô ¼Ò¸ðÇÏÁö¸¸, ÇÁ·Î±×·¥ ÀÛ¼ºÀÌ ¸Å¿ì ±î´Ù·Î¿ÍÁø´Ù. °è»êÇÑ °ªµéÀÌ, ÇÁ·Î±×·¡¸ÓÀÇ Àǵµ¿Í´Â ´Ù¸£°Ô ´Ù¸¥ °ªÀ¸·Î º¯°æµÇ±â ½±»óÀÌ´Ù. »ý°¢ÇÑ ´ë·Î ½ÇÇàµÇ´Â(¹ö±× ¾ø´Â) ÇÁ·Î±×·¥À» Â¥±â´Â ¸Å¿ì Èûµé¾îÁø´Ù.                                                          
  • Ç×»ó º¹»çÇϸ鼭 ±¸ÇöÇÏ´Â °æ¿ì: °øÀ¯Çϸ鼭 º¹ÀâÇØ Áö´Â »óȲÀ» ¸ð¸éÇϱâ À§Çؼ­, ÀÌÁ¦´Â ±× ¹Ý´ë·Î °£ °æ¿ìÀÌ´Ù. ÁýÇÕÀ» ¸¸µé ¶§ ¸¶´Ù Áö±Ý±îÁö ÀÖ¾ú´ø ´Ù¸¥ ÁýÇÕ°ú´Â ÀüÇô °øÀ¯ÇÏ´Â °ÍÀÌ ¾øµµ·Ï ÇÑ´Ù. set(1,2,3)Àº ÁýÇÕ ¿ø¼Ò 1,2,3À» °¡Áö´Â ±¸Á¶¹°À» Ç×»ó »õ·Ó°Ô ¸¸µç´Ù. setUnion(x,y)´Â µÎ ÁýÇÕµéÀÇ ¿ø¼ÒµéÀ» ¸ðµÎ º¹»çÇؼ­ µÎ ÁýÇÕÀÇ ÇÕÁýÇÕÀ» Ç¥ÇöÇÏ´Â »õ·Î¿î ±¸Á¶¹°À» ¸¸µç´Ù(±×¸² 4.)


    ±×¸² 4. ``Ç×»ó º¹»çÇϱâ''¹æ½ÄÀÇ ÁýÇÕ Ç¥Çö

    ÀÌ·¸°Ô µÇ¸é À§ÀÇ Áú¹®µé¿¡´ëÇÑ ´äÀ» Çϱâ´Â °£ÆíÇØ Áø´Ù. Á¤¼ö°ªÀ» ´Ù·ç´ø ÀÌÀüÀÇ ÇÁ·Î±×·¥°ú °°Àº °æ¿ì°¡ µÇ´Âµ¥, cÀÇ ÁýÇÕÀº dÀÇ ÁýÇÕ°ú °°Àº ÁýÇÕÀÌ°í, a³ª dÀÇ ÁýÇÕÀ» ¹Ù²Û´Ù°í Çصµ cÀÇ ÁýÇÕ°ú´Â ¹«°üÇÏ°Ô µÇ°í, e := c ¸¦ ¼öÇàÇÒ ¶§´Â c¸¦ º¹»çÇؼ­ e°¡ °¡Áö°Ô µÈ´Ù. c ÁýÇÕÀ» °¡Áö°í ÀÏÀ» ¸¶ÃÆÀ¸¸é ±× ÁýÇÕÀ» ¾ø¾Ö¹ö·Áµµ µÈ´Ù. ÀÌ·± ¹æ½ÄÀ¸·Î ±¸ÇöÇϸé, ÇÁ·Î±×·¥À» ÀÛ¼ºÇÏ°í ÀÌÇØÇϱâ´Â ÆíÇØÁø´Ù. ÇÁ·Î±×·¥ÀÌ °è»êÇÏ´Â ¸ðµç °ªµéÀº Ç×»ó °³º°ÀûÀ¸·Î µ¶¸³µÇ¾î Àֱ⠶§¹®¿¡, °ªµéÀÌ ¾ôÈ÷°í ¼³ÄÑÀÖ´Â °ü°è¸¦ ½Å°æ¾²¸é¼­ ÇÁ·Î±×·¥À» ÀÌÇØÇϰųª ÀÛ¼ºÇØ¾ß ÇÏ´Â ºÎ´ãÀÌ ¾ø´Ù. ÇÏÁö¸¸, ¹®Á¦´Â ¸Þ¸ð¸® ¼Ò¸ð¿Í ½Ã°£ÀÌ ¸¹ÀÌ µå´Â °ÍÀÌ´Ù.
  • À§ÀÇ µÎ ¹æ½Ä¿¡¼­ ÁÁÀº °ÍÀ» ÃëÇϱâ: ÃÖ´ëÇÑ °øÀ¯Çϸ鼭 ÇÁ·Î±×·¥ ÀÛ¼ºÀ̳ª ÀÌÇØ°¡ ½±µµ·Ï ÇÏ´Â ¹æ½ÄÀÌ ÀÖ´Ù. ÁýÇÕÀ» ¸¸µé ¶§ ÀÌ¹Ì °è»êµÈ ÁýÇÕµé°ú °øÀ¯ÇÒ ¼ö ÀÖ´Â °ÍÀº ÃÖ´ëÇÑ °øÀ¯ÇÏ°Ô Çϸ鼭, ÀÌ¹Ì °è»êµÈ ÁýÇÕµéÀº º¯°æµÇÁö ¾Êµµ·Ï ÇÏ´Â °ÍÀÌ´Ù. Áï, À§ÀÇ ÇÁ·Î±×·¥ ½ÇÇàÁß¿¡ ¸¸µå´Â ÁýÇÕµéÀº ´ÙÀ½ÀÇ ¼¼°³ÀÌ°í, ÀÌ ¼¼°èÀÇ ÁýÇÕÀº ¾ÕÀ¸·Î Àý´ë º¯ÇÏÁö ¾Ê´Â °ÍÀÌ´Ù: {1, 2, 3}, {4, 5, 6}, {1, 2, 3, 4, 5}. ÀÌ·± ¹æ¾ÈÀ» »óÁ¤ÇÏ°í, ÀÌÀü Áú¹®µé¿¡ ´äÇغ¸ÀÚ. cÀÇ ÁýÇÕÀº dÀÇ ÁýÇÕ°ú °°Àº ÁýÇÕÀΰ¡? ±×·¸´Ù. a³ª dÀÇ ÁýÇÕÀ» ¹Ù²Ù´Â °æ¿ì´Â ¾ø°í, º¯°æµÈ ´Ù¸¥ ÁýÇÕÀ» ¿øÇϸé a³ª dÀÇ ÁýÇÕÀº °Çµå¸®Áö ¾ÊÀ¸¸é¼­, ¿øÇÏ´Â ÁýÇÕÀ» »õ·Ó°Ô ¸¸µç´Ù. ÀÌ ¶§ Áö±Ý±îÁö ¸¸µé¾ú´ø ÁýÇÕµéÀº ¹Ù²î´Â ¹ýÀÌ ¾øÀ¸¹Ç·Î, ÇÊ¿äÇϸé Ç×»ó ÀÖ´ø ÁýÇÕµéÀ» °øÀ¯ÇÒ ¼ö ÀÕ´Ù. e := c ¸¦ ¼öÇàÇÒ ¶§´Â cÀÇ ÁýÇÕÀ» e°¡ °øÀ¯ÇÏ°Ô ÇÑ´Ù. ¸¶Áö¸·À¸·Î, c ÁýÇÕÀ» °¡Áö°í ÀÏÀ» ¸¶ÃÆÁö¸¸ ±× ÁýÇÕÀ» ¾ø¾Ö¹ö¸± ¼ö ´Â ¾ø´Ù. ´Ù¸¥ ÁýÇÕÀÌ ±× ÁýÇÕÀ» °øÀ¯Çϸ鼭 Ç¥ÇöµÉ ¼ö Àֱ⠶§¹®ÀÌ´Ù.
  À§ÀÇ ¸¶Áö¸· °æ¿ì°¡ ``°ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹Ö''ÀÎ °ÍÀÌ´Ù. ƯÈ÷, ±×·¸°Ô ±¸ÇöÇÏ´Â °ÍÀÌ ÀÚµ¿À¸·Î µÇ´Â ÇÁ·Î±×·¡¹Ö ¾ð¾î¸¦ ``°ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹Ö ¾ð¾î''¶ó°í ºÎ¸£ÀÚ.

À̾߱Ⱑ ÇÊ¿äÀÌ»óÀ¸·Î º¹ÀâÇØÁ³´Âµ¥, °ªÁß½É(value-oriented)ÀÇ ÇÁ·Î±×·¡¹Ö ½ºÅ¸ÀÏÀ» ¹°°ÇÁß½É(object-oriented)ÀÇ ½ºÅ¸ÀÏ°ú ´ëºñÇؼ­ ¿ä¾àÇÏ¸é ´ÙÀ½°ú °°´Ù. ¹°°ÇÀº ²÷ÀÓ¾øÀÌ º¯ÇÏÁö¸¸, °ªÀº ÀÏ´Ü ¸¸µé¾î Á³À¸¸é º¯ÇÏÁö ¾Ê´Â´Ù. Á¤¼ö 1Àº º¯ÇÏÁö ¾Ê´Â´Ù. 1ÀÌ ¾î´À³¯ º¯Çؼ­ 1.2°¡ µÇ°Å³ª 99°¡ µÇÁö ¾Ê´Â´Ù. ÁýÇÕ {1,2}´Â º¯ÇÏÁö ¾Ê´Â´Ù. ÀÌ ÁýÇÕÀÌ º¯Çؼ­ {1,2,3}ÀÌ µÈ °ÍÀÌ ¾Æ´Ï°í, ÁýÇÕ {1,2}¿Í {1,2,3}Àº ¼­·Î ´Ù¸¥ ÁýÇÕÀÎ °ÍÀÌ´Ù. 1°ú 1.2°¡ ´Ù¸¥ °ªÀ̵íÀÌ.

¹°°Ç S¸¦ ÁýÇÕ {1,2,3}¶ó°í ÇÏÀÚ. ÀÌ ÁýÇÕ¿¡ ¿ø¼Ò 4¸¦ ´õÇÏ´Â °æ¿ì S.add(4) ¹°°Ç S´Â ÁýÇÕ {1,2,3} À̾ú´Ù°¡ {1,2,3,4} ¶ó´Â »õ·Î¿î ÁýÇÕÀ¸·Î º¯ÇÏ°Ô µÇ´Â °ÍÀÌ´Ù(±×¸² 5).


±×¸² 5. ÁýÇÕÀ̶ó´Â ¹°°ÇÀº º¯ÇÑ´Ù

¹°°ÇÀº ¾î¶² ÀÛ¾÷À» ÅëÇؼ­ Ç×»ó ±× »óÅ°¡ º¯ÇÏ°£´Ù. ¹Ý¸é¿¡, °ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹ÖÀÎ °æ¿ì, ÁýÇÕ S ({1,2,3})¶ó´Â °ª¿¡ ¿ø¼Ò 4¸¦ Ãß°¡ÇÏ´Â °æ¿ì add(S, 4) »õ·Ó°Ô ¸¸µé¾î Áö´Â ÁýÇÕÀº S¶ó´Â ÁýÇÕÀ» º¯È­½ÃÅ°Áö ¾Ê´Â´Ù. ¿ÀÁ÷ ´Ù¸¥ ÁýÇÕ {1,2,3,4}¸¦ ÀǹÌÇÏ´Â °Í »ÓÀÌ´Ù. À̶§, °ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹Ö¿¡¼­´Â °ªÀÌ º¯ÇÏÁö ¾ÊÀ¸¹Ç·Î, Áö±Ý±îÁö °è»êµÈ ÁýÇÕµéÀ» ÃÖ´ëÇÑ °øÀ¯Çϸ鼭 »õ·Î¿î ÁýÇÕÀ» Ç¥ÇöÇÒ ¼ö ÀÖÀ» °ÍÀÌ´Ù (±×¸² 6).


±×¸² 6. ÁýÇÕÀ̶ó´Â °ªÀº º¯ÇÏÁö ¾Ê´Â´Ù

°ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹ÖÀº Ưº°ÇÑ °ÍÀÌ ¾Æ´Ï´Ù

``°ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹Ö'' À̶ó´Â ȣĪÀÌ ¶Ç´Ù¸¥ °³³äÀÇ ÇÁ·Î±×·¡¹Ö ÆĶó´ÙÀÓÀ» ¶æÇϳª º¸´Ù, ¶ó°í ±äÀåÇÒ ÇÊ¿ä´Â ¾ø´Ù. ±×°ÍÀº ¿ì¸® ÇÁ·Î±×·¡¸ÓµéÀÌ ±î¸¶µæÈ÷ ÀØ°í ÀÖ¾ú´ø, ¿¹Àü(Áß°íµîÇб³ ½ÃÀý ÄÄÇ»ÅÍ ÇÁ·Î±×·¡¹ÖÀ» ¹è¿ì±â Àü)¿¡´Â ³Ê¹«µµ Àͼ÷Çß´ø ÇÁ·Î±×·¡¹Ö ½ºÅ¸ÀÏÀ̾ú´Ù.

¿Ö ÀØ°í ÀÖ¾ú´ø °ÍÀϱî? Áö±Ý±îÁö ÀÍÇô ¿Â ÄÄÇ»ÅÍ ÇÁ·Î±×·¡¹ÖÀº ±×°Í°ú ´Þ¸® º¹ÀâÇ߱⠶§¹®ÀÌ´Ù. ¿Ö ´Ù¸£°í º¹ÀâÇß´ø °ÍÀ̾úÀ»±î? ±×°ÍÀº ÀÚ¿¬½º·¯¿î ``°ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹Ö''À» È¿°úÀûÀ¸·Î Áö¿øÇÏ´Â ±â¼úÀÌ ¾ÆÁ÷ ÄÄÇ»ÅÍ¿¡ ¾ø¾ú±â ¶§¹®ÀÌ´Ù. ±×·¡¼­ ÄÄÇ»ÅÍ ÇÁ·Î±×·¡¹ÖÀº º¹ÀâÇÑ ½ºÅ¸ÀÏÀÇ »ý°¢À» °­¿äÇØ¿Ô´ø °ÍÀÌ´Ù.

ÇÏÁö¸¸ ÀÌÁ¦´Â, ``°ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹Ö''±â¼úÀ» °¡´ÉÇÏ°Ô ÇÏ´Â Æ°Æ°ÇÑ ¿¬±¸¼º°úµéÀÌ ²ÙÁØÈ÷ ½×¿©¼­, ±×·¯ÇÑ ÀÚ¿¬½º·¯¿î ÇÁ·Î±×·¡¹ÖÀ» ȸº¹ÇÒ ¼ö ÀÖ°Ô µÇ¾ú´Ù. °ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹ÖÀ» Á¦´ë·Î Áö¿øÇÏ´Â ÇÁ·Î±×·¡¹Ö ¾ð¾î´Â ÀÌ¹Ì Çб³ÀÇ ¿¬±¸½Ç¿¡¼­ ³ª¿Í¼­, »ê¾÷ ÇöÀåÀÇ Áß¿äÇÑ ±¸¼®¿¡¼­ ¸ÍÈ°¾àÀ» ÇØ¿À°í ÀÖ´Ù. ÀÌ ½Ã¸®Áî¿¡¼­ ¼Ò°³ÇÒ nMLÀ̶ó´Â ¾ð¾î´Â ±×·± ·ùÀÇ ¾ð¾îµé¿¡ ´ëÇؼ­ ¿ì¸®°¡ ³»³õÀ» ¼ö ÀÖ´Â ´ëÇ¥¼±¼öÀÌ´Ù. MLÀ̶ó´Â ¾ð¾î°è¿­ÀÇ Çѱ¹ »çÅõ¸®ÂëÀ¸·Î »ý°¢Çصµ ÁÁ´Ù.

´Ù½Ã ÀÌ ¼½¼ÇÀÇ º»·¡ ³íÁö·Î µ¹¾Æ¿Í¼­, »ç½Ç, Áö±Ý±îÁö 300³â ÀÌ»ó µ¿¾È ¼öÇÐÀ̶ó´Â ¾ð¾î°¡ »ç¿ëÇÑ ¼­¼ú ¹æ½ÄÀÌ ¹Ù·Î °ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹ÖÀ̾ú´Ù. ¼öÇп¡¼­ »ç¿ëÇÏ´Â ¸ðµç ¿¬»êÀº °ªÀ» ¸¸µé »ÓÀÌÁö ¸¸µç °ªÀ» ¹Ù²ÙÁö ¾Ê´Â´Ù. »õ·Î¿î °ªÀ» °è»êÇÏ´Â °Í »ÓÀÌ´Ù. ¾î´À ¼öÇÐÃ¥ÀÇ ÇÑ ÆäÀÌÁö¿¡¼­ µû¿Â ´ÙÀ½ÀÇ ´Ü¶ôÀ» º¸ÀÚ:

      ``V¸¦ (interior A) U f(W) ¶ó°í ÇÏÀÚ. ±×·¯¸é V U (interior W) = f(A) °¡ »ç½ÇÀÓÀ» ¾Ë ¼ö ÀÖ´Ù.''

¿©±â¼­ ù ¹®Àå¿¡ ³ªÅ¸³ª´Â interior A°¡ A°¡ °¡Áö´Â °ªÀ» º¯È­½ÃÅ°´Â°¡? ±×·¡¼­ µÎ¹ø° ¹®Àå¿¡ ³ªÅ¸³ª´Â A´Â óÀ½ÀÇ A¿Í ´Ù¸¥°ÍÀÌ´ø°¡? ±×·¸Áö ¾Ê´Ù. A°¡ °¡Áö´Â °ªÀº º¯ÇÏÁö ¾Ê´Â´Ù. interior A´Â A¸¦ °¡Áö°í Á¤ÀǵǴ ¾î¶² »õ·Î¿î °ªÀ» ÁöĪÇÒ »ÓÀÌÁö A¸¦ °ÇµéÁö´Â ¾Ê´Â °ÍÀÌ´Ù. f(W)¶ó´Â ¿¬»êµµ ¸¶Âù°¡Áö´Ù. W°¡ ±× ¿¬»ê¿¡ ÀÇÇؼ­ °ªÀÌ º¯ÇÏ´Â °ÍÀÌ ¾Æ´Ï´Ù. ù¹®Àå¿¡¼­³ª µÎ¹ø° ¹®Àå¿¡¼­³ª W´Â °°Àº °ªÀ» °¡Áú »ÓÀÌ´Ù.

ÀÌ·¯ÇÑ °ªÁß½ÉÀÇ ¼­¼ú¹æ½ÄÀÌ ¼öÇÐ(±×¸®°í ¸ðµç °úÇÐ) ºÐ¾ß¿¡¼­ »ç¶÷µé³¢¸® ¼ÒÅëÇÏ´Â ±âº»ÀûÀÎ ÇÁ·Î±×·¡¹Ö ¾ð¾î·Î À¯±¸ÇÏ°Ô ÀÌ¿ëµÈ ÀÌÀ¯´Â ¹»±î? ±× ÀÌÀ¯´Â, °£´ÜÇÏ°í Æí¸®Çؼ­ÀÌ´Ù. °£´ÜÇϹǷΠÆí¸®ÇÑ °ÍÀε¥, ÀÌ°ÍÀº ¼öÇÐÀ̳ª °úÇÐÀÌ ¼º°øÇÑ Áß¿äÇÑ ÀÎÇÁ¶óÀÌ´Ù. ¼öÇÐÀÇ ÇÁ·Î±×·¥(¼öÇÐÀÇ ³íÁõµé)Àº ±×°ÍÀÌ ¿Ç°í ±×¸¥Áö¸¦ È®ÀÎÇÒ ¼ö ÀÖÀ» ¶§¿¡¸¸ »ý¸íÀÌ ÀÖ´Ù. ¿Ç°í ±×¸¥Áö¸¦ È®ÀÎÇϱâ Æí¸®ÇÏ·Á¸é ¼­¼úÇÏ´Â ¾ð¾î°¡ °£´ÜÇؾ߸¸ ÇÑ´Ù. ±×·¸°Ô °£´ÜÇÏ°Ô ÇÏ´Â µ¥ ±â¿©ÇÑ ¾ð¾îÀÇ ÁÖ¿ä ¼ºÁúÀÌ ¹Ù·Î °ªÁß½ÉÀ¸·Î ÇÁ·Î±×·¥ÇϱâÀÎ °ÍÀÌ´Ù.

±×·¸´Ù¸é, ÄÄÇ»ÅÍ ÇÁ·Î±×·¥À» Â¥´Â ¿ì¸®°¡ ¼öÇÐÀÚµéÀ» µû¶ó°¡¾ß ÇÒ ÀÌÀ¯´Â ¹«¾ùÀΰ¡? ÄÄÇ»ÅÍ ¼ÒÇÁÆ®¿þ¾î´Â ¼öÇÐÀÇ ÇÁ·Î±×·¥¿¡¼­¿Í ¶È°°ÀÌ, ±× Âü/°ÅÁþÀ» ÆǸíÇØ¾ß ÇÏ´Â Çʿ伺ÀÌ ¸í¹éÇØÁö°í Àֱ⠶§¹®ÀÌ´Ù. ¼öÇп¡¼­ ÇÁ·Î±×·¥ÀÇ Âü/°ÅÁþÀ» ÆǸíÇÏ´Â °ÍÀÌ ¼öÇÐÀÇ Á¸Àç¿Í ¹ßÀüÀÇ ±Ù°£À̾úµíÀÌ, ÄÄÇ»ÅÍ ¼ÒÇÁÆ®¿þ¾îÀÇ Á¸Àç¿Í ¹ßÀüÀÇ ±Ù°£Àº ÀÌÁ¦ ÇÁ·Î±×·¥ÀÇ Âü/°ÅÁþÀ» ÆǸíÇÏ´Â ±â¼úÀÌ´Ù. ÇÁ·Î±×·¥ÀÌ ¿Ç°í ±×¸¥Áö¸¦ ÆǸíÇÏ´Â °ÍÀº ´Ù¸§¾Æ´Ï¶ó ÇÁ·Î±×·¥ÀÌ »ý°¢´ë·Î ÀÛµ¿ÇÒ Áö ¾ÈÇÒ Áö ¸¦ È®ÀÎÇÏ´Â °ÍÀÌ´Ù. ÇÁ·Î±×·¥ÀÌ »ý°¢´ë·Î ÀÛµ¿ÇÑ´Ù´Â °ÍÀº, ÇÁ·Î±×·¥ÀÌ ¹ö±×¾øÀÌ ½ÇÇàµÈ´Ù´Â °ÍÀ» ¶æÇÑ´Ù.

ÀÛ¼ºÇÑ ÇÁ·Î±×·¥ÀÌ ¹ö±×¾øÀÌ ½ÇÇàµÉ Áö¸¦ ¹Ì¸® ÀÚµ¿À¸·Î È®ÀÎÇÏ´Â ±â¼ú, ÀÌ ±â¼úÀ» ´Þ¼ºÇÏ´Â ±×·ìÀÌ ¾ÕÀ¸·Î ¼ÒÇÁÆ®¿þ¾î ¹ßÀüÀÇ Çì°Ô¸ð´Ï¸¦ Â÷ÁöÇÏ°Ô µÉ ÅÙµ¥, ÀÌ ±â¼úÀÌ ²ÉÇÇ´Â ¶¥Àº °ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹Ö ¾ð¾î·Î Â¥¿©Áø ÇÁ·Î±×·¥µéÀÌ µÉ °ÍÀÌ´Ù. ¼öÇÐÀÇ Âü/°ÅÁþÀ» È¿°úÀûÀ¸·Î ¼ÒÅë½ÃÄ×´ø ¾ð¾î°¡ °ªÁß½ÉÀÇ ¾ð¾î¿´´Ù´Â »ç½ÇÀÌ ÀÌ ÁÖÀåÀ» ¶°¹ÞÄ¡°í ÀÖ´Ù.

ÇÁ·Î±×·¥ÀÌ ¹ö±×¾øÀÌ ½ÇÇàµÉ Áö¸¦ ¹Ì¸® ÀÚµ¿À¸·Î È®ÀÎÇØ ÁÖ´Â ±â¼úÀÌ ¿Ö Áß¿äÇÏ°í, Áö±Ý±îÁöÀÇ ¿¬±¸¼º°úµéÀÌ ¾îµð±îÁö ¿Í ÀÖ°í, °ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹Ö ¾ð¾î, ƯÈ÷ ÀÌ ½Ã¸®Áî¿¡¼­ ¼Ò°³ÇÒ nMLÀ̶ó´Â ¾ð¾î´Â ÀÌ ¸Æ¶ô¿¡¼­ ¹«½¼ ¿ªÇÒÀ» ÇÏ´ÂÁö¿¡ ´ëÇÑ ÀÚ¼¼ÇÑ ³»¿ëÀº ´ÙÀ½È£¿¡ °èȹµÇ¾î ÀÖÀ¸¹Ç·Î ±×¶§·Î ¹Ì·ç±â·Î ÇÏ°í(°£´ÜÇÑ ±ÛÀº ¿©±â¸¦), ´Ù½Ã ¿ì¸®ÀÇ º»·ÐÀ¸·Î µ¹¾Æ°¡ÀÚ.

°ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹ÖÀº ºñ½ÎÁö ¾Ê´Ù

°ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹ÖÀ» Áö¿øÇÏ·Á´Â µ¥ °ÆÁ¤µÇ´Â ºñ¿ëÀÌ È¤½Ã ÀÖÁö ¾ÊÀ»±î? °ªÁ᫐ ÇÁ·Î±×·¡¹ÖÀÇ ÇÙ½ÉÀº, ¸¸µé¾îÁø °ªÀº º¯ÇÏÁö ¾Ê´Â´Ù, À̹ǷÎ, »õ·Î¿î °ªÀ» ¸¸µé¶§ »õ·Î¿î ¸Þ¸ð¸®¸¦ ¼Ò¸ðÇØ¾ß ÇÏ´Â °Ô ¾Æ´Ò±î? ÀÌ ÃßÃøÀÌ ¸ÂÁö ¾ÊÀº ÀÌÀ¯¸¦ ±¸Ã¼ÀûÀ¸·Î »ìÆ캸¸é¼­ À̹ø ù ȸ¸¦ ¸¶¹«¸® ÇÏÀÚ.

°ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹ÖÀÌ °è»êÀÚ¿øÀÇ ³¶ºñ¸¦ ¿ÀÈ÷·Á ¸·À» ¼ö ÀÖ´Â ÀÌÀ¯´Â, °ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹ÖÀÇ Çٽɿ¡ ÀÖ´Ù. ¸¸µé¾îÁø °ªÀº º¯ÇÏÁö ¾Ê´Â´Ù, ´Â ÇÙ½É ´öÅÿ¡, Ç×»ó ¾È½ÉÇÏ°í ÀÌ¹Ì ÀÖ´Â °ªµéÀ» °øÀ¯ÇÒ ¼ö ÀְԵȴÙ; ``ö¼ö¾ß, 9¹ø ¹ö½º·Î ÅëÇÐÇϴ±¸³ª. ³Ê ÅëÇÐÇϸ鼭 9¹øÀÌ ´Ù¸¥ ³ë¼±À» ¿îÇàÇϵµ·Ï ¹Ù²ÙÁö ¾ÊÀ»°ÅÁö? ³ªµµ ¾Ê¹Ù²ã. ±×·¡, °°ÀÌ 9¹ø ¹ö½º·Î ÅëÇÐÇÒ ¼ö ÀÖ°Ú±¸³ª.'' °ªÀ» ¸¸µå´Â ½Ã°£Àº ¾î¶²°¡? °øÀ¯ÇϹǷΠ°ªÀ» ¹Ýº¹Çؼ­ ´Ù½Ã ¸¸µå´Â ½Ã°£ÀÌ ÁÙ¾îµç´Ù.

±¸Ã¼ÀûÀÎ ÇÁ·Î±×·¥À¸·Î À̾߱âÇØ º¸ÀÚ. ¿¹·Î µé¾ú´ø, Á¤¼öµéÀÇ ÁýÇÕÀ» °è»êÇÏ´Â ÇÁ·Î±×·¥À» »ý°¢ÇØ º¸ÀÚ. Á¤¼öÀÇ ÁýÇÕÀ» ±¸ÇöÇÏ´Â ¹æ¹ýÀ¸·Î ÀÌÁø Ž»ö Æ®¸®(binary search tree)¸¦ ÀÌ¿ëÇÑ´Ù°í ÇÏÀÚ. ÀÌ ¹æ¹ýÀº ÁýÇÕÀÇ ¿ø¼ÒµéÀ» µÎ°¥·¡·Î °¥¶óÁö´Â(binary) °¡Áö±¸Á¶(tree)À§¿¡ Ưº°ÇÑ ¹æ½ÄÀ¸·Î ºÐÆ÷½ÃÄѼ­ ¿ø¼Ò¸¦ ã±â°¡(search) »¡¶óÁöµµ·Ï ÇÏ´Â °ÍÀÌ´Ù. Ưº°ÇÑ ¹æ½ÄÀÇ ºÐÆ÷¶õ, °¥¶óÁö´Â ÁöÁ¡(node)¿¡ ÀÖ´Â ¿ø¼Ò´Â Ç×»ó ±× ¿ÞÆí¿¡ ¸Å´Þ¸° ¸ðµç ¿ø¼Òµéº¸´Ù Å©°Å³ª °°°í ¿À¸¥Æí¿¡ ¸Å´Þ¸° ¿ø¼Òµé º¸´Ù ÀÛ´Ù. ¿¹¸¦µé¾î, ÁýÇÕ {1,2,3,5,6,7}Àº [±×¸² 7]°ú °°ÀÌ Ç¥ÇöµÇ´Â °ÍÀÌ´Ù. ±×·¯ÇÑ Á¶°Ç ´öÅÿ¡ ¾î¶² ¿ø¼Ò¸¦ ã´Âµ¥ µ¥ ÇÊ¿äÇÑ ½Ã°£Àº ¿ø¼ÒµéÀÇ ÃÑ °¹¼ö NÀÌ ¾Æ´Ï¶ó log N(Æ®¸®ÀÇ ²À´ë±â¿¡¼­ ¾Æ·¡·Î¸¸ ³»·Á°¡´Â ÇÑ °³ °æ·ÎÀÇ ±æÀÌ) ¸¸Å­¸¸ ÇÊ¿äÇÏ°Ô µÈ´Ù. »õ·Î¿î ¿ø¼Ò¸¦ ³ÖÀ» ¶§¿¡µµ, ³ÖÀ» À§Ä¡¸¦ ã¾Æ°¡¾ß ÇϹǷΠlog NÀÇ ½Ã°£ÀÌ ÇÊ¿äÇÏ´Ù.


±×¸² 7. ÀÌÁø °Ë»ö Æ®¸®·Î Ç¥ÇöµÈ ÁýÇÕ {1,2,3,5,6,7}

ÀÚ ÀÌÁ¦ µûÁ®º¸µµ·Ï ÇÏÀÚ. »õ·Î¿î ¿ø¼Ò¸¦ Ãß°¡Çؼ­ »õ·Î¿î ÁýÇÕÀ» ¸¸µé¾î ³»´Â °æ¿ì¸¦ µûÁ®º¸ÀÚ. ¿ì¼± ÇÁ·Î±×·¥¿¡¼­ µÎ°¡Áö °æ¿ì°¡ ÀÖÀ» ¼ö ÀÖ°Ú´Ù. »õ·Î¿î ÁýÇÕÀ» ¸¸µé¸é ¿¹Àü ÁýÇÕ°ú »õ·Î¿î ÁýÇÕµéÀ» ¸ðµÎ À¯ÁöÇØ¾ß ÇÏ´Â °æ¿ì¿Í, Ç×»ó »õ·Ó°Ô ¸¸µç ÁýÇÕ¸¸À» »ç¿ëÇÏ°í ¿¹ÀüÀÇ °ÍÀº ¹ö·Áµµ µÇ´Â °æ¿ì.

  • ÇÁ·Î±×·¥¿¡¼­ ¿¹ÀüÀÇ ÁýÇÕ°ú »õ·Î ¸¸µé¾îÁø ÁýÇÕÀ» ¸ðµÎ À¯ÁöÇØ¾ß ÇÏ´Â °æ¿ì: °ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹Ö¿¡¼­´Â ¸¸µé¾îÁø ÁýÇÕÀÌ º¯°æµÇ´Â °æ¿ì´Â ¾øÀ¸¹Ç·Î, Ç×»ó °øÀ¯ÇÒ ¼ö ÀÖ´Â °ÍÀº °øÀ¯ÇÏ°Ô µÈ´Ù. ¿¹¸¦µé¾î À§ÀÇ {1,2,3,5,6,7}¿¡ 10ÀÌ Ã·°¡µÈ ÁýÇÕÀ» ¸¸µå´Â °ÍÀ» »ý°¢Çϸé, »õ·Î¿î ÁýÇÕÀº 3°ú 7¹ø ³ëµå¿¡ ÇØ´çÇÏ´Â °Í¸¸ »õ·Î ¸¸µé°í ³ª¸ÓÁö´Â ¸ðµÎ °øÀ¯Çϸ鼭 »õ·Î¿î ¿ø¼Ò 10À» »õ·Î ¸¸µç ¿ø¼Ò 7ÀÇ ³ëµåÀÇ ¿À¸¥ÂÊ¿¡ ³Ö¾îÁÖ¸é µÈ´Ù (±×¸² 8).


    ±×¸² 8. ÀÌÁø Ž»ö Æ®¸®¿¡ ¿ø¼Ò ³Ö±â: º¯ÇÏÁö ¾Ê´Â °æ¿ì

    µû¶ó¼­ ½Ã°£°ú °ø°£ÀÌ log N¸¸Å­ ¼Ò¸ðµÈ´Ù. ÇÑÆí, ¸¸µé¾îÁø ÁýÇÕÀÌ º¯°æµÉ ¼ö ÀÖ´Â °æ¿ì(°ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹Ö Á¶°ÇÀ» °®ÃßÁö ¸øÇÑ°æ¿ì) °øÀ¯Çؼ­´Â ¾ÊµÈ´Ù. ±×¸®°í, ¿¹Àü ÁýÇÕ°ú »õ·Î¸¸µç ÁýÇÕÀ» ¸ðµÎ °¡Áö°í ÀÖ¾î¾ß ÇϹǷÎ, ¿¹Àü ÁýÇÕÀ» ±×´ë·Î º¹»çÇÏ°í »õ·Î¿î °ÍÀ» Çϳª ÷°¡ÇØ¾ß ÇÑ´Ù (±×¸² 9). µû¶ó¼­ °ªÁß½ÉÀÌ ¾Æ´Ñ °æ¿ì ½Ã°£°ú °ø°£ÀÌ N¸¸Å­ ¼Ò¸ðµÈ´Ù.


    ±×¸² 9. ÀÌÁø Ž»ö Æ®¸®¿¡ ¿ø¼Ò ³Ö±â: º¯ÇÒ ¼ö ÀÖ´Â °æ¿ì

     

  • ÇÁ·Î±×·¥¿¡¼­ ¿¹ÀüÀÇ ÁýÇÕÀº ´õÀÌ»ó »ç¿ëÇÏÁö ¾Ê°í Ç×»ó ÃÖ½ÅÀÇ ÁýÇÕ¸¸ »ç¿ëÇÏ´Â °æ¿ì: ÀÌ°æ¿ì´Â °ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹Ö ¹æ½ÄÀ̳ª ±×·¸Áö ¾ÊÀº ¹æ½ÄÀ̳ª ¶È°°Àº ºñ¿ëÀÌ µç´Ù. ÀÌÀü °ÍÀº ´õ ÀÌ»ó »ç¿ëµÇÁö ¾ÊÀ¸¹Ç·Î, ÇöÀçÀÇ ÁýÇÕÀ§¿¡ µ¡ºÙ¿©¼­(destructive update) »õ·Î¿î ¿ø¼Ò¸¦ ¸Å´Þ¸é ±×¸¸ÀÌ´Ù. µå´Â ½Ã°£Àº, »õ·Î¿î ¿ø¼ÒÀÇ À§Ä¡¸¦ ã´Â ½Ã°£ log N(Æ®¸®À§ÀÇ ÇÑ °æ·Î) ¸¸Å­ÀÌ´Ù. ¸Þ¸ð¸®´Â »õ·Î ¸Å´Ù´Â ¿ø¼Ò Çϳª¸¸ ´õ ÀÖÀ¸¸é µÈ´Ù.
  ±¸Ã¼ÀûÀ¸·Î µûÁ®º¸¾ÒµíÀÌ, ÀÌÁø Ž»ö Æ®¸®·Î ±¸ÇöµÈ ÁýÇÕ¿¡ »õ·Î¿î ¿ø¼Ò¸¦ ÷°¡ÇÏ´Â ¿¬»êÀ» ±¸Çö ÇÒ ¶§, °ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹Ö(°ªÀº º¯ÇÏÁö ¾Ê´Â´Ù)¸¦ °¡Á¤ÇÏ¸é ½Ã°£°ú ¸Þ¸ð¸®ÀÇ ¼Ò¸ð°¡ ±×·¸Áö ¾ÊÀº °æ¿ì¿Í °°°Å³ª ±×º¸´Ù ¿ÀÈ÷·Á Àû°ÔµÈ´Ù.

¸¶Ä¡¸é¼­

°ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹Ö(value-oriented programming)Àº ±âÁ¸ÀÇ ¹°°ÇÁß½ÉÀÇ ÇÁ·Î±×·¡¹Ö(object-oriented programming)°ú´Â ´Ù¸¥ »ý°¢ÀÇ Æ²À» Á¦°øÇÑ´Ù. ¹°°Ç(object)À» ¸¸µé°í º¯È­½ÃÅ°´Â °úÁ¤À» ÇÁ·Î±×·¥À¸·Î ÀÛ¼ºÇÏ´Â °ÍÀÌ ¾Æ´Ï°í, °ª(value)À» Á¤ÀÇÇÏ°í °è»êÇÏ´Â °úÁ¤À» ÇÁ·Î±×·¥À¸·Î ²Ù¹Ìµµ·Ï ÇÑ´Ù. ¹°°Ç°ú °ªÀÇ Â÷ÀÌ´Â, ¹°°ÇÀº º¯ÇÏÁö¸¸, °ªÀº º¯ÇÏÁö ¾Ê´Â´Ù´Â °ÍÀÌ´Ù. Ç×»ó º¯È­ÇÏ´Â ¹°°ÇÀ» »ý°¢Çϸ鼭 ÇÁ·Î±×·¡¹Ö ÇÏ´Â º¹ÀâÇÔ ´ë½Å¿¡, ÇÁ·Î±×·¥Àº °ªÀ» °è»êÇÏ°í Á¤ÀÇÇÏ´Â °Í »ÓÀ̶ó´Â, ¿ì¸®°¡ »ç½Ç Áß°íµîÇб³ ¼öÇп¡¼­ Àͼ÷ÇÏ°Ô »ç¿ëÇÏ´ø ½±°í °£´ÜÇÑ ÇÁ·Î±×·¡¹Ö ½ºÅ¸ÀÏÀÎ °ÍÀÌ´Ù.

»ç½Ç ÀÌ ÀÚ¿¬½º·¯¿î °³³äÀº Áö³­ 300³âÀÌ»ó ¼öÇÐ(°úÇÐ)ÀÇ ¹ßÀüÀ» ¼ÒÅë½ÃÄ×´ø °£ÆíÇÑ ¾ð¾î ÀÎÇÁ¶ó¿´°í, ÄÄÇ»ÅÍ ¼ÒÇÁÆ®¿þ¾îÀÇ ¹ßÀüÀ» À§Çؼ­µµ ÀÌ·¯ÇÑ °³³äÀ» °®Ãá ¾ð¾î°¡ »ç¿ëµÉ ÇÊ¿ä°¡ ÀÖ´Ù. ¿ì¸®°¡ ÀÌ¹Ì Àͼ÷ÇÑ ¹Ù ÀÖ´Â ÀÌ·¯ÇÑ ÇÁ·Î±×·¡¹Ö ¾ð¾îÀÇ °³³äÀÌ Áö±Ý±îÁö ¹¯ÇôÁ³´ø °ÍÀº, ÄÄÇ»ÅÍ¿¡¼­ ±× °³³äÀ» È¿°úÀûÀ¸·Î Áö¿øÇÏ´Â ¹æ¹ýÀÌ ¾ø¾ú±â ¶§¹®ÀÌ´Ù. ÇÏÁö¸¸, ÀÌÁ¦´Â ±×·¯ÇÑ ÀÚ¿¬½º·´°í °£´ÜÇÑ ÇÁ·Î±×·¡¹Ö °³³äÀ» È¿°úÀûÀ¸·Î Áö¿øÇÏ´Â ¾ð¾îµéÀÌ ÀÌ¹Ì ÇöÀåÀ¸·Î ³ª¿À±â ½ÃÀÛÇß´Ù.

°ªÁß½ÉÀÇ ÇÁ·Î±×·¥µéÀº ½ÇÇà ºñ¿ëÀÌ ¸¹ÀÌ µå´Â °Ç ¾Æ´Ò±î ¿°·ÁÇÒ ÇÊ¿ä´Â ¾ø´Ù. ÀüÅëÀûÀÎ ÄÄÆÄÀÏ·¯ ±â¼úµéÀÌ ¿¡¼Àºí¸® ÇÁ·Î±×·¡¹ÖÀ» ¸¸Á·½º·´°Ô ´ëü½ÃÄ×µíÀÌ, °ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹Ö ¾ð¾î¸¦ ±¸ÇöÇÏ´Â »õ·Î¿î ÄÄÆÄÀÏ·¯ ±â¼úµéÀº ÀÌ¹Ì ±×·¯ÇÑ ¿°·Á¸¦ ±â¿ì¿¡ °¡±õ°Ô ¸¸µé¾î ³õ¾Ò´Ù. ¹®Á¦´Â ±âÁ¸ÀÇ ÇÁ·Î±×·¡¹Ö ¹æ½ÄÀÇ »çȸ/°æÁ¦Àû °ü¼ºÀ» ¾î¶»°Ô °Å½º¸£³Ä´Â °ÍÀÌ´Ù. ±×°ÍÀ» °Å½º¸£´Â ÇØÄ¿µé, ÀÌ¹Ì Â¥¿©Áø ¸ÅÆ®¸¯½º¸¦ °Å½½·¯ »õ·Î¿î ÇÁ·Î±×·¡¹ÖÀÇ ¼¼°è¸¦ È®ÀÎÇÏ°í ½Í¾îÇÏ´Â ³×¿À(¿µÈ­ [¸ÅÆ®¸¯½º]ÀÇ ÁÖÀΰø) µéÀÌ ³ª¼³ ¹«´ë´Â ÁغñµÇ¾î ÀÖ´Ù.

ÀÌÂëÇؼ­ À̹ø ùȸÀÇ ³»¿ëÀ» ¸¶Ä¡µµ·Ï ÇÏÀÚ. ´ÙÀ½È£¿¡¼­´Â, ÀÌ ½Ã¸®Áî°¡ ´Ù·ç±â·ÎÇÑ nMLÀ̶ó´Â °ªÁß½ÉÀÇ ÇÁ·Î±×·¡¹Ö ¾ð¾î°¡ ÄÄÇ»ÅÍ ¼ÒÇÁÆ®¿þ¾îÀÇ ¹ß´Þ°úÁ¤¿¡¼­ ¾î´À À§Ä¡¿¡¼­ ¾î¶² ¿ªÇÒÀ» Çϵµ·Ï °í¾ÈµÇ°í ÀÖ´ÂÁö¸¦ »ìÆ캸µµ·Ï ÇÏ°Ú´Ù. ±×·¸°Ô µÎ ȸÀÇ ±ÛÀ» ÅëÇؼ­ nMLÀ» º¸´Â ¿ì¸®ÀÇ ¾È¸ñÀ» ÁغñÇÑ ÈÄ¿¡, 3ȸ ºÎÅÍ´Â ±¸Ã¼ÀûÀÎ nML ÇÁ·Î±×·¡¹ÖÀÇ ¼¼°è·Î ¿©ÇàÇغ¸µµ·Ï ÇÏÀÚ.