0Pricing
DSA Interview Prep · 강의

최장 회문 부분 수열과 부분 문자열

구간 DP로 최장 회문 부분 수열을 찾고, 중심에서 확장하는 기법으로 최장 회문 부분 문자열을 찾습니다.

최장 회문 부분 수열과 부분 문자열은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

회문 정의 다시 보기

회문 부분 수열은 앞뒤로 읽어도 같은 부분 수열입니다(요소가 반드시 연속일 필요는 없습니다). 회문 부분 문자열은 문자가 연속되어 있어야 합니다. 'bbbab'의 경우 최장 회문 부분 수열은 'bbbb'(길이 4)인 반면, 최장 회문 부분 문자열은 'bbb'(길이 3)입니다. 이름은 비슷하지만 이 두 문제에는 서로 다른 기법이 필요합니다.

최장 회문 부분 수열: LPS 상태

dp[i][j]를 s[i..j]에서 최장 회문 부분 수열의 길이로 정의합니다. 점화식은 다음과 같습니다. s[i] == s[j]이면 dp[i][j] = dp[i+1][j-1] + 2입니다(서로 일치하는 두 문자가 안쪽 회문을 확장합니다). 그렇지 않으면 dp[i][j] = max(dp[i+1][j], dp[i][j-1])입니다(왼쪽 문자나 오른쪽 문자를 건너뜁니다). 기본 사례는 모든 단일 문자에 대해 dp[i][i] = 1입니다.

s = 'bbbab'
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
    dp[i][i] = 1
print('Base cases set, dp[i][i] = 1 for all i')

LPS 채우는 순서 및 구현

일반적인 구간 DP와 같은 패턴으로 구간 길이를 늘려 가며 LPS 표를 채웁니다. 길이가 2 이상인 각 구간 [i, j]에 대해 양 끝 문자가 일치하는지 확인하고 점화식을 적용합니다. 최종 답은 전체 문자열의 LPS인 dp[0][n-1]입니다.

def longest_palindromic_subsequence(s):
    n = len(s)
    dp = [[0]*n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                inner = dp[i+1][j-1] if length > 2 else 0
                dp[i][j] = inner + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    return dp[0][n-1]

print(longest_palindromic_subsequence('bbbab'))  # 4

LCS를 이용한 LPS의 동치성

우아한 대안이 있습니다. 문자열 s의 LPS는 s와 그 역순인 s[::-1]의 LCS와 같습니다. s의 모든 회문 부분 수열은 s와 그 역순에 공통으로 포함되는 부분 수열이기 때문입니다. 이 변환을 이용하면 LCS 코드를 그대로 재사용할 수 있습니다. 'bbbab'을 뒤집으면 'babbb'가 되고, 두 문자열의 LCS는 4입니다.

def lps_via_lcs(s):
    t = s[::-1]
    m, n = len(s), len(t)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

print(lps_via_lcs('bbbab'))  # 4

최장 회문 부분 문자열: 무차별 대입

최장 회문 부분 문자열은 문자가 연속되어 있어야 합니다. 무차별 대입 접근법은 O(n²)개의 모든 부분 문자열을 확인하고 각각을 O(n)에 검증하므로 총 O(n³)이 걸립니다. 더 빠른 두 가지 접근법이 있습니다. O(n²) time과 O(n²) 공간을 사용하는 구간 DP와 O(n²) time이 걸리지만 O(1) 공간만 사용하는 중심 확장입니다. 면접에서는 상수가 더 작고 코드가 더 간결한 중심 확장 방식이 선호됩니다.

회문 부분 문자열을 위한 구간 DP

s[i..j]가 회문이면 dp[i][j] = True로 정의합니다. 점화식은 dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]입니다. 기본 사례는 dp[i][i] = True 및 dp[i][i+1] = (s[i] == s[i+1])입니다. 지금까지 찾은 회문의 최대 길이를 기록하십시오. 길이를 늘려 가는 순서로 채웁니다. 이 방식은 O(n²) time과 O(n²) 공간을 사용합니다.

def longest_palindrome_dp(s):
    n = len(s)
    dp = [[False]*n for _ in range(n)]
    start, max_len = 0, 1
    for i in range(n):
        dp[i][i] = True
    for i in range(n-1):
        if s[i] == s[i+1]:
            dp[i][i+1] = True
            start, max_len = i, 2
    for length in range(3, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i+1][j-1]:
                dp[i][j] = True
                if length > max_len:
                    start, max_len = i, length
    return s[start:start+max_len]

print(longest_palindrome_dp('babad'))  # 'bab' or 'aba'

중심 확장 기법

중심 확장 접근법은 각 문자와 인접한 각 문자 쌍을 잠재적인 회문의 중심으로 시도하고, 양쪽이 일치하는 동안 바깥쪽으로 확장합니다. 가능한 중심은 2n-1개입니다(n개의 홀수 길이 중심과 n-1개의 짝수 길이 중심). 각 확장에는 최대 O(n) time이 걸리므로, 총 O(n²) time과 O(1) 공간을 사용합니다. 이는 대부분의 면접 상황에서 최적입니다.

def longest_palindrome_expand(s):
    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return r - l - 1  # length of palindrome
    
    start, max_len = 0, 1
    for i in range(len(s)):
        odd = expand(i, i)      # odd-length
        even = expand(i, i+1)   # even-length
        best = max(odd, even)
        if best > max_len:
            max_len = best
            start = i - (best - 1) // 2
    return s[start:start+max_len]

print(longest_palindrome_expand('cbbd'))  # 'bb'

LPS 공간 최적화

LPS 구간 DP는 O(n²) 공간을 사용합니다. 길이만 필요하고 실제 부분 수열은 필요하지 않다면, dp[i][j]가 dp[i+1][j-1], dp[i+1][j], dp[i][j-1]에만 의존한다는 점을 이용하여 공간을 줄일 수 있습니다. 행을 재사용하고 대각선 값 하나를 저장하면 O(n) 공간을 사용할 수 있지만, 구현이 더 복잡하고 면접에서는 거의 요구되지 않습니다.

LPS 복원

실제 회문 부분 수열을 복원하려면 DP 표를 역추적하십시오. (0, n-1)에서 시작합니다. s[i] == s[j]이면 해당 문자를 결과의 양 끝에 추가하고 (i+1, j-1)로 이동합니다. 그렇지 않으면 (i+1, j)와 (i, j-1) 중 값이 더 큰 쪽으로 이동합니다. 이 탐욕적 역추적을 통해 최적 회문 부분 수열 하나를 복원할 수 있습니다.

def reconstruct_lps(s, dp):
    result = []
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] == s[j]:
            result.append(s[i])
            i += 1; j -= 1
        elif dp[i+1][j] > dp[i][j-1]:
            i += 1
        else:
            j -= 1
    # middle character for odd-length
    mid = [s[i]] if i == j else []
    return ''.join(result + mid + result[::-1])

print('Traceback recovers one optimal LPS')

LPS와 LCS의 time 복잡도 비교

구간 DP를 이용한 LPS와 LCS는 모두 O(n²) time과 O(n²) 공간을 사용합니다. 최장 회문 부분 문자열을 위한 중심 확장은 O(n²) time이 걸리지만 O(1) 공간만 사용합니다. 마나커 알고리즘은 부분 문자열 문제를 O(n) time과 공간에 해결하지만, 충분히 복잡하기 때문에 면접관이 요구하는 경우는 드뭅니다. 대부분의 면접 상황에서 부분 문자열 변형 문제에 대해 기대되는 최적 solution은 중심 확장입니다.

일반적인 함정과 경계 사례

다음과 같은 함정을 주의하십시오: (1) 부분 수열과 부분 문자열을 혼동하는 것 — 둘은 서로 다른 문제이며 해법도 다릅니다; (2) 길이가 2인 구간의 구간 DP 기본 사례는 특별히 처리해야 합니다. dp[i+1][j-1]이 dp[i+1][i]가 되기 때문입니다(빈 구간); (3) 중심 확장에서는 max_len = 1로 초기화하십시오(각 단일 문자는 회문입니다); (4) 결과를 추출할 때 중심에서 시작 인덱스를 올바르게 찾으려면 start = i - (best-1)//2를 계산하십시오.

빠른 확인

이 수업에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해를 확인하십시오.

수업 요약

이 수업에서는 다음을 배웠습니다. LPS는 문자가 일치할 때 dp[i][j] = dp[i+1][j-1]+2라는 점화식을 사용하는 구간 DP입니다. 최장 회문 부분 문자열은 O(n²) 시간과 O(1) 공간을 사용하는 중심 확장으로 해결하는 것이 가장 좋습니다. 또한 LPS는 문자열과 그 역순 문자열의 LCS와 같습니다. 다음에는 회문 표와 최소 절단 횟수를 구하는 1차원 DP를 결합하는 회문 분할 II를 다룹니다.

자주 묻는 질문

“최장 회문 부분 수열과 부분 문자열” 강의는 무료인가요?

네 — “최장 회문 부분 수열과 부분 문자열” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

“최장 회문 부분 수열과 부분 문자열”에서 뭘 배우나요?

구간 DP로 최장 회문 부분 수열을 찾고, 중심에서 확장하는 기법으로 최장 회문 부분 문자열을 찾습니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.

“최장 회문 부분 수열과 부분 문자열” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

  1. 구간 DP 패턴과 채우기 순서
  2. 최장 회문 부분 수열과 부분 문자열
  3. 회문 분할 II
  4. 풍선 터뜨리기: 역방향 구간 DP
← DSA Interview Prep(으)로 돌아가기