백준 9251번 LCS 파이썬

2020.10.20	2021.03.09
틀림	맞은줄 알고 있었지만 틀림 뭐지?????? 이때 풀이도 틀린거임 (원리 잘못 이해 다시 풀자)

알고리즘 자체에 익숙하지 않다고 많이 반성하게 된 문제..

아직 난 잘 모르나보다,다이나믹 프로그래밍 수식만 알았으면 쉽게 맞출수 있는 문제였는데..

아직 모자르다.

 

 

---

문제

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

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

입력

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

출력

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

 

 

---

문제풀이 핵심 아이디어

• 두 수열이 주어졌을때, 두 수열 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾아야합니다.
• 가장 긴 공통부분 수열 문제는 대표적인 동적 프로그래밍 문제이다.
• 두 수열의 길이가 N 미만일때, 시간복잡도 O(n2) 으로 문제를 해결할 수 있습니다.
• 두 수열을 각각 X, Y라고 합시다.
• D[i][j] = X[0 ... i] 와 Y[0 ... j ]의 공통 부분 수열의 최대 길이
• 두 문자열의 길이를 조금씩 늘려가며 확인하여,, 공통부분 수열의 최대 길이를 계산합니다.
•  

x= input()
y = input()

dp = [[0] * (len(y)+1) for _ in range(len(x)+1)]

for i in range(1, len(x)+1):
	for j in range(1, len(y)+1):
    	if x[i-1] == y[j-1]:
        	dp[i][j] = dp[i-1][j-1] +1
        else:
        	dp[i][j] = max(dp[i-1][j-1] , dp[i-1][j])

print(dp[len(x)][len(y)])