{"id":28001,"date":"2024-10-27T15:20:56","date_gmt":"2024-10-27T15:20:56","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=28001"},"modified":"2024-11-26T07:12:15","modified_gmt":"2024-11-26T07:12:15","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-%ec%b5%9c%ec%9e%a5-%ea%b3%b5%ed%86%b5-%eb%b6%80%eb%b6%84-%ec%88%98%ec%97%b4","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/28001\/","title":{"rendered":"\uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8 \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4 \ucc3e\uae30"},"content":{"rendered":"

<\/p>\n

\n

\ubb38\uc81c \uc124\uba85<\/h2>\n

\n \ub450 \uac1c\uc758 \ubb38\uc790\uc5f4\uc774 \uc8fc\uc5b4\uc84c\uc744 \ub54c, \uc774 \ub450 \ubb38\uc790\uc5f4\uc758 \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4(Longest Common Subsequence, LCS)\uc744 \ucc3e\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4.
\n \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc740 \ub450 \ubb38\uc790\uc5f4\uc758 \uc21c\uc11c\ub97c \uc720\uc9c0\ud558\uba74\uc11c \uacb9\uce58\ub294 \ucd5c\ub300 \uae38\uc774\uc758 \ubd80\ubd84 \ubb38\uc790\uc5f4\uc744 \uc758\ubbf8\ud569\ub2c8\ub2e4.
\n \uc608\ub97c \ub4e4\uc5b4, \ubb38\uc790\uc5f4 A\uac00 “ABCBDAB”\uc774\uace0 \ubb38\uc790\uc5f4 B\uac00 “BDCAB”\uc77c \uacbd\uc6b0, \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc740 “BDAB” \ub610\ub294 “BCAB” \ub4f1\uc785\ub2c8\ub2e4.\n <\/p>\n

\uc785\ub825 \ud615\uc2dd<\/h2>\n

\n – \uccab \ubc88\uc9f8 \uc904\uc5d0 \ubb38\uc790\uc5f4 A\uc758 \uae38\uc774 N\uacfc \ubb38\uc790\uc5f4 B\uc758 \uae38\uc774 M\uc774 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4. (1 \u2264 N, M \u2264 1000)
\n – \ub450 \ubc88\uc9f8 \uc904\uc5d0 \ubb38\uc790\uc5f4 A\uac00 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4.
\n – \uc138 \ubc88\uc9f8 \uc904\uc5d0 \ubb38\uc790\uc5f4 B\uac00 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4.\n <\/p>\n

\ucd9c\ub825 \ud615\uc2dd<\/h2>\n

\n – \ub450 \ubb38\uc790\uc5f4\uc758 \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc758 \uae38\uc774\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.\n <\/p>\n

\uc608\uc81c<\/h2>\n
\n            \uc785\ub825:\n            7 5\n            ABCBDAB\n            BDCAB\n\n            \ucd9c\ub825:\n            4\n        <\/pre>\n
\ubb38\uc81c \ud574\uacb0\uc744 \uc704\ud55c \uc811\uadfc\ubc95<\/h2>\n
\n            \uc774 \ubb38\uc81c\ub294 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d(Dynamic Programming)\uc758 \uc804\ud615\uc801\uc778 \uc608\uc2dc\uc785\ub2c8\ub2e4.
\n            LCS\ub97c \uad6c\ud558\uae30 \uc704\ud574\uc11c\ub294 \ub450\uac1c\uc758 \ubb38\uc790\uc5f4\uc744 \ube44\uad50\ud558\uc5ec \uc77c\uce58\ud558\ub294 \ubb38\uc790\ub97c \ucc3e\uace0,
\n            \uc774 \ub54c\uc758 \ubd80\ubd84 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uc5ec \ucd5c\uc885 \uae38\uc774\ub97c \ub3c4\ucd9c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n        <\/p>\n
\ub2e8\uacc4\ubcc4 \uc811\uadfc<\/h3>\n
    \n
  1. \n\ub3d9\uc801 \uacc4\ud68d\ubc95 \ud14c\uc774\ube14 \ucd08\uae30\ud654:<\/strong><\/p>\n
    \n                    2\ucc28\uc6d0 \ubc30\uc5f4 DP\ub97c \uc0dd\uc131\ud569\ub2c8\ub2e4. DP[i][j]\ub294 \ubb38\uc790\uc5f4 A\uc758 \ucc98\uc74c i\uac1c \ubb38\uc790\uc640 \ubb38\uc790\uc5f4 B\uc758 \ucc98\uc74c j\uac1c \ubb38\uc790\uae4c\uc9c0\uc758
    \n                    \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc758 \uae38\uc774\ub97c \uc800\uc7a5\ud569\ub2c8\ub2e4. \ubc30\uc5f4\uc758 \ud06c\uae30\ub294 (N+1) x (M+1)\uc785\ub2c8\ub2e4.\n                <\/p>\n<\/li>\n
  2. \n\ud14c\uc774\ube14 \ucc44\uc6b0\uae30:<\/strong><\/p>\n
    \n                    A\uc758 i\ubc88\uc9f8 \ubb38\uc790\uc640 B\uc758 j\ubc88\uc9f8 \ubb38\uc790\uac00 \uac19\uc73c\uba74 DP[i][j] = DP[i-1][j-1] + 1
    \n                    \uadf8\ub807\uc9c0 \uc54a\ub2e4\uba74 DP[i][j] = max(DP[i-1][j], DP[i][j-1])\ub85c \uc124\uc815\ud569\ub2c8\ub2e4.\n                <\/p>\n<\/li>\n
  3. \n\uacb0\uacfc \ucd9c\ub825:<\/strong><\/p>\n
    \n                    DP[N][M]\uc5d0 \ub3c4\ub2ec\ud558\uba74 \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc758 \uae38\uc774\ub97c \ubc18\ud658\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n                <\/p>\n<\/li>\n<\/ol>\n
    \uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8 \ucf54\ub4dc<\/h2>\n
    \nfunction longestCommonSubsequence(A, B) {\n    const N = A.length;\n    const M = B.length;\n    \n    \/\/ DP \ud14c\uc774\ube14 \ucd08\uae30\ud654\n    const DP = Array.from(Array(N + 1), () => Array(M + 1).fill(0));\n    \n    \/\/ DP \ud14c\uc774\ube14 \ucc44\uc6b0\uae30\n    for (let i = 1; i <= N; i++) {\n        for (let j = 1; j <= M; j++) {\n            if (A[i - 1] === B[j - 1]) {\n                DP[i][j] = DP[i - 1][j - 1] + 1;\n            } else {\n                DP[i][j] = Math.max(DP[i - 1][j], DP[i][j - 1]);\n            }\n        }\n    }\n    \n    return DP[N][M];\n}\n\n\/\/ \uc785\ub825 \uc608\uc81c \uc2e4\ud589\nconst A = 'ABCBDAB';\nconst B = 'BDCAB';\nconsole.log(longestCommonSubsequence(A, B)); \/\/ Output: 4\n        <\/code><\/pre>\n
    \ubcf5\uc2b5 \ubc0f \uc5f0\uc2b5 \ubb38\uc81c<\/h2>\n
    \n            \uc774 \ubb38\uc81c\ub97c \uc644\uc804\ud788 \uc774\ud574\ud588\ub2e4\uba74, \ucd94\uac00\uc801\uc778 \uc5f0\uc2b5\ubb38\uc81c\ub97c \ud1b5\ud574 \ub2a5\ub825\uc744 \ud0a4\uc6cc\ubcf4\uc138\uc694. \ub2e4\uc74c\uacfc \uac19\uc740 \ubb38\uc81c\uc5d0 \ub3c4\uc804\ud574 \ubcf4\uc2ed\uc2dc\uc624.\n        <\/p>\n