다이내믹 프로그래밍(Dynamic Programming) 문제로 이해하기

📘 문제: 가장 긴 팰린드롬 부분 문자열

주어진 문자열 s에서, 가장 긴 팰린드롬(회문) 부분 문자열을 찾아서 반환하세요.

팰린드롬이란 앞에서 읽든 뒤에서 읽든 동일한 문자열을 의미합니다.
예: "aba", "racecar", "a"는 팰린드롬입니다.

 

---

✨ 예시

예시 1

• 입력: "babad"
• 출력: "bab"
  (또는 "aba"도 정답으로 인정됩니다)

예시 2

• 입력: "cbbd"
• 출력: "bb"

---

⛓️ 제약 조건

• 문자열 s의 길이는 최소 1, 최대 1000입니다.
• 문자열 s는 영어 알파벳(az, AZ) 또는 숫자로만 구성됩니다.

---

🔍 목표

문자열 내에서 가장 긴 연속된 팰린드롬 부분 문자열을 찾아서 반환하는 프로그램을 작성하세요.

---

🧠 핵심 아이디어

문자열 s[i..j]가 팰린드롬인지 아닌지를 저장하는 DP 테이블을 만듭니다.

• dp[i][j] = True 이면 s[i..j]는 팰린드롬이다.
• 점화식:
  • s[i] == s[j] 이고
  • j - i <= 2 (길이가 2 이하) 또는 dp[i+1][j-1] == True

---

✅ 코드 (Bottom-up 방식)

def longest_palindrome(s):
    n = len(s)
    if n < 2:
        return s

    # dp[i][j] = True if s[i..j] is a palindrome
    dp = [[False] * n for _ in range(n)]

    start = 0
    max_len = 1

    # 모든 길이 1의 문자열은 팰린드롬
    for i in range(n):
        dp[i][i] = True

    # 길이 2 이상부터 검사
    for length in range(2, n + 1):  # 부분 문자열의 길이
        for i in range(n - length + 1):
            j = i + length - 1  # 끝 인덱스

            if s[i] == s[j]:
                if length == 2 or dp[i + 1][j - 1]:
                    dp[i][j] = True
                    if length > max_len:
                        max_len = length
                        start = i

    return s[start:start + max_len]

---

 

 

🧠 단계별 설명

---

1. 입력이 너무 짧은 경우 처리

n = len(s)
if n < 2:
    return s

• 문자열 길이가 0 또는 1이면, 자기 자신이 팰린드롬이므로 그대로 반환합니다.

---

2. DP 테이블 만들기

dp = [[False] * n for _ in range(n)]

• dp[i][j]는 s[i:j+1]이 팰린드롬인지 아닌지를 저장하는 2차원 배열입니다.
• 처음에는 모두 False로 초기화.

---

3. 결과 추적용 변수 초기화

start = 0
max_len = 1

• start: 가장 긴 팰린드롬의 시작 인덱스
• max_len: 그 팰린드롬의 길이

---

4. 길이 1짜리 문자열은 항상 팰린드롬

for i in range(n):
    dp[i][i] = True

• s[i] == s[i] → 당연히 팰린드롬이므로, 대각선 값은 True로 설정

---

5. 길이 2 이상인 부분 문자열들 검사

for length in range(2, n + 1):

• length: 검사할 부분 문자열의 길이 (2, 3, ..., n)

    for i in range(n - length + 1):

• i: 시작 인덱스. 길이 length짜리 문자열을 만들 수 있는 범위까지만 반복
• 예: n=6, length=3 → i는 0~3까지만 가능

        j = i + length - 1

• j: 끝 인덱스

---

6. 팰린드롬 여부 판단

        if s[i] == s[j]:

• 시작과 끝 문자가 같아야 팰린드롬이 될 수 있어요

            if length == 2 or dp[i + 1][j - 1]:

• 길이가 2이면 s[i+1:j]이 비어 있으므로 바로 팰린드롬
• 길이가 3 이상이면 s[i+1:j-1]이 팰린드롬이어야 전체도 팰린드롬

---

7. 팰린드롬이면 DP 업데이트 + 결과 기록

                dp[i][j] = True
                if length > max_len:
                    max_len = length
                    start = i

• 새로운 더 긴 팰린드롬을 찾으면 그 정보를 기록

---

8. 결과 반환

return s[start:start + max_len]

• 가장 긴 팰린드롬 부분 문자열을 잘라서 반환

---

🔍 예시 실행: "babad"

i j s[i] s[j] dp[i+1][j-1] 팰린드롬인가 업데이트

0	2	b	b	a (True)	YES	"bab" 저장
1	3	a	a	b (True)	YES	"aba" 저장

둘 다 팰린드롬이므로 "bab" 또는 "aba" 중 하나 반환 가능.

---

🧪 실행 예시

print(longest_palindrome("babad"))  # 출력: "bab" 또는 "aba"
print(longest_palindrome("cbbd"))   # 출력: "bb"

---

📊 시간/공간 복잡도

• 시간 복잡도: O(n²)
• 공간 복잡도: O(n²) (2차원 DP 배열 사용)

---

📌 정리

• 문자열 내 모든 부분 문자열을 검사하면서, 팰린드롬 여부를 다이내믹 프로그래밍으로 저장해서 재활용
• 핵심은 점화식:
  s[i] == s[j]이고 dp[i+1][j-1] == True면 dp[i][j] == True
• 길이가 2 이하일 때는 따로 조건을 체크해줘야 해요

---

이 알고리즘이 잘 이해되셨다면, 더 최적화된 O(n) 시간 알고리즘인 Manacher’s Algorithm 도 소개해드릴 수 있어요! 원하시면 알려주세요 😊