문제
https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
문제 접근 방식
가장 긴 부분 수열의 길이를 구하는 문제이며, 이를 구하기 위해서는 이전 항들과의 관계를 통해서 풀이를 도출해야함을 알 수 있다.
이전 항과의 관계를 통해 푸는 문제이기에 DP 로 판단을 하고 점화식을 세우는데 집중했다.
점화식의 경우 시행 착오를 거쳐서 도출을 했는데 그 과정을 공유하겠다.
맨 처음 점화식
d[ i ] = 수열 s1의 i 번째로 만들 수 있는 최대 수열의 길이와 그때의 s2의 항 j
위와 같이 일차원 배열을 통해 문제를 풀려고 하면 O(n^3) 의 시간 복잡도가 걸리는 코드가 작성되며 n의 최댓값이 1000이므로 통과를 하지 못한다. 점화식을 어떻게 세워야하지 고민하던 와중에, 위 정의에서 결과에 포함되어 있던 j를 입력으로 가져와도 괜찮을 것 같다는 생각이 들었다. 이런 흐름으로 두번째 점화식을 세워보았다.
두 번째 점화식
d[ i ][ j ] = s1의 i 번째 항과 s2의 j 번째 항을 포함해서 만들 수 있는 부분수열의 최대 길이
이전 DP문제들에서 특정 위치의 항을 포함시켜줘야 점화식이 완성되었기 때문에 이번에도 그렇게 정의를 했다.
이렇게 세울 경우, i 번째와 j 번째가 같지 않은 경우 d[ i ][ j ]가 이전 수열에 대한 정보를 갖지 않게 되기 때문에 누적이 되지 않는다. 즉, 메모이제이션이 제대로 되지 않는다. 여기서 i 번째를 포함시키고 말고는 문제의 특정에 따라 달라진다는 것을 알게 되었다.
아무튼, 정의가 잘못되었으므로 다시 수정했다.
마지막 점화식
d[ i ][ j ] = s1의 i 번째 항과 s2의 j 번째 항까지 부분 수열의 최대 길이
이렇게 작성하는 경우 d[ i ][ j ]는 이전 항들의 값을 활용하여 값을 누적시킬 수 있다.
구체적인 점화식은 아래와 같다.
d[i][j]=d[i-1][j-1] (s1[i]==s2[j]일 경우)
d[i][j]=max(d[i-1][j],d[i][j-1]) (s1[i]!=s2[j]일 경우)
위와 같이 점화식을 세웠고 예시로 검증하여 제대로된 점화식임을 알 수 있었다.
시간 복잡도
두 수열(각 수열의 길이 = n,m) 을 모두 순회해야하기 때문에 O(nm) 이 걸리며 n,m의 최대값이 1000이므로 시간내에 동작하는 것을 알 수있다.
코드
if __name__=='__main__':
s1=list(input())
s2=list(input())
s1.insert(0,'')
s2.insert(0,'')
n=len(s1)
m=len(s2)
# d[i][j]= i,j 번째 위치로 만들 수 있는 최대 부분 수열의 길이
d=[[0 for _ in range(m)] for _ in range(n)]
for i in range(1,n):
for j in range(1,m):
if s1[i]==s2[j]:
d[i][j]=d[i-1][j-1]+1
else:
d[i][j]=max(d[i-1][j],d[i][j-1])
print(d[n-1][m-1])
회고
저번 dp 들을 풀면서 점화식을 정의할 때, i 번째 항을 포함하도록 정의해야한다고 생각했는데 잘못된 일반화였다. 문제마다 다르며 정의를 하는데 있어 하나의 옵션이라고 생각하면 되겠다. 또한, 이 문제를 통해 이차원 배열을 사용하여 DP를 구현할 수도 있다는 것을 경험했다.
'문제풀이 > 백준' 카테고리의 다른 글
백준 1753 최단경로 문제풀이 (1) | 2024.01.13 |
---|---|
백준 9251 점프 문제풀이 (1) | 2024.01.11 |
백준 11053 [가장 긴 증가하는 부분 수열] 문제풀이 (0) | 2024.01.10 |
백준 1912 연속합 문제풀이 (0) | 2024.01.08 |
백준 2579 계단오르기 문제풀이 (1) | 2024.01.08 |