{"id":33784,"date":"2024-11-01T09:20:20","date_gmt":"2024-11-01T09:20:20","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33784"},"modified":"2024-11-01T12:27:06","modified_gmt":"2024-11-01T12:27:06","slug":"%ed%8c%8c%ec%9d%b4%ec%8d%ac-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%ea%b0%80%ec%9e%a5-%ea%b8%b4-%ea%b3%b5%ed%86%b5-%eb%b6%80%eb%b6%84-%ec%88%98%ec%97%b4-%ec%b0%be%ea%b8%b0","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33784\/","title":{"rendered":"Python coding test course, finding the longest common subsequence"},"content":{"rendered":"

<\/p>\n

Problem Description<\/h2>\n

\n Given two strings, this is a problem of finding the Longest Common Subsequence (LCS) between them. A common subsequence refers to characters that appear in both strings while maintaining their order. The goal is to find the maximum length of such a subsequence.\n <\/p>\n

Example<\/h2>\n

Input<\/h3>\n

\n String A: ABCBDAB<\/strong>
\n String B: BDCAB<\/strong>\n<\/p>\n

Output<\/h3>\n

\n Longest Common Subsequence: BDAB<\/strong>\n<\/p>\n

Approach to the Problem<\/h2>\n

\n To solve the LCS problem, we can use Dynamic Programming. Dynamic Programming is a technique that solves problems by storing already computed results and reusing them. To find the LCS, we store the length of the subsequence based on the comparison results of each character in the two strings.\n <\/p>\n

Finding LCS using Dynamic Programming<\/h2>\n

Step 1: Initialize the DP Table<\/h3>\n

\n Let the lengths of the two strings be m<\/code> and n<\/code>, we create and initialize a 2D DP array of size (m + 1) x (n + 1)<\/code>. Each element of the DP array stores the length of the common subsequence found in the two strings.\n <\/p>\n

Step 2: Fill the DP Table<\/h3>\n

\n We fill in the DP table while comparing each character of the two strings. If the characters match, the LCS length including that character is DP[i-1][j-1] + 1<\/code>. If they do not match, we use DP[i][j] = max(DP[i-1][j], DP[i][j-1])<\/code> to record the length of the LCS found so far.\n <\/p>\n

Step 3: Extract LCS Length and String<\/h3>\n

\n After filling the DP table, check DP[m][n]<\/code> to get the length of the longest common subsequence, and extract the actual common subsequence using this length. The extraction process is carried out by tracing back through the table to find common characters.\n <\/p>\n

Algorithm Code <\/h2>\n
\n    \ndef lcs(A, B):\n    # Step 1: Initialize the DP array\n    m = len(A)\n    n = len(B)\n    dp = [[0] * (n + 1) for _ in range(m + 1)]\n\n    # Step 2: Fill the DP array\n    for i in range(1, m + 1):\n        for j in range(1, n + 1):\n            if A[i - 1] == B[j - 1]:\n                dp[i][j] = dp[i - 1][j - 1] + 1\n            else:\n                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])\n\n    # Step 3: Get LCS length\n    lcs_length = dp[m][n]\n\n    # Extract LCS string\n    lcs_str = []\n    i, j = m, n\n    while i > 0 and j > 0:\n        if A[i - 1] == B[j - 1]:\n            lcs_str.append(A[i - 1])\n            i -= 1\n            j -= 1\n        elif dp[i - 1][j] >= dp[i][j - 1]:\n            i -= 1\n        else:\n            j -= 1\n\n    lcs_str.reverse()  # Reverse the extracted string to restore original order\n    return lcs_length, ''.join(lcs_str)\n\n# Test code\nA = \"ABCBDAB\"\nB = \"BDCAB\"\nlength, lcs_string = lcs(A, B)\nprint(\"LCS length:\", length)\nprint(\"LCS string:\", lcs_string)\n    <\/code>\n    <\/pre>\n
Complexity Analysis<\/h2>\n
\n        The time complexity of this algorithm is O(m * n). Since each character needs to be compared, the result is a product of the lengths of the two strings. The space complexity is also O(m * n), determined by the size of the created DP table. However, there are ways to reduce the size of the DP table. For example, since only the previous row’s data is needed, it can be implemented using two 1D arrays.\n    <\/p>\n
Optimized Code Example<\/h3>\n
\n    \ndef optimized_lcs(A, B):\n    m = len(A)\n    n = len(B)\n    dp = [0] * (n + 1)\n\n    for i in range(1, m + 1):\n        current = 0  # Value at the current position\n        for j in range(1, n + 1):\n            temp = dp[j]\n            if A[i - 1] == B[j - 1]:\n                dp[j] = current + 1\n            else:\n                dp[j] = max(dp[j], dp[j - 1])\n            current = temp  # Store the value from the previous row\n\n    return dp[n]\n\n# Optimized test\nlength = optimized_lcs(A, B)\nprint(\"LCS length:\", length)\n    <\/code>\n    <\/pre>\n
Conclusion<\/h2>\n
\n        In this lecture, we dealt with the problem of finding the Longest Common Subsequence (LCS). This problem is a great example of how to easily utilize string processing and dynamic programming concepts. The LCS problem is widely used in various fields, especially in gene analysis and finding identical sequences, so understanding and implementing the algorithm is very useful for coding tests and practical applications.\n    <\/p>\n
References<\/h2>\n