https://cryosleep.tistory.com/17
LCS란? Longest Common Subsequence=최장 공통 부분순서
그냥 댕쉬움.
문제 풀면서 인지한 동적 프로그래밍, Tabulation의 테이블 작성의 공통점. 정답을 구하기 위해 당장에는 무의미한것까지 맨땅부터 차근차근 다 해보는 것이다(당장에는 무의미하지만 그 무의미한게 답을 구하게 해줌).
두개의 문자열을 비교하는 것이므로 2차원 배열임. x축=문자열A, y축=문자열B
배열은 문자열 각각의 길이에서의 LCS의 길이로 구성됨.
비교되는 2개의 문자열의 타겟 문자가 같으면 dp[i][j]=1+dp[i-1][j-1]
비교되는 2개의 문자열의 타겟 문자가 다르면 dp[i][j]=max(dp[i-1][j], dp[i][j-1]
from sys import stdin
#0-1배낭문제와는 달리 문자열간 비교이므로 어떤 물자열이 X축이고 Y축인지 중요하지 않음
def lcsSolution(a,b):
x=len(a)
y=len(b)
dp=[[0]*(x+1) for _ in range(y+1)]
for i in range(1, y+1):
for j in range(1, x+1):
if(a[j-1]==b[i-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[y][x])
def main():
a=stdin.readline().strip()
b=stdin.readline().strip()
lcsSolution(a,b)
main()
'알고리즘 > DP(Dynamic programming, 동적프로그래밍)' 카테고리의 다른 글
[백준] 2293 동전1 (0) | 2023.05.31 |
---|---|
[백준] 11066번: 파일 합치기 (0) | 2023.05.20 |
배낭채우기 문제 (0) | 2023.02.28 |
DP 기본문제인 막대기 자르기(백준에 없는문제) (0) | 2023.02.14 |
동적프로그래밍의 개념과 기본 개념을 잡아주는 피보나치 문제 (0) | 2023.02.14 |