[골드5]백준 9251번(LCS) - 코테공부 31일차(2025.02.23)

문제유형

동적 계획법

풀이 방법 도출 과정

1. 두 개의 부분 수열이 주어졌을 때, 두 수열 모두에 공통으로 등장하는 부분 수열의 개수를 구하는 문제이다.

2. 각 수열의 가능한 부분 수열의 수는 길이가 n일때 약 2에 n 개이다.  에를 들어 길이가 1000인 수열은 2에 1000개의 부분 수열을 갖게 되므로, 모든 경우를 생성해 비교하는 방식은 계산량이 기하급수적으로 증가해 실제로는 불가능하다.

3. 그렇다면 그리디 알고리즘으로 접근해보도록 하면 한 수열을 순회하며 특정 패턴(예: 'A', 그 다음 'AC' 등)을 차례로 찾아 나가는 그리디 방식은 일부 경우에는 효과적일 수 있으나. 항상 최적의 해답을 도출하지 못할 뿐 아니라, 최악의 경우 불필요한 중복 연산이 많아져 시간 복잡도가 크게 증가할 수 있다.

4.두 문자열의 공통 부분 수열 문제는 부분 문제의 중복이 존제하기 때문에, 이미 게산한 결과를 저장하고 재활용하는 동적 계획법을 적용하면 효율적으로 해결할 수 있다.

5. dp에는 dp[i][j]를 s1[0:i]와 s2[0:j]의 LCS 길이라고 정의하여 푼다. 점화식은 아래와 같다. 

# DP Table 갱신
for n in range(1, N + 1):
    for m in range(1, M + 1): # dp[n][m]
        if s1[n] == s2[m]:
            dp[n][m] = dp[n - 1][m - 1] + 1
        else: 
            dp[n][m] = max(dp[n - 1][m], dp[n][m - 1])

이런 방식을 생각하면 풀 수 있다. 

 

6. 최장 공통 부분 수열의 길이는 dp[N][M]에 저장된다. 따라서 dp 테이블의 마지막 값이 정답이 된다. 

시간 복잡도

시간 복잡도는 dp 테이블의 크기에 따라 O(N x M)이다. 

코드 및 간단설명

DP 알고리즘을 사용하였다. 

s1 = input()
s2 = input()

N, M = len(s1), len(s2)
s1 = " " + s1
s2 = " " + s2

# 초기값 처리
dp = [[0] * (M + 1) for _ in range(N + 1)]

# DP Table 갱신
for n in range(1, N + 1):
    for m in range(1, M + 1): # dp[n][m]
        if s1[n] == s2[m]:
            dp[n][m] = dp[n - 1][m - 1] + 1
        else: 
            dp[n][m] = max(dp[n - 1][m], dp[n][m - 1])

print(dp[N][M])