[BOJ] 9251, 15482. LCS, 한글 LCS

www.acmicpc.net/problem/15482

15482번: 한글 LCS

www.acmicpc.net/problem/9251

9251번: LCS

문제: 문자열 2개에서 최장 공통 부분 수열을 찾아라.

 

문제 이해하기!!

LCS 문제입니다. (Longest Common Subsequence라고 하죠)

문제 제목에 한글 LCS 문제라고 되어있기 때문에 쉽게 알 수 있었어요!

두 문제는 영어랑 한글이 다른 것 뿐인데, 파이썬에서는 형에 대한 생각을 안해도 되니깐!! 둘 다 풀립니다.

자, 그럼 어떻게 풀어야 할까?

처음엔 완전탐색을 한다면 O(n**3)의 시간복잡도가 나옵니다.

그럼 이걸 줄여야겠죠? 문자열의 길이가 1000이니까 O(n**2)로만 줄여도 답이 나옵니다!

줄이기 위해서는 다이나믹 프로그래밍으로 풀면되는데요.

 

그 방식을 설명하자면!!

1. 하나의 0으로 된 dp배열을 만듭니다.

2. 한 문자열(a)을 돌면서 다른 문자열(b)에서 한 문자열(a) 1번째와 같은 것이 있는지 확인합니다.

3. 같다면 다른 문자열(b) 인덱스까지 저장된 dp배열 중 제일 컸던 것에 +1을 해서 dp배열에 수정해줍니다.

4. dp 배열 중 가장 큰 값을 출력해주면 됩니다.

끝~~!!

 

코드:

def s():
    s1, s2 = input(), input()
    dp = [0] * 1000
    for i in range(len(s1)):
        max_dp = 0
        for j in range(len(s2)):
            if max_dp < dp[j]:
                max_dp = dp[j]
            elif s1[i] == s2[j]:
                dp[j] = max_dp + 1
    print(max(dp))
s()