세 개의 문자열 s1, s2, s3가 주어졌을 때, 세 문자열 모두에 공통으로 나타나는 가장 긴 공통 부분 수열(Longest Common Subsequence, LCS)의 길이를 구하는 프로그램을 만들어 보겠습니다.
예를 들어 입력이 s1 = "ababchemxde", s2 = "pyakcimde", s3 = "oauctime"이라면, 세 문자열에 공통으로 등장하는 가장 긴 부분 수열은 "acme"이므로 결과는 4가 됩니다.
해결 접근 방식
이 문제는 동적 계획법(Dynamic Programming)을 사용하면 효율적으로 해결할 수 있습니다. 흔히 알려진 두 문자열의 LCS 문제를 3차원으로 확장한 형태로, 세 문자열의 각 위치를 인덱스로 하는 3차원 DP 테이블을 차례대로 채워 나가는 것이 핵심입니다.
구체적인 알고리즘은 다음과 같습니다.
- m := s1의 길이, n := s2의 길이, o := s3의 길이
- dp := (m + 1) × (n + 1) × (o + 1) 크기의 3차원 배열을 생성하고 0으로 초기화
- i를 1부터 m까지 반복
- j를 1부터 n까지 반복
- k를 1부터 o까지 반복
- s1[i - 1], s2[j - 1], s3[k - 1]이 모두 같다면 → dp[i][j][k] = 1 + dp[i - 1][j - 1][k - 1]
- 그렇지 않다면 → dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1])
- k를 1부터 o까지 반복
- j를 1부터 n까지 반복
- 최종적으로 dp[m][n][o]를 반환
여기서 세 문자의 값이 일치하는 경우에는 대각선 방향의 값에 1을 더해 LCS 길이를 늘리고, 일치하지 않는 경우에는 세 방향(i 감소, j 감소, k 감소) 중 가장 큰 값을 선택하여 최댓값을 유지합니다.
Python 코드 예제
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
class Solution:
def solve(self, s1, s2, s3):
m = len(s1)
n = len(s2)
o = len(s3)
dp = [[[0 for i in range(o + 1)] for j in range(n + 1)] for k in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
for k in range(1, o + 1):
if s1[i - 1] == s2[j - 1] == s3[k - 1]:
dp[i][j][k] = 1 + dp[i - 1][j - 1][k - 1]
else:
dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1])
return dp[m][n][o]
ob = Solution()
s1 = "ababchemxde"
s2 = "pyakcimde"
s3 = "oauctime"
print(ob.solve(s1, s2, s3))
입력
"ababchemxde", "pyakcimde", "oauctime"
출력
4
복잡도 분석
세 개의 중첩 루프를 사용하기 때문에 시간 복잡도는 O(m × n × o)입니다. 또한 3차원 DP 테이블을 저장해야 하므로 공간 복잡도 역시 O(m × n × o)입니다. 문자열의 길이가 매우 길어지면 메모리 사용량이 커질 수 있으므로, 필요에 따라 슬라이딩 윈도우 기법으로 차원을 줄이는 최적화도 고려할 수 있습니다.