[AlgorithmSolving][DP] JUNGOL_4377: 공통부분문자열(longest common substring)
1. 문제 내용
-
문제:
두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.
어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다.
예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다.
하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.
두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다.
이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다.
만약, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공통 부분 문자열은 빈 문자열이다.
-
입력:
첫째 줄과 둘째 줄에 문자열이 주어진다.
문자열은 대문자로 구성되어 있으며, 길이는 1 이상 4000 이하이다.
-
출력:
첫째 줄에 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 출력한다.
2. 문제 유형 파악
이 문제는 전형적인 DP문제로 알고리즘 공부를 할 때 가장 주의해야 할 치명적인 함정이 숨어있는 문제이기도 합니다.
-
주의할 점(Substring vs Subsequence):
이 문제는 “최장 공통 부분 수열(Longest Common Subsequence)”이 아니라 “최장 공통 부분 문자열(Longest Common Substring)”을 구하는 문제입니다. 문제 설명에서도 “연속으로 나타나는 것”이라고 명확히 설명하고 있습니다.
-
시간 복잡도 분석:
두 문자열의 최대 길이가 각각 4000입니다. 따라서 2차원 배열을 만들어 $O(N \times M)$의 시간 복잡도로 탐색을 진행하면 연산 횟수는 최대 16,000,000번이 됩니다. 이는 일반적인 코딩 테스트의 시간 제한 내에 넉넉히 통과할 수 있는 수치이므로, 2차원 DP 테이블을 그리는 정석적인 접근이 가장 적합합니다.
3. 문제를 풀기 위한 핵심 아이디어
이 문제를 관통하는 핵심은 “문자가 연속되지 않고 끊어졌을 때 상태는 어떻게 처리할 것인가”를 DP 테이블의 점화식에 완벽하게 반영하는 것입니다.
- 2차원 DP 테이블의 정의
두 문자열을 각각 A와 B라고 할 때, 과거의 상태르 기록할 2차원 배열을 다음과 같이 정의합니다.
- $DP[i][j]$ : 문자열 A의 $i$번째 문자와 문자열 B의 $j$번째 문자에서 끝나는 최장 공통 부분 문자열의 길이.
- 점화식
이중 반복문으로 문자를 하나씩 비교하면서 다음과 같은 두 가지 엄격한 규칙으로 DP 테이블을 채워나갑니다.
- 문자가 서로 같을 때 ($A[i-1] == B[j-1]$):
- 두 문자열이 성공적으로 연속해서 이어지고 있다는 뜻입니다. 따라서 바로 직전 대각선 왼쪽 위 칸의 값(이전까지 이어져 온 공통 문자열 길이)에 1을 더해줍니다.
- 점화식: $DP[i][j] = DP[i-1][j-1] + 1$
- 문자가 서로 다를 때 ($A[i-1] \neq B[j-1]$):
- 문자열은 무조건 '연속'되어야 하므로, 문자가 다르면 연속성은 즉시 파괴됩니다. 이전까지 얼마나 긴 문자열이 이어져 왔든 0으로 초기화합니다. 이것이 최장 공통 부분 수열 문제와의 가장 결정적인 차이점입니다.
- 점화식: $DP[i][j] = 0$
- 정답(최댓값) 추출 방식의 차이
일반적인 최장 공통 부분 수열 문제에서는 값을 계속 누적해서 가져가기 때문에 DP 테이블의 맨 마지막 우측 하단 칸(DP[N][M])이 최종 정답이 됩니다.
하지만 이 문제는 문자가 다르면 중간에 값이 0으로 초기화되어 버리므로, 가장 긴 공통 부분 문자열이 반드시 문자열의 맨 끝에서 완성된다는 보장이 없습니다.
따라서 DP 테이블을 채워나가는 반복문 내부에서, 값이 갱신될 때마다 기존의 최댓값과 비교하여 가장 큰 값을 별도의 변수에 계속 갱신하며 추적해야 합니다. 모든 탐색이 끝난 후 이 별도의 변수가 문제에서 요구하는 최종 정답이 됩니다.
4. 코드
문제를 해겨한 코드는 다음과 같습니다.
import sys
def solve():
input = sys.stdin.readline
input_str1 = input().rstrip()
input_str2 = input().rstrip()
n = len(input_str1)
m = len(input_str2)
dp = [[0] * (m+1) for _ in range(n+1)]
max_value = 0
for i in range(1, n+1):
for j in range(1, n+1):
if input_str1[i-1] == input_str2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
if dp[i][j] > max_value:
max_value = dp[i][j]
else:
dp[i][j] = 0
print(max_value)
solve()
5. 복기 및 최적화
5.1 최적화
이 문제도 결국 다른 DP 문제와 동일하게 i번째와 i-1번째 DP 배열만을 사용하고 있으므로 굳이 첫 번째 입력의 길이(N)와 두 번째 입력의 길이(M) NxM의 2차원 DP 배열을 사용하지 않고 단 두 개의 DP 배열만을 사용하여 공간복잡도를 줄일 수 있습니다.
import sys
def solve():
input = sys.stdin.readline
input_str1 = input().rstrip()
input_str2 = input().rstrip()
n = len(input_str1)
m = len(input_str2)
dp = [0] * (m+1)
max_value = 0
for i in range(1, n+1):
next_dp = [0] * (m+1)
for j in range(1, n+1):
if input_str1[i-1] == input_str2[j-1]:
next_dp[j] = dp[j-1] + 1
if next_dp[j] > max_value:
max_value = next_dp[j]
else:
next_dp[j] = 0
dp = next_dp
print(max_value)
solve()
Comments