[백준] 9251번 LCS [Python] - 다이나믹, 문자열

LCS$($Longest Common Subsequence, 최장 공통 부분 수열$)$문제

최장 공통 부분 수열

 

문제

LCS$($Longest Common Subsequence, 최장 공통 부분 수열$)$문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

https://www.acmicpc.net/problem/9251

 

한 단어의 철자를 순서대로 다른 단어의 철자와 비교하면서 같은

철자가 있으면 공통 부분 수열의 원소가 되므로 +1을 해주고,

다른 철자는 수열에 포함 되지 않아서 길이에 영향을 미치지 않기 때문에

이전 상태의 수열의 길이와 같다고 생각하면 된다.

 

수열의 길이를 최댓값으로 업데이트를 잘 진행해 나가면 문제를 풀 수 있다.

 

 

1차원 리스트에 수열의 길이를 업데이트 하는 방식

import sys
input = sys.stdin.readline

def main():
    s1 = input().rstrip()
    s2 = input().rstrip()
	
    # 수열의 길이를 저장할 리스트
    dp = [0] * 1000
	
    # s1 과 s2의 철자를 하나씩 비교 >> 같으면 길이 + 1
    for a in s1:
        c = 0
        for i, b in enumerate(s2):
            # s2가 이전 s1의 철자까지 비교했을 때 저장해둔 수열의 길이 최신화
            if c < dp[i]:
                c = dp[i]
            
            # 철자가 같으면 + 1
            elif b == a:
                dp[i] = c + 1
	
    # 최댓값 출력
    print(max(dp))

if __name__ == "__main__":
    main()

 

 

2차원 리스트에 두 단어를 비교하면서 수열의 길이를 구하는 코드

import sys
input = sys.stdin.readline

def main():
    s1 = input().rstrip()
    s2 = input().rstrip()
    n1, n2 = len(s1) + 1, len(s2) + 1

    dp = [[0]*(n1) for _ in range(n2)]

	# s2의 철자 하나씩 비교해서
    for i in range(1, n2):
        s = s2[i-1]
		
        for j in range(1, n1):
	        # s1의 철자와 같은 값이 있으면: 수열의 길이 += 1
            if s == s1[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            # 없으면 가능한 최댓값으로 수열의 길이를 저장
            else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

	# 모든 철자를 대조한 후 마지막 값(최댓값) 출력
    print(dp[n2-1][n1-1])

if __name__ == "__main__":
    main()

 

예제 입력 1 

ACAYKP
CAPCAK

예제 출력 1 

4