1. \uc11c\ub860<\/h2>\n
\n \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c \ud574\uacb0\uc758 \ud575\uc2ec\uc740 \ub2e4\uc591\ud55c \ubb38\uc81c\ub97c \uc774\ud574\ud558\uace0 \ud574\uacb0\ud558\ub294 \ub2a5\ub825\uc744 \uae30\ub974\ub294 \uac83\uc785\ub2c8\ub2e4. \uadf8 \uc911\uc5d0\uc11c\ub3c4 \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4(Longest Common Subsequence, LCS) \ubb38\uc81c\ub294 \uc5ec\ub7ec \uc54c\uace0\ub9ac\uc998 \uc2dc\ud5d8\uc5d0\uc11c \uc790\uc8fc \ub4f1\uc7a5\ud558\ub294 \uae30\ubcf8\uc801\uc778 \ubb38\uc81c\uc785\ub2c8\ub2e4. \uc774 \uae00\uc5d0\uc11c\ub294 \ucf54\ud2c0\ub9b0\uc744 \uc774\uc6a9\ud558\uc5ec LCS \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \uacfc\uc815\uc744 \uc790\uc138\ud788 \uc0b4\ud3b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n<\/section>\n \n \uc8fc\uc5b4\uc9c4 \ub450 \ubb38\uc790\uc5f4\uc774 \uc788\uc744 \ub54c, \uc774\ub4e4 \ubb38\uc790\uc5f4\uc5d0\uc11c \uac01\uac01\uc758 \ubb38\uc790\ub97c \uc0ad\uc81c\ud558\uc9c0 \uc54a\uace0 \uacf5\ud1b5\uc73c\ub85c \ub098\ud0c0\ub098\ub294 \uac00\uc7a5 \uae34 \ubd80\ubd84 \uc218\uc5f4\uc758 \uae38\uc774\ub97c \uad6c\ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. \ub2e4\uc2dc \ub9d0\ud574, \ub450 \ubb38\uc790\uc5f4\uc5d0\uc11c \ubb38\uc790\uc758 \uc21c\uc11c\ub97c \uc720\uc9c0\ud558\uba74\uc11c \uacf5\ud1b5\uc73c\ub85c \ucc3e\uc544\ub0bc \uc218 \uc788\ub294 \uac00\uc7a5 \uae34 \uc11c\ube0c \uc2dc\ud000\uc2a4\ub97c \ucc3e\ub294 \uac83\uc774\uc8e0.\n <\/p>\n \n LCS \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud55c \uc77c\ubc18\uc801\uc778 \uc811\uadfc\ubc95\uc740 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d(Dynamic Programming)\uc785\ub2c8\ub2e4. \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d\uc740 \ubcf5\uc7a1\ud55c \ubb38\uc81c\ub97c \ub354 \uac04\ub2e8\ud55c \ud558\uc704 \ubb38\uc81c\ub85c \ub098\ub204\uc5b4 \ud574\uacb0\ud558\ub294 \ubc29\ubc95\ub860\uc785\ub2c8\ub2e4. \uc5ec\uae30\uc5d0\uc120 \ub450 \ubb38\uc790\uc5f4\uc758 \uac01 \ubb38\uc790\ub97c \ube44\uad50\ud558\uba70, \ucd5c\ub300 \uae38\uc774\ub97c \uacc4\uc0b0\ud574 \ub098\uac11\ub2c8\ub2e4.\n <\/p>\n \n \uba3c\uc800, \ub450 \ubb38\uc790\uc5f4\uc758 \uae38\uc774\ub97c \uac01\uac01 \n \ub450 \ubb38\uc790\uc5f4\uc758 \ub9c8\uc9c0\ub9c9 \ubb38\uc790\uae4c\uc9c0 \ube44\uad50\ud558\uba70 \ub2e4\uc74c\uc758 \uaddc\uce59\uc73c\ub85c \ud14c\uc774\ube14\uc744 \ucc44\uc6cc \ub098\uac11\ub2c8\ub2e4:\n <\/p>\n \n \uc774 \uacfc\uc815\uc744 \ud1b5\ud574 \uc644\uc131\ub41c \n \uc774\uc81c \uc774\ub860\uc801\uc778 \uc124\uba85\uc744 \ubc14\ud0d5\uc73c\ub85c \ucf54\ud2c0\ub9b0\uc744 \uc774\uc6a9\ud574 \uc2e4\uc81c\ub85c LCS\ub97c \uacc4\uc0b0\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n \n \uc704\uc758 \ucf54\ub4dc\ub294 O(m * n)\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\uc640 O(m * n)\uc758 \uacf5\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9d1\ub2c8\ub2e4. \ub530\ub77c\uc11c \ubb38\uc790\uc5f4\uc758 \uae38\uc774\uac00 \uae38\uc5b4\uc9c8\uc218\ub85d \uc131\ub2a5\uc774 \uac10\uc18c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uadf8\ub7ec\ub098 LCS \ubb38\uc81c\ub294 \ub2e4\uc591\ud55c \ucd5c\uc801\ud654 \uae30\ubc95\uc744 \ud1b5\ud574 \uac1c\uc120\ub420 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n \n \ud604\uc7ac\ub294 2D \ubc30\uc5f4\uc744 \uc0ac\uc6a9\ud588\uc9c0\ub9cc, \uc2e4\uc81c\ub85c\ub294 \uc774\uc804 \ud589\uc758 \uac12\ub9cc \ud544\uc694\ud558\ubbc0\ub85c 1D \ubc30\uc5f4\ub85c\ub3c4 \ud574\uacb0 \uac00\ub2a5\ud569\ub2c8\ub2e4. \uc774\ub97c \ud1b5\ud574 \uacf5\uac04 \ubcf5\uc7a1\ub3c4\ub97c O(n)\uc73c\ub85c \uc904\uc77c \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n \n \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4 \ubb38\uc81c\ub294 \uc54c\uace0\ub9ac\uc998 \uacf5\ubd80\uc640 \ucf54\ub4dc \ud14c\uc2a4\ud2b8\uc5d0\uc11c \ub9e4\uc6b0 \uc911\uc694\ud55c \ubb38\uc81c\uc785\ub2c8\ub2e4. \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d\uc744 \ud65c\uc6a9\ud558\uc5ec \ubb38\uc81c\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \ud574\uacb0\ud560 \uc218 \uc788\uc73c\uba70, \uc5ec\ub7ec \ucd5c\uc801\ud654 \uae30\ubc95\uc774 \uc788\uc74c\uc744 \uc54c\uac8c \ub418\uc5c8\uc2b5\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub97c \ud1b5\ud574 \uc54c\uace0\ub9ac\uc998\uc801 \uc0ac\uace0\ub97c \ubc1c\uc804\uc2dc\ud0a4\uace0 \ucf54\ud2c0\ub9b0 \ud504\ub85c\uadf8\ub798\ubc0d\uc744 \uc5f0\uc2b5\ud560 \uc218 \uc788\ub294 \uae30\ud68c\uac00 \ub418\uae38 \ubc14\ub78d\ub2c8\ub2e4.\n <\/p>\n<\/section>\n2. \ubb38\uc81c \uc124\uba85<\/h2>\n
\uc608\uc81c<\/h3>\n
\n
3. \ubb38\uc81c \ud574\uacb0\uc758 \uc811\uadfc\ubc95<\/h2>\n
3.1. \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d \ud14c\uc774\ube14 \uc815\uc758<\/h3>\n
m<\/code>, n<\/code>\uc774\ub77c\uace0 \ud560 \ub54c, dp[i][j]<\/code>\ub97c \ubb38\uc790\uc5f41\uc758 \ucc98\uc74c i<\/code>\uae00\uc790\uc640 \ubb38\uc790\uc5f42\uc758 \ucc98\uc74c j<\/code>\uae00\uc790\uae4c\uc9c0\uc758 LCS\uc758 \uae38\uc774\ub85c \uc815\uc758\ud569\ub2c8\ub2e4. \uc774 \ud14c\uc774\ube14\uc758 \ud06c\uae30\ub294 (m+1) x (n+1)<\/code>\uc785\ub2c8\ub2e4. \ud14c\uc774\ube14\uc758 \uccab \ubc88\uc9f8 \ud589\uacfc \uc5f4\uc740 0\uc73c\ub85c \ucd08\uae30\ud654\ud569\ub2c8\ub2e4.\n <\/p>\n3.2. \uc810\ud654\uc2dd \uc124\uc815<\/h3>\n
\n
dp[i][j] = dp[i-1][j-1] + 1<\/code><\/li>\ndp[i][j] = max(dp[i-1][j], dp[i][j-1])<\/code><\/li>\n<\/ul>\n3.3. \uacb0\uacfc \ucd94\ucd9c<\/h3>\n
dp<\/code> \ud14c\uc774\ube14\uc758 \ub9c8\uc9c0\ub9c9 \uc140 dp[m][n]<\/code>\uc5d0\ub294 \ub450 \ubb38\uc790\uc5f4\uc758 LCS \uae38\uc774\uac00 \uc800\uc7a5\ub429\ub2c8\ub2e4.\n <\/p>\n<\/section>\n4. \ucf54\ud2c0\ub9b0 \uad6c\ud604<\/h2>\n
\nfun longestCommonSubsequence(s1: String, s2: String): Int {\n val m = s1.length\n val n = s2.length\n val dp = Array(m + 1) { IntArray(n + 1) }\n\n for (i in 1..m) {\n for (j in 1..n) {\n if (s1[i - 1] == s2[j - 1]) {\n dp[i][j] = dp[i - 1][j - 1] + 1\n } else {\n dp[i][j] = maxOf(dp[i - 1][j], dp[i][j - 1])\n }\n }\n }\n\n return dp[m][n]\n}\n\nfun main() {\n val s1 = \"ABCBDAB\"\n val s2 = \"BDCAB\"\n println(\"\ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc758 \uae38\uc774: ${longestCommonSubsequence(s1, s2)}\")\n}\n <\/code><\/pre>\n<\/section>\n5. \ubd84\uc11d<\/h2>\n
5.1. \uacf5\uac04 \ud6a8\uc728\uc131 \uac1c\uc120<\/h3>\n
\nfun longestCommonSubsequenceOptimized(s1: String, s2: String): Int {\n val m = s1.length\n val n = s2.length\n val dp = IntArray(n + 1)\n\n for (i in 1..m) {\n val prev = IntArray(n + 1)\n for (j in 1..n) {\n if (s1[i - 1] == s2[j - 1]) {\n dp[j] = prev[j - 1] + 1\n } else {\n dp[j] = maxOf(dp[j - 1], prev[j])\n }\n prev[j] = dp[j]\n }\n }\n return dp[n]\n}\n <\/code><\/pre>\n<\/section>\n6. \uacb0\ub860<\/h2>\n