두 개의 문자열 s1과 s2가 주어졌을 때, 두 문자열 모두의 특수 부분 문자열(special substring)에 해당하는 가장 긴 문자열 s3의 크기를 구하는 프로그램을 만들어 보겠습니다.
여기서 문자열 x가 다른 문자열 y의 특수 부분 문자열이라는 것은, y에서 0개 이상의 문자를 제거했을 때 x를 얻을 수 있다는 의미입니다. 즉, 이 문제는 널리 알려진 최장 공통 부분 수열(Longest Common Subsequence, LCS) 문제와 본질적으로 같은 문제입니다.
예를 들어 입력이 s1 = 'pineapple', s2 = 'people'이라면 출력은 5가 됩니다. 이때 가장 긴 특수 부분 문자열은 'peple'이며, 그 크기는 5입니다.
해결 접근 방법
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 알고리즘의 단계는 다음과 같습니다.
- prev := 새로운 딕셔너리(존재하지 않는 키에 대해서는 0 반환)
- i를 0부터 len(s1) - 1까지 반복:
- cur := 새로운 딕셔너리(존재하지 않는 키에 대해서는 0 반환)
- j를 0부터 len(s2) - 1까지 반복:
- cur[j] := s1[i]와 s2[j]가 같으면 prev[j - 1] + 1, 그렇지 않으면 max(cur[j - 1], prev[j])
- prev := cur
- prev[len(s2) - 1] 값 반환
구현 예시
다음 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.
from collections import defaultdict
def solve(s1, s2):
prev = defaultdict(int)
for i in range(len(s1)):
cur = defaultdict(int)
for j in range(len(s2)):
cur[j] = prev[j - 1] + 1 if s1[i] == s2[j] else max(cur[j - 1], prev[j])
prev = cur
return prev[len(s2)-1]
s1 = 'pineapple'
s2 = 'people'
print(solve(s1, s2))입력
'pineapple', 'people'
출력
5
동작 원리 및 복잡도
이 알고리즘은 일반적인 2차원 LCS DP 테이블을 1차원 배열 두 개(prev, cur)만 사용하도록 최적화한 형태입니다. 각 단계에서 현재 행의 값을 계산한 뒤 이전 행을 덮어쓰기 때문에 메모리 사용량이 줄어듭니다.
시간 복잡도는 두 문자열의 길이를 각각 m, n이라 할 때 O(m × n)이며, 공간 복잡도는 O(n)입니다. 문자열이 일치할 경우 이전 위치의 값에 1을 더하고, 일치하지 않을 경우 왼쪽 값과 위쪽 값 중 큰 값을 선택하는 방식으로 최장 공통 부분 수열의 길이가 누적됩니다.