\uc8fc\uc5b4\uc9c4 \ub450 \ubb38\uc790\uc5f4 A\uc640 B\uac00 \uc788\uc744 \ub54c, \uc774\ub4e4 \ubb38\uc790\uc5f4\uc758 \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4(Longest Common Subsequence, LCS)\uc744 \ucc3e\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. \ubd80\ubd84 \uc218\uc5f4\uc740 \ubb38\uc790\uc5f4\uc5d0\uc11c \ubb38\uc790\uc758 \uc21c\uc11c\ub97c \uc720\uc9c0\ud558\uba74\uc11c \uc0ad\uc81c\ub85c \uc5bb\uc744 \uc218 \uc788\ub294 \ubb38\uc790\uc5f4\uc785\ub2c8\ub2e4. \uc989, A\uc758 \ubd80\ubd84 \uc218\uc5f4\uc774 B\uc5d0 \uc874\uc7ac\ud574\uc57c \ud569\ub2c8\ub2e4.<\/p>\n
\uc608\ub97c \ub4e4\uc5b4, \ubb38\uc790\uc5f4 A\uac00 “ABCBDAB”\uc774\uace0 B\uac00 “BDCAB”\ub77c\uba74, \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc740 “BCAB”\uc785\ub2c8\ub2e4. \uc774\ub7ec\ud55c LCS \ubb38\uc81c\ub294 \ub2e4\uc591\ud55c \ubd84\uc57c\uc5d0\uc11c \ud6a8\uc728\uc801\uc778 \uc54c\uace0\ub9ac\uc998\uc744 \ud544\uc694\ub85c \ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4.<\/p>\n
\ub450 \ubb38\uc790\uc5f4 A\uc640 B\uc758 \uae38\uc774 N, M (1 \u2264 N, M \u2264 1000) \ubc0f \ubb38\uc790\uc5f4 A\uc640 B\uac00 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4.<\/p>\n
\ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc758 \uae38\uc774\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/p>\n
\uc774 \ubb38\uc81c\ub294 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d(DP)\uc744 \uc0ac\uc6a9\ud558\uc5ec \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. DP\ub294 \ubcf5\uc7a1\ud55c \ubb38\uc81c\ub97c \uc791\uc740 \ubd80\ubd84 \ubb38\uc81c\ub85c \ub098\ub204\uc5b4 \ud574\uacb0\ud558\uc5ec \ud6a8\uc728\uc131\uc744 \ub192\uc774\ub294 \uae30\ubc95\uc785\ub2c8\ub2e4. \uc774 \uacbd\uc6b0, DP \ubc30\uc5f4\uc744 \uc0ac\uc6a9\ud558\uc5ec \uac01 \ubb38\uc790 \uc30d \uac04\uc758 LCS \uae38\uc774\ub97c \uc800\uc7a5\ud558\uace0 \uacc4\uc0b0\ud569\ub2c8\ub2e4.<\/p>\n
\uc6b0\uc120, \ub450 \ubb38\uc790\uc5f4 A\uc640 B\uc758 \uae38\uc774\uc5d0 \ub530\ub77c 2\ucc28\uc6d0 DP \ubc30\uc5f4\uc744 \ucd08\uae30\ud654\ud569\ub2c8\ub2e4. DP[i][j]\ub294 A\uc758 \uccab i\uac1c \ubb38\uc790\uc640 B\uc758 \uccab j\uac1c \ubb38\uc790\uc758 \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc758 \uae38\uc774\ub97c \ub098\ud0c0\ub0c5\ub2c8\ub2e4.<\/p>\n
\n int[,] dp = new int[N + 1, M + 1];\n <\/code><\/pre>\n3. DP \uc0c1\ud0dc \uc804\uc774<\/h3>\n
DP \uaddc\uce59\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n
\n- \ub9cc\uc57d 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<\/code><\/li>\n- \ub9cc\uc57d A\uc758 i\ubc88\uc9f8 \ubb38\uc790\uc640 B\uc758 j\ubc88\uc9f8 \ubb38\uc790\uac00 \ub2e4\ub974\uba74:
dp[i][j] = Math.Max(dp[i - 1][j], dp[i][j - 1])<\/code><\/li>\n<\/ul>\n4. \ucd5c\uc885 \uacb0\uacfc<\/h3>\n
DP \ubc30\uc5f4\uc774 \ucc44\uc6cc\uc9c4 \ud6c4, dp[N][M]<\/code>\uc5d0\ub294 \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc758 \uae38\uc774\uac00 \uc800\uc7a5\ub429\ub2c8\ub2e4.<\/p>\n\ucf54\ub4dc \uad6c\ud604<\/h2>\n\n using System;\n\n class Program\n {\n static void Main(string[] args)\n {\n string A = \"ABCBDAB\";\n string B = \"BDCAB\";\n int N = A.Length;\n int M = B.Length;\n\n int[,] dp = new int[N + 1, M + 1];\n\n for (int i = 1; i <= N; i++)\n {\n for (int j = 1; j <= M; j++)\n {\n if (A[i - 1] == B[j - 1])\n {\n dp[i, j] = dp[i - 1, j - 1] + 1;\n }\n else\n {\n dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);\n }\n }\n }\n\n Console.WriteLine(\"\ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc758 \uae38\uc774: \" + dp[N, M]);\n }\n }\n <\/code><\/pre>\n\ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4<\/h2>\n\uc608\uc81c \uc785\ub825<\/h3>\n\n A: ABCBDAB\n B: BDCAB\n <\/code><\/pre>\n\uc608\uc81c \ucd9c\ub825<\/h3>\n\n \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc758 \uae38\uc774: 4\n <\/code><\/pre>\n\uc2dc\uac04 \ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
\uc774 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(N * M)\uc774\uba70, \uacf5\uac04 \ubcf5\uc7a1\ub3c4 \ub610\ud55c O(N * M)\uc785\ub2c8\ub2e4. \uc774\ub97c \ud1b5\ud574 \ub450 \ubb38\uc790\uc5f4\uc758 \uae38\uc774\uac00 1000\uc77c \ub54c\ub3c4 \ucda9\ubd84\ud788 \uc131\ub2a5\uc744 \ub9cc\uc871\ud558\ub294 \uc54c\uace0\ub9ac\uc998\uc785\ub2c8\ub2e4.<\/p>\n
\uacb0\ub860<\/h2>\n
\ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4(LCS) \ubb38\uc81c\ub294 \ucef4\ud4e8\ud130 \uacfc\ud559\uc758 \uc5ec\ub7ec \ubd84\uc57c\uc5d0\uc11c \uc5b4\ub5bb\uac8c \uc54c \uc218 \uc788\ub294\uc9c0\ub97c \ubcf4\uc5ec\uc8fc\ub294 \uc8fc\uc694 \ubb38\uc81c\uc785\ub2c8\ub2e4. \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d\uc744 \uc0ac\uc6a9\ud558\uc5ec \ud6a8\uc728\uc801\uc73c\ub85c \ud574\uacb0\ud560 \uc218 \uc788\uc74c\uc744 \ud655\uc778\ud588\uc2b5\ub2c8\ub2e4. \uc774 \ubc29\ubc95\uc740 \uc2e4\uc81c \ucf54\ub529\ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc218\uc2dc\ub85c \ub4f1\uc7a5\ud558\ubbc0\ub85c, \uc798 \uc774\ud574\ud558\uace0 \uc5f0\uc2b5\ud558\ub294 \uac83\uc774 \uc911\uc694\ud569\ub2c8\ub2e4.<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"