백준 9251번 - LCS

LCS 문제 바로 가기

풀이 날짜: 2026-01-19

baekjoon 알고리즘 문제 풀이

풀이 코드


import sys
input = sys.stdin.readline

A = input().strip()
B = input().strip()

n,m = len(A), len(B)
dp = [[0] * (m+1) for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,m+1):
        if A[i-1] == B[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])
print(dp[n][m])

print(count)

문제 핵심 요약:

이 문제의 목표는 학생들을 번호가 증가하는 순서로 만들기 위해 최소 몇 명을 옮겨야 하는지 구하는 것이다. 여기서 중요한 관찰은 “옮기지 않고 그대로 둘 수 있는 학생들의 최대 집합”을 찾으면, 나머지만 적절한 위치로 옮겨 전체를 증가 순으로 만들 수 있다는 점이다. 즉, 최대로 유지 가능한 증가 부분 수열의 길이(LIS) 를 구하면, 정답은 전체 n - LIS 길이가 된다.

DP 정의

dp[i][j] = 문자열 A의 앞 i글자와 문자열 B의 앞 j글자를 사용했을 때, 만들 수 있는 LCS의 최대 길이

처음에는 어떤 학생이든 자기 자신만으로 길이 1짜리 증가 수열을 만들 수 있기 때문에 dp = [1] * n으로 시작한다.
이후 i를 끝으로 만들 수 있는 죄장 길이를 앞의 원소들과 비교하며 갱신했다.

헷갈렸던 것 정리

문자가 같은 경우의 처리

현재 비교 중인 문자가 A[i-1]와 B[j-1]일 때, 두 문자가 같다면 공통 부분 수열에 이 문자를 추가할 수 있다. 이 경우, 이전까지의 최적 결과인 dp[i-1][j-1]에 1을 더하면 된다

문자가 다른 경우의 처리

두 문자가 다를 경우, 이 둘을 동시에 공통 수열에 포함시키는 것은 불가능하다. 따라서 둘 중 하나는 사용하지 않는 경우를 고려해야 한다.

A의 현재 문자를 제외한 경우 → dp[i-1][j]
B의 현재 문자를 제외한 경우 → dp[i][j-1]

이 중에서 더 큰 값이 “지금까지 만들 수 있었던 최대 공통 길이”가 된다.

dp[i][j] = max(dp[i][j-1], dp[i-1][j])

LIS와의 차이점 정리

이 문제를 풀며 느낀 점은, LCS는 LIS와 매우 비슷하지만 한 단계 더 확장된 문제라는 것이다.

LIS: 수열 1개 → DP 1차원
LCS: 문자열 2개 → DP 2차원

Vienna sausage