¡ºÇÁ·Î±×·¡¹Ö ¾ð¾î °­ÁÂ-C,C++,VC °­Á (go PROG)¡» 1593¹ø Á¦ ¸ñ:[°­ÁÂ] Æ÷ÀÎÅÍ ½ºÅ͵ð [8/8] -½Å°æÈ£ ¿Ã¸°ÀÌ:ÆÄÀÌ»ç¶û(½Å°æÈ£ ) 00/01/27 00:00 ÀÐÀ½:516 °ü·ÃÀÚ·á ¾øÀ½ ----------------------------------------------------------------------------- ¡º¹è¿òÅÍ-°­Á (go SSCS)¡» 33¹ø Á¦ ¸ñ:[°­ÁÂ] Æ÷ÀÎÅÍ ½ºÅ͵ð [8/8] -½Å°æÈ£ ¿Ã¸°ÀÌ:ÆÄÀÌ»ç¶û(½Å°æÈ£ ) 00/01/23 23:37 ÀÐÀ½: 4 °ü·ÃÀÚ·á ¾øÀ½ ----------------------------------------------------------------------------- ¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬ ¡á Æ÷ÀÎÅÍ ½ºÅ͵ð [8] ¡á ¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬ [990221 ÆÄÀÌ»ç¶û] ¢Ä ¾î´Àµ¡ ½ºÅ͵𸦠¸¶ÃÄ¾ß ÇÒ ½Ã°£ÀÌ ¿Ô³×¿ä. Àç¹Ìµµ ¾ø°í Áö·çÇϱ⸸ ÇßÀ» ±×µ¿¾ÈÀÇ ½ºÅ͵𠸹ÀÌ ºÁ Áּż­ Á¤¸» °¨»çµå¸®±¸¿ä. ºÎÁ·ÇÏÁö¸¸ Á¶±ÝÀ̳ª ¸¶ µµ¿òÀÌ µÇ¾ú´Ù¸é ´ÙÇàÀÏÅ×Áö¿ä. Á¦°¡ °³ÀÎÀûÀ¸·Î ¹ÙºüÁú(^^) °ü°è·Î ÈÄ ¹ÝÀÇ ¸î°³ÀÇ ½ºÅ͵𸦠³¯¸²À¸·Î ¸¸µéÁö´Â ¾Ê¾Ò³ª ÇÏ´Â »ý°¢µµ µé°í¡¦ ==;; C++ ½ºÅ͵𸦠ÇÒ ¼ö ÀÖÀ»Áö ¾øÀ»Áöµµ È®½ÇÇÏ°Ô ¸»¾¸µå¸± ¼ö°¡ ¾ø³×¿ä. ±×·³ »õÇØ º¹ ¸¹ÀÌ ¹ÞÀ¸½Ã±¸¿ä. ÇϽô ÀÏ ¸ðµÎ Àß µÇ½Ã±æ ¹Ù¶ø´Ï´Ù. ±âȸ °¡ µÇ¸é C++ ½ºÅ͵𿡼­ ´Ù½Ã ºËµµ·Ï ÇÏÁö¿ä. *^^* ¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬ ¡á 8. ÀÌÁß ¸µÅ©µå ¸®½ºÆ®¿Í Å¥, ½ºÅà ¡á ¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬ ¢Ä ÀÌÁß ¸µÅ©µå ¸®½ºÆ® ½Ã°£ ½Ã°£¿¡´Â ´ÜÀÏ ¸µÅ©µå ¸®½ºÆ®¸¦ Çß¾úÁö¿ä. ´ÜÀÏ°ú ÀÌÁß. ¸Ó°¡ Çϳª°í µÎ°³¶õ ¸»Àϱî¿ä? ³×. ±×·¸Áö¿ä. ¹Ù·Î ¿¬°áÀ» ½ÃÄÑÁÖ´Â Æ÷ÀÎÅÍ ÀÔ´Ï´Ù. ´ÜÀÏ ¸µÅ©µå ¸®½ºÆ®¿¡¼­´Â Æ÷ÀÎÅÍ°¡ next ¹Û¿¡ Á¸ÀçÇÏÁö ¾Ê¾Ò¾úÁö¿ä. ÀÌÁß ¸µÅ©µå ¸®½ºÆ®¿¡´Â ¿©±â¿¡ prev Æ÷ÀÎÅ͸¦ ´õÇؼ­ Æ÷ÀÎÅÍ°¡ µÎ°³ Á¸Àç ÇÕ´Ï´Ù. Æ÷ÀÎÅÍ °¡ µÎ°³¶ó¼­ ¾ò´Â À̵æÀº ¹«¾ùÀÌ ÀÖÀ»±î¿ä? Áö³­ ½Ã°£¿¡ ³ëµåÀÇ Æ÷ÀÎÅ͸¦ ¹Þ ¾Æ ±× ³ëµå¸¦ »èÁ¦ÇÏ´Â ÇÔ¼ö¸¦ ¸¸µé ¶§ ¿ì¸®´Â ±× ³ëµåÀÇ ¹Ù·Î ¾Õ ³ëµå¸¦ ã ±â À§ÇØ Àüü ¸®½ºÆ®¸¦ Çì¸Þ°í ´Ù´Ïµµ·Ï Çß¾úÁö¿ä. ÇÏÁö¸¸ ÀÌÁ¦´Â ¹Ù·Î ¾Õ ³ë µåÀÇ Æ÷ÀÎÅ͵µ °¡Áö°í Àֱ⠶§¹®¿¡ ±×·² ÇÊ¿ä°¡ ¾ø½À´Ï´Ù. ¾îµð¿¡ ³¢¿ö ³Ö±â ¸¦ Çϰųª ÇÒ¶§µµ ¹Ù·Î Á¢±ÙÀÌ °¡´ÉÇϱ⠶§¹®¿¡ ÈξÀ Æí¸®ÇÏÁö¿ä. ±×·¯³ª ¸Þ ¸ð¸®¸¦ Á¶±Ý ¸¹ÀÌ »ç¿ëÇÏ°í(¾Æ¹«·¡µµ Æ÷ÀÎÅÍ°¡ µÎ°³´Ï±î¡¦) ¼Ò½º Äڵ尡 Á¶±Ý º¹ÀâÇØÁø´Ù´Â(°æ¿ì¿¡ µû¶ó¼­´Â ´õ ´Ü¼øÇØ Áú¼öµµ ÀÖ°í¡¦) ´ÜÁ¡ÀÌ ÀÖ±â´Â ÇÏÁö ¸¸ Æí¸®Çϱ⠶§¹®¿¡ ´ÜÀÏ º¸´Ù´Â ÀÌÁß ¸µÅ©µå ¸®½ºÆ®°¡ ´õ ¸¹ÀÌ »ç¿ë µË´Ï´Ù. struct node_tag { int number; struct node_tag *prev, *next; }; typedef struct node_tag node_t; Á¤¼ö¸¦ ÀúÀåÇÏ´Â ÀÌÁß ¸µÅ©µå ¸®½ºÆ®ÀÇ ³ëµå¸¦ ¼±¾ð Çß½À´Ï´Ù. ÀÌÁ¦ ¾Õ¿¡¼­ Çß´ø °Íó·³ head¿Í tail Æ÷ÀÎÅ͸¦ ¸¸µé°í countµµ ¸¸µì½Ã´Ù. node_t *head = NULL, *tail = NULL; int count = 0; ÀÌÁ¦ ½ÇÁ¦·Î Å¥¸¦ Çϳª ¸¸µé¾î º¸¸é¼­ ÀÌÁß ¸µÅ©µå ¸®½ºÆ®ÀÇ »ç¿ë ¹æ¹ýÀ» ¾Ë¾Æº¸µµ·Ï ÇÏÁö¿ä. ¢Ä Å¥ Å¥´Â ¾Æ½Ã´Ù½ÃÇÇ ¸ÕÀú µé¾î°£ °ÍÀÌ ¸ÕÀú ³ª¿À´Â FIFO(First In, First Out) ±¸Á¶ ÀÔ´Ï´Ù. µé¾î°¡´Â °÷À» head¶ó°í ÇÏ°í ³ª¿À´Â °÷À» tailÀ̶ó°í ÇÏÁö¿ä. int enqueue(int number) { node_t *temp; temp = (node_t *)malloc(sizeof(node_t)); if (temp == NULL) return 0; // ¸Þ¸ð¸® ÇÒ´ç ¿¡·¯ temp->number = number; temp->prev = NULL; // head·Î µé¾î°¡¹Ç·Î temp°¡ ù ³ëµå°¡ µÊ temp->next = head; count++; if (head != NULL) head->prev = temp; if (head == NULL) tail = temp; head = temp; return 1; } ¿ì¼± tempÀÇ °ªµéÀ» ¼³Á¤ÇÑ ÈÄ¿¡ ´Ù¸¥ ³ëµå°¡ Á¸ÀçÇϸé headÀÇ ¾Õ¿¡ temp¸¦ ¿¬°áÇÏÁö¿ä. ÀÌÁ¦ »õ·Î¿î head´Â temp°¡ µÇ°í, Ãʱ⠻óÅÂÀ̸é tailµµ temp°¡ µÇÁö¿ä. (head = temp¸¦ if (head ...)º¸´Ù ¾Õ¿¡ ¾²¸é ¾ÈµË´Ï´Ù) int dequeue(void) { int number; if (tail == NULL) return NULL; // Ãʱ⠻óÅÂÀÎ °æ¿ì number = tail->number; // tailÀº Àá½Ã ÈÄ free¿¡ ÀÇÇØ »èÁ¦µÇ¹Ç·Î // °ªÀ» µû·Î ÀúÀåÇÏ°í ÀÖ¾î¾ß ÇÕ´Ï´Ù tail = tail->prev; // »õ·Î¿î tailÀº ¹Ù·Î ¾Õ ³ëµå°¡ µË´Ï´Ù if (tail != NULL) { free(tail->next); // ¿ø·¡ÀÇ tailÀÌ »èÁ¦ µË´Ï´Ù tail->next = NULL; } else head = NULL; // ¸ðµç node°¡ »èÁ¦µÈ °æ¿ì headµµ NULLÀÌ µÊ count--; return number; } void main(void) { printf("%d\n", dequeue()); // 0 enqueue(1); enqueue(2); enqueue(3); printf("%d\n", dequeue()); // 1 enqueue(4); enqueue(5); enqueue(6); printf("%d\n", dequeue()); // 2 printf("%d\n", dequeue()); // 3 printf("%d\n", dequeue()); // 4 printf("%d\n", dequeue()); // 5 printf("%d\n", dequeue()); // 6 enqueue(7); enqueue(8); printf("%d\n", dequeue()); // 7 printf("%d\n", dequeue()); // 8 } °á°ú´Â ¿¹»ó´ë·Î ³ª¿É´Ï´Ù. ¢Ä ½ºÅà ½ºÅÃÀº µé¾î°£ °÷°ú ³ª¿À´Â °÷ÀÌ µ¿ÀÏÇÏ¸é µÇ°ÚÁö¿ä. µÑ´Ù tailÀ̶ó°í °¡Á¤ ÇսôÙ. int push(int number) { node_t *temp; temp = (node_t *)malloc(sizeof(node_t)); if (temp == NULL) return 0; // ¸Þ¸ð¸® ÇÒ´ç ¿¡·¯ temp->number = number; temp->next = NULL; // tail·Î µé¾î°¡¹Ç·Î temp°¡ ³¡ ³ëµå°¡ µÊ temp->prev = tail; count++; if (tail != NULL) tail->next = temp; if (tail == NULL) head = temp; tail = temp; return 1; } int pop(void) { int number; if (tail == NULL) return NULL; // Ãʱ⠻óÅÂÀÎ °æ¿ì number = tail->number; // tailÀº Àá½Ã ÈÄ free¿¡ ÀÇÇØ »èÁ¦µÇ¹Ç·Î // °ªÀ» µû·Î ÀúÀåÇÏ°í ÀÖ¾î¾ß ÇÕ´Ï´Ù tail = tail->prev; // »õ·Î¿î tailÀº ¹Ù·Î ¾Õ ³ëµå°¡ µË´Ï´Ù if (tail != NULL) { free(tail->next); // ¿ø·¡ÀÇ tailÀÌ »èÁ¦ µË´Ï´Ù tail->next = NULL; } else head = NULL; // ¸ðµç node°¡ »èÁ¦µÈ °æ¿ì headµµ NULLÀÌ µÊ count--; return number; } void main(void) { printf("%d\n", pop()); // 0 push(1); push(2); push(3); printf("%d\n", pop()); // 3 push(4); push(5); push(6); printf("%d\n", pop()); // 6 printf("%d\n", pop()); // 5 printf("%d\n", pop()); // 4 printf("%d\n", pop()); // 3 printf("%d\n", pop()); // 2 push(7); push(8); printf("%d\n", pop()); // 8 printf("%d\n", pop()); // 7 } pop ÇÔ¼öÀÇ °æ¿ì Å¥ÀÇ dequeue ÇÔ¼ö¿Í ¶È°°½À´Ï´Ù. ¶È°°ÀÌ tail¿¡¼­ ÇϳªÀÇ °ªÀ» »©¿À´Â ÇÔ¼öÀÌ´Ï ´Ù¸¦ ÀÌÀ¯°¡ ¾øÁö¿ä. ±×·±µ¥ À§ÀÇ µÎ ÇÔ¼ö¸¦ º¸¸é head °ªÀ» ¿©±âÀú±â¼­ º¯°æÇϱâ´Â Çϴµ¥ ¾Æ¹« °÷¿¡¼­µµ ÂüÁ¶¸¦ ¾ÈÇÏÁö¿ä? Áï ½ºÅà ¿¡¼­´Â head³ª tail Áß¿¡ Çϳª¸¸ À־ µÈ´Ù´Â °Ì´Ï´Ù. ´ç¿¬È÷ ÇÑÂÊ¿¡¼­¸¸ ÀÔÃâ·ÂÀ» Çϱ⠶§¹®¿¡ ¹Ý´ëÂÊÀÇ Æ÷ÀÎÅ͸¦ °¡Áú ÇÊ¿ä°¡ ¾ø´Â °ÍÀÌÁö¿ä. head°¡ ÀÖ´Â ºÎºÐÀ» »©°í ½ÇÇàÇصµ ¾Æ¹« ¹®Á¦°¡ ¾ø½À´Ï´Ù. À§ÀÇ dequeue¿Í pop ÇÔ¼öÀÇ °æ¿ì ¸®½ºÆ®¿¡ ¾Æ¹«·± °ªµµ ¾øÀ» ¶§ 0À» ¸®ÅÏÇÏ ´Âµ¥¿ä. ±×·¸´Ù¸é ¸®½ºÆ®¿¡ 0À̶ó´Â °ªÀ» ³Ö¾úÀ» ¶§ ±× ¸®½ºÆ®°¡ ºñ¾ú´Ù´Â Ç¥ ½ÃÀÎÁö °ª 0ÀÎÁö ±¸º°À» ÇÏÁö ¸øÇÏÁö¿ä. ¾î¶² Ã¥µéÀ» º¸¸é Æ÷ÀÎÅ͸¦ ¸®ÅÏÇÏ¹Ç ·Î½á ÇØ°áÀ» Çϱ⵵ Çϴµ¥ ÀÌ·± ¹æ¹ýÀº ¸Þ¸ð¸®¿¡¼­ ¹®Á¦°¡ »ý±æ ¼öµµ ÀÖ½À´Ï ´Ù. Â÷¶ó¸® is_null µîÀÇ ÇÔ¼ö¸¦ »õ·Î ¸¸µé¾î¼­ ºñ¾î ÀÖ´ÂÁö ¿©ºÎ¸¦ È®ÀÎÇÏ°í °ªÀ» »©³»´Â °ÍÀÌ ÁÁÀ» µí Çϳ׿ä. ¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬ ¢Ä Áö³­ ½Ã°£ÀÇ ½ºÅ͵𠳻¿ëÀ» ¿ÏÀüÈ÷ ÀÌÇØÇß´Ù°í °¡Á¤ÇÏ°í ½è±â ¶§¹®¿¡ ¼Ò½º ¿Ü¿¡´Â º°°Ô ¾ø³×¿ä. ÀÌÇØ°¡ ¾ÈµÇ½Ã¸é ¿ì¼± Áö³­ ½Ã°£ÀÇ ³»¿ëÀ» È®½ÇÈ÷ ÀÌ ÇØÇÏ°í ´Ù½Ã º¸¼¼¿ä. CÀÇ °¡Àå °í±Þ ±â¹ýÀ̶ó°í ÇÒ ¼ö ÀÖ´Â(?) Æ÷ÀÎÅ͸¦ È°¿ëÇÑ ¸µÅ©µå ¸®½ºÆ®±îÁö ¸ðµÎ ³¡³µ½À´Ï´Ù. ±×·³ ¸ðµÎ ÇູÇϼ¼¿ä. (¸µÅ©µå ¸®½ºÆ®¸¦ ¸» ±×´ë·Î ¸®½ºÆ®·Î ¾²°í Áß°£¿¡ »ðÀÔÇϰųª »èÁ¦ÇÏ´Â ÇÔ¼öµéµµ Çѹø ¸¸µé¾î º¸¼¼¿ä) ¢Ä Thanks To 98 ³ª¹Ý, Àü°ø ¼Ò¸ðÀÓ OZ¡¦ Special Thanks To »ç¶ûÇÏ´Â ¿ï¹Ý ³» Ä£±¸´ú¡¦ (ƯÈ÷ ½ºÅ͵ð °è¼ÓÇϵµ·Ï °Ý·ÁÇØ ÁØ ¸ð¾ç, ¸ð±º¡¦ ^^) ÀÌ»Û ¸»¸¸ ¾²´Â ¼¼»óÀ» ¸¸µé°í ½ÍÀº ÆÄÀÌ°¡¡¦ ^^; µð ¾Øµå. ¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬¦¬