파이썬(Python)으로 가장 긴 회문 부분 수열의 길이 구하기 – 동적 계획법 풀이

문제 정의

하나의 문자열이 주어졌을 때, 다음 두 조건을 모두 만족하는 회문 부분 수열(palindromic subsequence)을 찾아야 합니다.

• 길이가 반드시 짝수여야 합니다.

• 정확히 가운데에 있는 두 문자를 제외하면, 연속된 두 문자가 서로 같아서는 안 됩니다.

그리고 조건을 만족하는 부분 수열 중 가장 긴 것의 길이를 결과로 반환해야 합니다.

예를 들어 입력 문자열이 s = 'efeffe'라고 해 보겠습니다. 이때 출력은 4입니다. 조건을 만족하는 짝수 길이의 회문 부분 수열은 'effe' 하나뿐이며, 그 길이가 정확히 4이기 때문입니다.

풀이 전략: 동적 계획법(DP)

이 문제는 구간 단위로 최적해를 쌓아 올리는 대표적인 동적 계획법 유형입니다. 여기서는 dp[i][j]를 "s[i..j] 구간에서 조건을 만족하는 가장 긴 회문 부분 수열"에 대한 정보로 정의하되, 단순한 숫자가 아니라 (길이, 가장 바깥쪽 문자) 형태의 쌍(pair)으로 저장합니다. 바깥쪽 문자를 함께 기록하는 이유는, 구간을 확장할 때 연속된 같은 문자가 생기는 상황을 판별하기 위해서입니다.

구체적인 알고리즘 단계는 다음과 같습니다.

1. n := 문자열 s의 길이로 설정합니다.

2. dp := 각 칸이 (0, 빈 문자열) 쌍으로 초기화된 n × n 2차원 배열을 생성합니다.

3. i를 n-1부터 0까지 1씩 감소시키며 반복합니다.

   • j를 i+1부터 n-1까지 반복합니다.

     • 만약 s[i] == s[j]이고, dp[i+1][j-1]에 저장된 문자가 s[i]가 아니라면 → dp[i][j] := (dp[i+1][j-1]의 길이 + 2, s[i])로 갱신합니다. 즉, 안쪽 회문의 양 끝에 s[i]를 붙여 길이를 2 늘립니다.

     • 그렇지 않다면 → dp[i+1][j], dp[i][j-1], dp[i+1][j-1] 세 후보 중 길이(첫 번째 요소)가 가장 큰 값을 그대로 가져옵니다.

4. 모든 반복이 끝난 후 dp[0][n-1]에 저장된 쌍의 첫 번째 요소, 즉 최대 길이를 반환합니다.

왜 이 방법이 작동할까?

s[i]와 s[j]가 같다면 이 두 문자를 양 끝에 추가해도 회문 성질은 유지됩니다. 하지만 짝수 길이 회문에서는 오직 가운데 두 문자만 같아도 되므로, 안쪽 구간의 회문이 이미 s[i]를 바깥 문자로 사용하고 있는 상태에서 확장하면 연속된 같은 문자가 발생하게 됩니다. 따라서 dp[i+1][j-1]의 두 번째 요소(바깥 문자)가 s[i]와 다른 경우에만 확장을 허용함으로써 제약 조건을 자연스럽게 지키게 됩니다.

Python 구현 예제

def solve(s):
    n = len(s)
    dp = [[(0, '')]*n for _ in range(n)]
    for i in range(n-1, -1, -1):
        for j in range(i+1, n):
            if s[i]== s[j] and dp[i+1][j-1][1] != s[i]:
                dp[i][j] = (dp[i+1][j-1][0] + 2, s[i])
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1], dp[i+1][j-1], key=lambda x: x[0])
    return dp[0][n-1][0]
print(solve('efeffe'))

입력

'efeffe'

출력

4

복잡도 분석

가능한 모든 구간 (i, j) 조합을 한 번씩 처리하므로 시간 복잡도는 O(n²)이며, 2차원 DP 테이블을 사용하므로 공간 복잡도 역시 O(n²)입니다. 문자열 길이가 수천 수준이라면 충분히 실용적인 성능을 기대할 수 있습니다.