Python으로 문자열에서 가장 긴 회문 부분 수열의 길이 구하기

이번 문제는 소문자로 이루어진 문자열 s가 주어졌을 때, 해당 문자열 안에서 만들 수 있는 가장 긴 회문(palindrome) 부분 수열의 길이를 구하는 것입니다.

여기서 부분 수열(subsequence)은 문자열에서 일부 문자를 삭제하더라도 나머지 문자들의 상대적인 순서가 유지되는 형태를 의미합니다. 반드시 연속된 문자일 필요는 없다는 점이 부분 문자열(substring)과 다릅니다.

예를 들어 입력이 s = "aolpeuvekyl"이라면, 정답은 5가 됩니다. 이 문자열에서 "level"이라는 회문을 만들 수 있기 때문입니다.

해결 접근 방법

이 문제는 재귀적 동적 계획법(Dynamic Programming)을 활용해 해결할 수 있습니다. 구간 [i, j]에 대해 가장 긴 회문 부분 수열의 길이를 계산하는 dp(i, j) 함수를 정의하고, 다음 규칙에 따라 처리합니다.

• n := 문자열 s의 길이로 설정합니다.
• dp(i, j) 함수를 정의합니다.
• i == j인 경우 (구간에 문자가 하나뿐인 경우):
  • 1을 반환합니다. (길이 1짜리 회문)
• i > j인 경우 (유효하지 않은 구간):
  • 0을 반환합니다.
• 그 외의 경우:
  • s[i]와 s[j]가 같다면, 양 끝 두 문자를 회문에 포함할 수 있으므로 2 + dp(i + 1, j - 1)을 반환합니다.
  • 같지 않다면, 한쪽 끝을 제외한 경우 중 더 큰 값을 선택하여 max(dp(i + 1, j), dp(i, j - 1))을 반환합니다.
• 최종적으로 dp(0, n - 1)을 반환합니다.

Python 구현 예제

아래 코드를 통해 실제 구현 방법을 확인해 보겠습니다.

class Solution:
    def solve(self, s):
        n = len(s)
        def dp(i, j):
            if i == j:
                return 1
            elif i > j:
                return 0
            else:
                if s[i] == s[j]:
                    return 2 + dp(i + 1, j - 1)
                else:
                    return max(dp(i + 1, j), dp(i, j - 1))
        return dp(0, n - 1)

ob = Solution()
s = "aolpeuvekyl"
print(ob.solve(s))

입력

"aolpeuvekyl"

출력

5

성능 개선 팁

위 재귀 구현은 최악의 경우 지수 시간 복잡도 O(2ⁿ)를 가질 수 있습니다. 중복되는 하위 문제가 많기 때문에 @lru_cache 데코레이터나 메모이제이션(memoization)을 적용하면 시간 복잡도를 O(n²)까지 크게 줄일 수 있습니다.

from functools import lru_cache

class Solution:
    def solve(self, s):
        n = len(s)
        @lru_cache(maxsize=None)
        def dp(i, j):
            if i == j:
                return 1
            if i > j:
                return 0
            if s[i] == s[j]:
                return 2 + dp(i + 1, j - 1)
            return max(dp(i + 1, j), dp(i, j - 1))
        return dp(0, n - 1)

이처럼 회문 부분 수열 문제는 구간 단위 DP의 대표적인 유형으로, 코딩 테스트와 알고리즘 인터뷰에서 자주 등장하는 주제이므로 원리를 잘 익혀두면 다양한 변형 문제에도 쉽게 대응할 수 있습니다.