{"id":27968,"date":"2024-10-27T15:20:43","date_gmt":"2024-10-27T15:20:43","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=27968"},"modified":"2024-11-26T07:12:56","modified_gmt":"2024-11-26T07:12:56","slug":"%ec%9e%90%eb%b0%94%ec%8a%a4%ed%81%ac%eb%a6%bd%ed%8a%b8-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%eb%b9%8c%eb%94%a9-%ec%88%9c%ec%84%9c-%ea%b5%ac%ed%95%98%ea%b8%b0","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/27968\/","title":{"rendered":"\uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8 \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \ube4c\ub529 \uc21c\uc11c \uad6c\ud558\uae30"},"content":{"rendered":"

<\/p>\n

\ubcf8 \uae00\uc5d0\uc11c\ub294 \uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8 \ucf54\ub529\ud14c\uc2a4\ud2b8 \ubb38\uc81c \uc911\uc5d0\uc11c ‘\ube4c\ub529 \uc21c\uc11c \uad6c\ud558\uae30’ \ubb38\uc81c\ub97c \ub2e4\ub8f0 \uac83\uc785\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub294 \uadf8\ub798\ud504 \uc774\ub860\uacfc \uc704\uc0c1 \uc815\ub82c(topological sorting) \uac1c\ub150\uc744 \ud65c\uc6a9\ud558\uc5ec \ud480 \uc218 \uc788\ub294 \ud765\ubbf8\ub85c\uc6b4 \ubb38\uc81c\uc785\ub2c8\ub2e4. \uc2dc\uc791\ud558\uae30 \uc804\uc5d0 \ubb38\uc81c\uc758 \uc815\uc758\uc640 \uc694\uad6c\uc0ac\ud56d\uc744 \uc0b4\ud3b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n

\ubb38\uc81c \uc815\uc758<\/h2>\n

\uc8fc\uc5b4\uc9c4 N\uac1c\uc758 \ube4c\ub529\uacfc \uadf8\ub4e4 \uc0ac\uc774\uc758 \uc758\uc874 \uad00\uacc4\ub97c \ubc14\ud0d5\uc73c\ub85c, \ubaa8\ub4e0 \ube4c\ub529\uc744 \uac74\uc124\ud558\uae30 \uc704\ud574 \ud544\uc694\ud55c \uc21c\uc11c\ub97c \uad6c\ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. \ube4c\ub529 A\uac00 \ube4c\ub529 B\ubcf4\ub2e4 \uba3c\uc800 \uac74\uc124\ub418\uc5b4\uc57c \ud55c\ub2e4\uba74, \uc774 \ub450 \ube4c\ub529 \uc0ac\uc774\uc5d0\ub294 \uc758\uc874 \uad00\uacc4\uac00 \uc788\ub2e4\uace0 \ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n

\uc785\ub825<\/h3>\n
\n\uc785\ub825\uc740 \ub2e4\uc74c\uacfc \uac19\uc740 \ud615\uc2dd\uc774\ub2e4:\n- \uccab \uc904: N (\ube4c\ub529\uc758 \uac1c\uc218), M (\uc758\uc874 \uad00\uacc4\uc758 \uc218)\n- \ub2e4\uc74c M\uc904: A B (\ube4c\ub529 A\ub294 \ube4c\ub529 B\ubcf4\ub2e4 \uba3c\uc800 \uac74\uc124\ub418\uc5b4\uc57c \ud568\uc744 \ub098\ud0c0\ub0c4)\n    <\/code><\/pre>\n
\ucd9c\ub825<\/h3>\n
\n\uac00\ub2a5\ud55c \ube4c\ub529 \uac74\uc124 \uc21c\uc11c\ub97c \ud55c \uc904\uc5d0 \uacf5\ubc31\uc73c\ub85c \uad6c\ubd84\ud558\uc5ec \ucd9c\ub825\ud55c\ub2e4. \ub2e8, \uc21c\uc11c\uac00 \uac00\ub2a5\ud558\uc9c0 \uc54a\uc744 \uacbd\uc6b0 \"Impossible\"\uc744 \ucd9c\ub825\ud55c\ub2e4.\n    <\/code><\/pre>\n
\uc608\uc81c<\/h2>\n
\uc608\uc81c 1<\/h3>\n
\n\uc785\ub825:\n4 2\n1 2\n2 3\n\n\ucd9c\ub825:\n1 2 3 4\n    <\/code><\/pre>\n
\uc608\uc81c 2<\/h3>\n
\n\uc785\ub825:\n3 3\n1 2\n2 3\n3 1\n\n\ucd9c\ub825:\nImpossible\n    <\/code><\/pre>\n
\ubb38\uc81c \ud574\uacb0 \uacfc\uc815<\/h2>\n
\uc704\uc0c1 \uc815\ub82c(Topological Sorting)<\/h3>\n
\uc774 \ubb38\uc81c\uc758 \ud574\uacb0\uc5d0 \uc788\uc5b4\uc11c \uac00\uc7a5 \uc911\uc694\ud55c \uac1c\ub150\uc740 \uc704\uc0c1 \uc815\ub82c\uc785\ub2c8\ub2e4. \uc704\uc0c1 \uc815\ub82c\uc740 \ubc29\ud5a5\uc131\uc774 \uc788\ub294 \uadf8\ub798\ud504\uc5d0\uc11c \ubaa8\ub4e0 \uc815\uc810\uc758 \uc120\ud6c4 \uad00\uacc4\ub97c \uace0\ub824\ud558\uc5ec \uc815\ub82c\ub41c \ud615\ud0dc\ub85c \ub098\uc5f4\ud558\ub294 \ubc29\ubc95\uc785\ub2c8\ub2e4. \uc704\uc0c1 \uc815\ub82c\uc758 \uacb0\uacfc\uac00 \uc874\uc7ac\ud558\ub824\uba74 \uadf8\ub798\ud504\uac00 \uc0ac\uc774\ud074\uc774 \uc5c6\uc5b4\uc57c \ud569\ub2c8\ub2e4. \uc989, \ubaa8\ub4e0 \uc758\uc874 \uad00\uacc4\uac00 \uba85\ud655\ud574\uc57c\ub9cc \uc21c\uc11c\ub97c \uc815\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
\ubb38\uc81c \ud574\uacb0 \uc54c\uace0\ub9ac\uc998<\/h3>\n
\ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud55c \uc54c\uace0\ub9ac\uc998\uc744 \ub2e4\uc74c\uacfc \uac19\uc774 \uad6c\uc131\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
    \n
  1. \uadf8\ub798\ud504\uc758 \uc815\uc810 \uc218(N)\uc640 \uac04\uc120 \uc218(M)\ub97c \uc77d\uc2b5\ub2c8\ub2e4.<\/li>\n
  2. \uadf8\ub798\ud504\uc758 \uc778\uc811 \ub9ac\uc2a4\ud2b8\ub97c \uc0dd\uc131\ud558\uba74\uc11c, \uac01 \ube4c\ub529\uc774 \uac74\uc124\ub418\uae30 \uc704\ud574 \ud544\uc694\ud55c \ube4c\ub529\uc758 \uc218(\uc9c4\uc785 \ucc28\uc218)\ub97c \uce74\uc6b4\ud2b8\ud569\ub2c8\ub2e4.<\/li>\n
  3. \uc9c4\uc785 \ucc28\uc218\uac00 0\uc778 \ube4c\ub529\uc744 \ud050\uc5d0 \ucd94\uac00\ud569\ub2c8\ub2e4.<\/li>\n
  4. \ud050\uc5d0\uc11c \ube4c\ub529\uc744 \ud558\ub098\uc529 \uaebc\ub0b4\uc5b4 \uacb0\uacfc \ub9ac\uc2a4\ud2b8\uc5d0 \ucd94\uac00\ud558\uace0, \uadf8 \ube4c\ub529\uacfc \uc758\uc874 \uad00\uacc4\uc5d0 \uc788\ub294 \ube4c\ub529\ub4e4\uc758 \uc9c4\uc785 \ucc28\uc218\ub97c \uac10\uc18c\uc2dc\ud0b5\ub2c8\ub2e4.<\/li>\n
  5. \uc9c4\uc785 \ucc28\uc218\uac00 0\uc774 \ub418\ub294 \ube4c\ub529\uc744 \ud050\uc5d0 \ucd94\uac00\ud569\ub2c8\ub2e4.<\/li>\n
  6. \ubaa8\ub4e0 \ube4c\ub529\uc744 \ucc98\ub9ac\ud55c \ud6c4, \uacb0\uacfc \ub9ac\uc2a4\ud2b8\uc758 \uae38\uc774\uac00 N\uacfc \uac19\uc73c\uba74 \uac00\ub2a5\ud55c \uac74\uc124 \uc21c\uc11c\ub97c \ucd9c\ub825\ud558\uace0, \uadf8\ub807\uc9c0 \uc54a\uc73c\uba74 “Impossible”\uc744 \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n
    \uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8 \ucf54\ub4dc \uad6c\ud604<\/h3>\n
    \nfunction getConstructionOrder(N, M, dependencies) {\n    const graph = Array.from({ length: N + 1 }, () => []);\n    const indegree = Array.from({ length: N + 1 }, () => 0);\n    \n    \/\/ \uc758\uc874 \uad00\uacc4\ub97c \uadf8\ub798\ud504\uc5d0 \ucd94\uac00\n    for (const [a, b] of dependencies) {\n        graph[a].push(b);\n        indegree[b]++;\n    }\n    \n    const queue = [];\n    \n    \/\/ \uc9c4\uc785 \ucc28\uc218\uac00 0\uc778 \ub178\ub4dc \ucd94\uac00\n    for (let i = 1; i <= N; i++) {\n        if (indegree[i] === 0) {\n            queue.push(i);\n        }\n    }\n    \n    const order = [];\n    \n    while (queue.length > 0) {\n        const current = queue.shift();\n        order.push(current);\n        \n        for (const neighbor of graph[current]) {\n            indegree[neighbor]--;\n            if (indegree[neighbor] === 0) {\n                queue.push(neighbor);\n            }\n        }\n    }\n\n    return order.length === N ? order : \"Impossible\";\n}\n\n\/\/ \ud14c\uc2a4\ud2b8 \uc608\uc81c\nconst N = 4;\nconst M = 2;\nconst dependencies = [[1, 2], [2, 3]];\nconst result = getConstructionOrder(N, M, dependencies);\nconsole.log(result.join(' ')); \/\/ \ucd9c\ub825: 1 2 3 4\n    <\/code><\/pre>\n
    \uacb0\ub860<\/h2>\n
    \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 ‘\ube4c\ub529 \uc21c\uc11c \uad6c\ud558\uae30’ \ubb38\uc81c\ub97c \ud1b5\ud574 \uc704\uc0c1 \uc815\ub82c\uc758 \uac1c\ub150\uacfc \uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8\ub85c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ubc29\ubc95\uc744 \ubc30\uc6e0\uc2b5\ub2c8\ub2e4. \uc784\uc758\uc758 \uc785\ub825\uc5d0 \ub300\ud574 \uadf8\ub798\ud504\ub97c \uad6c\uc131\ud558\uace0, \uc774 \uadf8\ub798\ud504\ub97c \uae30\ubc18\uc73c\ub85c \uac00\ub2a5\ud55c \uac74\uc124 \uc21c\uc11c\ub97c \ub3c4\ucd9c\ud558\ub294 \uacfc\uc815\uc744 \ud1b5\ud574 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c \ud574\uacb0 \ub2a5\ub825\uc744 \ud5a5\uc0c1\uc2dc\ud0ac \uc218 \uc788\uae30\ub97c \ubc14\ub78d\ub2c8\ub2e4. \ub2e4\uc591\ud55c \ud14c\ud06c\ub2c8\uceec \uc778\ud130\ubdf0\uc5d0\uc11c \uc720\uc0ac\ud55c \ubb38\uc81c\uac00 \ucd9c\uc81c\ub420 \uc218 \uc788\uc73c\ubbc0\ub85c, \uc9c0\uc18d\uc801\uc778 \uc5f0\uc2b5\uacfc \uc774\ud574\uac00 \ud544\uc694\ud569\ub2c8\ub2e4. \uac10\uc0ac\ud569\ub2c8\ub2e4!<\/p>\n
    \ucc38\uace0 \uc790\ub8cc<\/h2>\n
    \uad00\ub828\ub41c \uc790\ub8cc\uc640 \uc54c\uace0\ub9ac\uc998\uc5d0 \ub300\ud55c \uc774\ud574\ub97c \ub354 \uae4a\uc774 \uc788\uac8c \ud558\uace0 \uc2f6\ub2e4\uba74 \uc544\ub798\uc758 \uc790\ub8cc\ub97c \ucc38\uace0\ud558\uc138\uc694.<\/p>\n