Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 푸는 가장 긴 회문(Palindrome) 부분 문자열 찾기 - DP 완전 정복

문자열 S가 주어졌을 때, S 안에서 가장 긴 회문(palindromic) 부분 문자열을 찾는 문제입니다. 여기서는 문자열의 길이가 최대 1000이라고 가정합니다. 예를 들어 문자열이 "BABAC"라면, 가장 긴 회문 부분 문자열은 "BAB"가 됩니다.

회문이란 앞에서 읽으나 뒤에서 읽으나 같은 문자열을 의미합니다. 이 문제는 동적 계획법(Dynamic Programming, DP)을 활용하면 효율적으로 해결할 수 있습니다.

해결 접근 방식

DP 테이블을 활용한 해결 단계는 다음과 같습니다.

  • 문자열 길이와 같은 크기의 정사각 행렬(DP 테이블)을 만들고, 모든 값을 False로 초기화합니다.
  • 주 대각선 요소를 True로 설정합니다. 즉, 모든 i에 대해 DP[i][i] = True로 지정합니다. (길이 1인 문자열은 항상 회문)
  • start := 0으로 초기화합니다.
  • 부분 문자열의 길이 l을 2부터 len(S)+1까지 반복합니다.
    • 시작 인덱스 i를 0부터 len(S)-l+1까지 반복합니다.
    • end := i + l로 설정합니다.
    • l이 2인 경우: S[i] == S[end-1]이라면 DP[i][end-1] = True로 설정하고, max_len := l, start := i로 갱신합니다.
    • 그 외의 경우: S[i] == S[end-1]이면서 내부 부분 문자열도 회문(DP[i+1][end-2] == True)이라면 DP[i][end-1] = True로 설정하고, max_len := l, start := i로 갱신합니다.
  • 최종적으로 start 인덱스부터 start + max_len 인덱스까지의 부분 문자열을 반환합니다.

핵심 아이디어

이 알고리즘의 핵심은 다음과 같습니다. 문자열 s[i..j]가 회문이 되려면 두 조건을 만족해야 합니다.

  1. 양 끝 문자가 같아야 합니다. 즉, s[i] == s[j]
  2. 양 끝을 제외한 내부 부분 문자열 s[i+1..j-1]도 회문이어야 합니다.

길이가 작은 부분 문자열부터 차례대로 검사하므로, 더 긴 부분 문자열을 확인할 때 이미 내부 결과가 계산되어 있다는 점을 활용하는 것이 바텀업(bottom-up) 방식 DP의 장점입니다. 시간 복잡도는 O(n²), 공간 복잡도 역시 O(n²)입니다.

파이썬 구현 예제

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

class Solution(object):
   def longestPalindrome(self, s):
      dp = [[False for i in range(len(s))] for i in range(len(s))]
      for i in range(len(s)):
         dp[i][i] = True
      max_length = 1
      start = 0
      for l in range(2,len(s)+1):
         for i in range(len(s)-l+1):
            end = i+l
            if l==2:
               if s[i] == s[end-1]:
                  dp[i][end-1]=True
                  max_length = l
                  start = i
            else:
               if s[i] == s[end-1] and dp[i+1][end-2]:
                  dp[i][end-1]=True
                  max_length = l
                  start = i
      return s[start:start+max_length]
ob1 = Solution()
print(ob1.longestPalindrome("ABBABBC"))

입력

"ABBABBC"

출력

"BBABB"

입력 문자열 "ABBABBC"에서 가장 긴 회문 부분 문자열은 "BBABB"로 출력됩니다. 이처럼 DP 테이블을 활용하면 중복 계산 없이 모든 부분 문자열의 회문 여부를 체계적으로 판별할 수 있습니다.