\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
\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
\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
\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
- \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- \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- \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
\n
- \uc8fc\uc5b4\uc9c4 \ub450 \ubb38\uc790\uc5f4 \ub300\uc2e0 \uc138 \uac1c\uc758 \ubb38\uc790\uc5f4\uc5d0\uc11c \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc744 \ucc3e\ub294 \ubb38\uc81c.<\/li>\n
- \ub300\uc18c\ubb38\uc790\ub97c \uad6c\ubd84\ud558\uc9c0 \uc54a\uace0 \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc744 \ucc3e\ub294 \ubb38\uc81c.<\/li>\n
- \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4\uc744 \uad6c\ud558\ub294 \ubaa8\ub4e0 \uac00\ub2a5\ud55c \uc870\ud569\uc744 \ucd9c\ub825\ud558\ub294 \ubb38\uc81c.<\/li>\n<\/ul>\n
\ub9fa\uc74c\ub9d0<\/h2>\n
\n \ucd5c\uc7a5 \uacf5\ud1b5 \ubd80\ubd84 \uc218\uc5f4 \ubb38\uc81c\ub294 \ucef4\ud4e8\ud130 \uacfc\ud559\uc758 \uc911\uc694\ud55c \uac1c\ub150 \uc911 \ud558\ub098\ub85c, \ub2e4\uc591\ud55c \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\uc5d0 \uc751\uc6a9\ub420 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
\n \ub3d9\uc801 \uacc4\ud68d\ubc95\uc744 \uc0ac\uc6a9\ud55c \uc774 \ubc29\uc2dd\uc744 \ud1b5\ud574 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \uac83\uc740 \ub354\uc6b1 \ubcf5\uc7a1\ud55c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ub370 \ub3c4\uc6c0\uc774 \ub420 \uac83\uc785\ub2c8\ub2e4. \ub2e4\uc591\ud55c \ubb38\uc81c\ub97c \ud480\uba70 \uc2e4\ub825\uc744 \ub2e4\uc838 \ubcf4\uc138\uc694!\n <\/p>\n<\/div>\n<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"