백준 9251 LCS 문제풀이

문제 

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

9251번: LCS

 

문제 접근 방식

가장 긴 부분 수열의 길이를 구하는 문제이며, 이를 구하기 위해서는 이전 항들과의 관계를 통해서 풀이를 도출해야함을 알 수 있다. 

이전 항과의 관계를 통해 푸는 문제이기에 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를 구현할 수도 있다는 것을 경험했다.