[ 백준 9252 ] LCS 2 - Python

문제 보기

이 문제는 DP 문제이다.

 

LCS(Longest Common Subsequence, 최장 공통부분 수열)는 DP 문제로 유명하기 때문에 문제 이름을 보자마자 DP임을 유추할 수 있었다.

 

• 문제 접근
  • 2차원 dp를 활용하고자 하였다.
  • 행은 첫 번째 문자열, 열은 두 번째 문자열에 대한 정보를 나타낸다.
  • dp [row][col]
    - 첫 번째 문자열 row 길이, 두 번째 문자열 col 길이에 해당하는 문자열로 만들 수 있는 공통부분 수열
• 알고리즘
  • 첫 번째 문자열과 두 번째 문자열 길이를 이용해서 2차원 for문을 돈다.
    - 바깥쪽 for문은 첫 번째 문자열 인덱스(i)를 나타낸다.
    - 안쪽 for문은 두 번째 문자열 인덱스(j)를 나타낸다.
  • 첫 번째 문자열의 i번째와 두 번째 문자열의 j번째의 문자를 비교한다.
    - 일치한다면 dp[i][j] = dp[i - 1][j - 1] + 문자
    - 일치하지 않는다면 dp[i][j] = dp[i - 1][j]와 dp[i][j - 1]에서 길이가 긴 것을 대입한다.

코드

import copy

if __name__ == "__main__":

    # input
    string_1 = list(input())
    string_2 = list(input())

    # dp
    dp = [[""] * (len(string_2) + 1) for _ in range(len(string_1) + 1)]
    for i in range(1, len(string_1) + 1):
        for j in range(1, len(string_2) + 1):
            if string_1[i - 1] == string_2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + string_1[i - 1]
            else:
                if len(dp[i - 1][j]) >= len(dp[i][j - 1]):
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = dp[i][j - 1]

    if len(dp[-1][-1]) == 0:
        print(0)
    else:
        print(len(dp[-1][-1]))
        print(dp[-1][-1])