\ubcf8 \uac15\uc88c\uc5d0\uc11c\ub294 \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \ucd9c\uc81c\ub418\ub294 \ubb38\uc81c\uc778 “\ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4(Longest Common Subsequence, LCS)”\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. LCS \ubb38\uc81c\ub294 \ub450 \uac1c\uc758 \uc2dc\ud000\uc2a4\uac00 \uc8fc\uc5b4\uc84c\uc744 \ub54c, \ub450 \uc2dc\ud000\uc2a4\uc5d0\uc11c \uac01\uac01\uc758 \uc694\uc18c\uc758 \uc0c1\ub300\uc801 \uc21c\uc11c\ub97c \uc720\uc9c0\ud558\uba74\uc11c \ub9cc\ub4e4 \uc218 \uc788\ub294 \uac00\uc7a5 \uae34 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc744 \ucc3e\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4.<\/p>\n
\ub450 \uac1c\uc758 \ubb38\uc790\uc5f4 \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc758 \uae38\uc774 : 4<\/p>\n \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d(Dynamic Programming) \uc811\uadfc \ubc29\uc2dd\uc744 \uc0ac\uc6a9\ud560 \uac83\uc785\ub2c8\ub2e4. \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d\uc740 \ubb38\uc81c\ub97c \uc791\uc740 \ubd80\ubd84 \ubb38\uc81c\ub85c \ub098\ub204\uc5b4 \ud574\uacb0\ud558\uace0, \uadf8 \uacb0\uacfc\ub97c \uc800\uc7a5\ud558\uc5ec \ud6a8\uc728\uc801\uc73c\ub85c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ubc29\ubc95\uc785\ub2c8\ub2e4.<\/p>\n \ubb38\uc790\uc5f4 \ubc30\uc5f4\uc758 \uac01 \uc694\uc18c\ub294 \ucd08\uae30\uac12\uc73c\ub85c 0\uc73c\ub85c \uc124\uc815\ud569\ub2c8\ub2e4.<\/p>\n<\/div>\n \uc774\uc81c \uc774\ucc28\uc6d0 \ubc30\uc5f4 \ucd5c\uc885\uc801\uc73c\ub85c \uc774\uc81c \uc774 \uacfc\uc815\uc744 \uc790\ubc14 \ucf54\ub4dc\ub85c \uad6c\ud604\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n \uc704 \ucf54\ub4dc\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \ubc29\uc2dd\uc73c\ub85c \uc791\ub3d9\ud569\ub2c8\ub2e4.<\/p>\n \uc785\ub825:<\/strong> \ucd9c\ub825:<\/strong> \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc758 \uae38\uc774: \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc744 \ucc3e\ub294 \ubc29\ubc95\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uc558\uc2b5\ub2c8\ub2e4. \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d \uae30\ubc95\uc744 \ud65c\uc6a9\ud558\ub294 \uac83\uc774 \uc5bc\ub9c8\ub098 \ud6a8\uacfc\uc801\uc77c \uc218 \uc788\ub294\uc9c0\ub97c \ubcf4\uc5ec\uc8fc\uc5c8\uc2b5\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub294 \ub2e4\uc591\ud55c \ubd84\uc57c\uc5d0\uc11c \ud65c\uc6a9\ub420 \uc218 \uc788\uc73c\uba70, \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ud480 \ub54c \uae30\ubcf8\uc801\uc73c\ub85c \uc54c\uc544\ub450\uc5b4\uc57c \ud560 \ub0b4\uc6a9\uc785\ub2c8\ub2e4.<\/p>\n \ub354 \ub098\uc544\uac00 \ubcf8 \uac15\uc88c\uc5d0\uc11c \uacf5\uc720\ub41c \ucf54\ub4dc\ub97c \ubc14\ud0d5\uc73c\ub85c \ub2e4\ub978 \ubb38\uc790\uc5f4 \uc870\ud569\uc5d0 \ub300\ud574\uc11c\ub3c4 \uc2e4\ud5d8\ud574\ubcf4\uba70, \uc774\ub860\uc744 \ub354\uc6b1 \uc2ec\ud654\uc2dc\ud0ac \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c \ud480\uc774 \ub2a5\ub825\uc744 \ud0a4\uc6b0\ub294 \ub370 \ud070 \ub3c4\uc6c0\uc774 \ub418\uae30\ub97c \ubc14\ub78d\ub2c8\ub2e4.<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"str1<\/code>\uacfc str2<\/code>\uac00 \uc8fc\uc5b4\uc9c8 \ub54c, \uc774 \ub450 \ubb38\uc790\uc5f4\uc758 \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc758 \uae38\uc774\ub97c \uad6c\ud558\uc138\uc694.<\/p>\n\uc785\ub825<\/h3>\n
\n
str1<\/code> : “AGGTAB”<\/li>\nstr2<\/code> : “GXTXAYB”<\/li>\n<\/ul>\n\ucd9c\ub825<\/h3>\n
\ubb38\uc81c \ud480\uc774 \uacfc\uc815<\/h2>\n
1\ub2e8\uacc4: \uc774\ucc28\uc6d0 \ubc30\uc5f4 \ucd08\uae30\ud654<\/h3>\n
str1<\/code>\uacfc str2<\/code>\uc758 \uae38\uc774\ub97c \uae30\ubc18\uc73c\ub85c \uc774\ucc28\uc6d0 \ubc30\uc5f4 dp<\/code>\ub97c \uc0dd\uc131\ud569\ub2c8\ub2e4. \uc774 \ubc30\uc5f4\uc758 \ud06c\uae30\ub294 (m+1) x (n+1)<\/code>\uc774\uba70, <\/p>\n\n
m<\/code> : str1<\/code>\uc758 \uae38\uc774<\/li>\nn<\/code> : str2<\/code>\uc758 \uae38\uc774<\/li>\n<\/ul>\n2\ub2e8\uacc4: \uc774\ucc28\uc6d0 \ubc30\uc5f4 \ucc44\uc6b0\uae30<\/h3>\n
dp<\/code>\ub97c \ucc44\uc6cc \ub098\uac11\ub2c8\ub2e4. \ubb38\uc790\uc5f4\uc758 \uac01 \uae00\uc790\ub97c \ube44\uad50\ud558\uba74\uc11c \uc9c4\ud589\ud569\ub2c8\ub2e4.<\/p>\n\n
dp[i][j] = dp[i-1][j-1] + 1<\/code>\ub85c \uc124\uc815\ud569\ub2c8\ub2e4.<\/li>\ndp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])<\/code>\ub85c \uc124\uc815\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\ndp[m][n]<\/code>\uc758 \uac12\uc774 \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc758 \uae38\uc774\uac00 \ub429\ub2c8\ub2e4.<\/p>\n<\/div>\n3\ub2e8\uacc4: \ucf54\ub4dc \uad6c\ud604<\/h3>\n
\npublic class LongestCommonSubsequence {\n public static int lcs(String str1, String str2) {\n int m = str1.length();\n int n = str2.length();\n int[][] dp = new int[m + 1][n + 1];\n\n for (int i = 1; i <= m; i++) {\n for (int j = 1; j <= n; j++) {\n if (str1.charAt(i - 1) == str2.charAt(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[m][n];\n }\n\n public static void main(String[] args) {\n String str1 = \"AGGTAB\";\n String str2 = \"GXTXAYB\";\n System.out.println(\"\ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc758 \uae38\uc774: \" + lcs(str1, str2));\n }\n}\n <\/code><\/pre>\n\ucf54\ub4dc \ubd84\uc11d<\/h2>\n
\n
dp<\/code> \ubc30\uc5f4\uc744 \uc0dd\uc131\ud569\ub2c8\ub2e4.<\/li>\n\uc2e4\ud589 \uacb0\uacfc<\/h2>\n
str1 = \"AGGTAB\"<\/code>, str2 = \"GXTXAYB\"<\/code><\/p>\n4<\/code><\/p>\n<\/div>\n\uacb0\ub860<\/h2>\n