✓

태그:

26. 동적 계획법과 최단거리 역추적 CLASS 5 ESSENTIAL

주어진 문자열의 부분 문자열의 최장 공통 부분 수열의…

풀이 비스무리한거 보기

두 문자열의 최장 공통 부분 수열을 찾는 문제입니다. 최장 공통 부분 수열은 연속되지 않아도 된다는 것이 문제에 나와있기 때문에 이를 이용하여 DP 배열을 구성하는 방법을 생각해낼 수 있습니다.

DP 배열은 2차원 배열로 구성하되, 각 원소의 의미는 첫 문자열의 길이 i의 prefix, 두 문자열의 길이 j의 prefix의 LCS를 저장합니다. 이제 DP 배열을 확장시켜가는데, 아래의 관계식을 사용하여 DP 배열을 채웁니다.

if A[i] == B[j]:
    dp[i][j] = dp[i - 1][j - 1] + A[i]
else:
    dp[i][j] = longer(dp[i - 1][j], d[i][j - 1])

이를 모두 채운 후 가장 끝에 있는 원소를 그대로 출력하면 됩니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-02-26 22:05:11

---