회문 분할 II
미리 계산한 회문 표와 1차원 DP를 결합해 문자열을 회문들로 분할하는 데 필요한 최소 분할 횟수를 구합니다.
회문 분할 II은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
문제: 분할에 필요한 최소 절단 횟수
회문 분할 II에서는 문자열 s가 주어질 때, 분할된 모든 부분 문자열이 회문이 되도록 하는 최소 절단 횟수를 구합니다. 'aab'의 경우 한 번 절단하면 ['aa', 'b']가 되므로 답은 1입니다. 'a'의 답은 0입니다(이미 회문이기 때문입니다). 이 문제는 두 단계의 DP를 결합합니다. 먼저 어떤 부분 문자열이 회문인지 미리 계산한 다음, 1차원 DP를 사용해 최소 절단 횟수를 구합니다.
1단계: 회문 표 미리 계산
먼저 구간 DP를 사용하여 s[i..j]가 회문이면 is_pal[i][j] = True가 되도록 구성합니다. 이 과정은 O(n²) 시간과 O(n²) 공간을 사용합니다. 또는 중심 확장을 사용하여 같은 표를 O(n²) 시간에 채울 수도 있습니다. 이 표가 필요한 이유는 1차원 절단 DP가 is_pal[i][j]를 반복해서 조회하기 때문입니다. 미리 계산하면 절단 DP 반복문 안에서 회문 여부를 다시 계산하지 않아도 됩니다.
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
print(build_palindrome_table('aab'))2단계: 1차원 절단 DP 설정
cuts[i]를 s[0..i]를 분할하는 데 필요한 최소 절단 횟수로 정의합니다. s[0..i] 자체가 회문이면 cuts[i] = 0입니다. 그렇지 않으면 모든 분할을 시도합니다. j가 0부터 i-1까지인 각각의 경우에 s[j+1..i]가 회문이면 cuts[i] = min(cuts[i], cuts[j] + 1)로 갱신합니다. 이는 마지막 분할 조각이 s[j+1..i]라면 어떨지를 묻는 것입니다. 이 경우 접두 부분에는 cuts[j]번의 절단이 필요하고, 여기에 절단 한 번을 더해야 합니다.
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = [float('inf')] * n
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0 # entire prefix is a palindrome
else:
for j in range(i):
if is_pal[j+1][i]:
cuts[i] = min(cuts[i], cuts[j] + 1)
return cuts[n-1]전체 해법과 실행 추적
'aab'를 따라가 보겠습니다. 회문 표는 다음과 같습니다. is_pal[0][0]='a'=T, is_pal[1][1]='a'=T, is_pal[2][2]='b'=T, is_pal[0][1]='aa'=T, is_pal[1][2]='ab'=F, is_pal[0][2]='aab'=F입니다. 절단 횟수는 다음과 같습니다. cuts[0]=0입니다('a'는 회문입니다). cuts[1]=0입니다('aa'는 회문입니다). cuts[2]의 경우 'aab'는 회문이 아니므로 j=1을 시도하면 is_pal[2][2]=T입니다. 따라서 cuts[2] = cuts[1]+1 = 1입니다. 답은 1입니다.
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = [float('inf')] * n
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(i):
if is_pal[j+1][i]:
cuts[i] = min(cuts[i], cuts[j] + 1)
return cuts[n-1]
print(min_cut('aab')) # 1
print(min_cut('ababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab'))시간 및 공간 복잡도
1단계(회문 표)는 O(n²) 시간과 O(n²) 공간을 사용합니다. 2단계(절단 DP)는 바깥 반복문에서 n개의 위치를 순회하고, 안쪽 반복문에서 n개의 분할 지점을 순회하므로 역시 O(n²) 시간이 걸립니다. 전체 복잡도는 O(n²) 시간, O(n²) 공간입니다. 절단 횟수 배열의 공간은 O(n)으로 줄일 수 있지만, 회문 표에는 여전히 O(n²)이 필요합니다. 면접에서는 O(n²)을 기대합니다. 마나커 알고리즘을 사용하는 O(n) 해법은 일반적인 범위를 벗어납니다.
회문 표를 위한 중심 확장
회문 표를 구간 DP로 구성하는 대신, 중심 확장을 사용하여 is_pal을 채울 수 있습니다. 각 중심 위치에서 바깥쪽으로 확장하면서 찾은 모든 회문을 표시합니다. 이 방법도 O(n²) 시간과 O(n²) 공간을 사용하지만, 캐시 동작이 더 좋아 실제로는 더 빠를 수 있습니다. 두 방법 모두 면접에서 유효합니다.
def build_pal_expand(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
def expand(l, r):
while l >= 0 and r < n and s[l] == s[r]:
is_pal[l][r] = True
l -= 1; r += 1
for i in range(n):
expand(i, i) # odd-length centres
expand(i, i+1) # even-length centres
return is_pal
print('Expand-around-centre palindrome table built')모든 분할 열거하기(1부)
회문 분할 I은 관련 문제로, 모든 부분 문자열이 회문인 ALL 유효한 분할을 열거하라고 요구합니다. 이 문제는 미리 계산한 회문 표를 가지치기의 판단 기준으로 사용하는 백트래킹으로 해결합니다. 최소 절단 DP가 개수를 세는 것과 달리, 이 문제는 지수적으로 많은 해를 열거하므로 전혀 다른 접근법이 필요합니다.
def partition_all(s):
n = len(s)
is_pal = build_pal_expand(s)
result = []
def backtrack(start, path):
if start == n:
result.append(path[:])
return
for end in range(start, n):
if is_pal[start][end]:
path.append(s[start:end+1])
backtrack(end+1, path)
path.pop()
backtrack(0, [])
return result
print(partition_all('aab')) # [['a','a','b'], ['aa','b']]n-1로 절단 횟수 초기화하기
일반적인 요령은 inf 대신 cuts[i] = i로 초기화하는 것입니다. s[0..i]의 최악의 경우는 각 문자를 따로 절단하는 것이므로 절단 횟수가 i가 되기 때문입니다. 이렇게 하면 코드에서 inf인지 확인하지 않아도 됩니다. is_pal[0][i]가 참이면 0으로 덮어씁니다. 이 초기화는 절단 횟수의 상한을 분명하게 보여 주고 코드를 조금 단순하게 만듭니다.
def min_cut_clean(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = list(range(n)) # cuts[i] = i (worst case)
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(1, i+1):
if is_pal[j][i]:
cuts[i] = min(cuts[i], cuts[j-1] + 1)
return cuts[n-1]대안: 별도 표 없이 한 번에 수행하는 DP
회문 표와 절단 DP를 동시에 채우는 우아한 변형도 있습니다. 각 중심에서 회문을 확장하면서 즉시 cuts 배열을 갱신합니다. 회문 s[l..r]에 대해 cuts[r] = min(cuts[r], (cuts[l-1]+1 if l > 0 else 0))으로 갱신할 수 있습니다. 이렇게 하면 별도의 O(n²) 표 순회 단계를 없앨 수 있으며, 시간 압박 속에서 면접을 볼 때 구현하기 더 깔끔할 수 있습니다.
고려해야 할 경계 사례
회문 분할 II의 주요 경계 사례는 다음과 같습니다: (1) 한 문자로 이루어진 문자열은 절단 횟수 0을 반환합니다; (2) 이미 회문인 문자열은 절단 횟수 0을 반환합니다; (3) 모든 문자가 서로 다른 문자열에는 n-1번의 절단이 필요합니다; (4) 모든 문자가 같은 문자열(예: 'aaaa')에는 전체 문자열이 회문이므로 절단이 필요하지 않습니다. 해법이 is_pal[0][i] = True일 때의 조기 종료를 올바르게 처리하는지 항상 확인하십시오.
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = list(range(n))
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(1, i+1):
if is_pal[j][i]:
cuts[i] = min(cuts[i], cuts[j-1] + 1)
return cuts[n-1]
print(min_cut('a')) # 0
print(min_cut('aaaa')) # 0
print(min_cut('abc')) # 2면접에서 설명하는 요령
면접에서 이 문제를 설명할 때는 두 단계 접근법부터 제시하십시오. 먼저 회문 표를 구성한 다음 절단 횟수 배열에 1차원 DP를 적용합니다. 코딩하기 전에 점화식을 말로 설명하십시오. 회문 표에는 O(n²)개의 항목이 있으며, 각 항목은 구간 DP 점화식을 사용해 O(1)에 채울 수 있다는 점을 언급하십시오. 시간 압박 속에서도 정확성을 보여 주려면 전체 해법을 작성하기 전에 추적 예시를 항상 직접 따라가 보십시오.
빠른 확인
이 수업에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해를 확인하십시오.
수업 요약
이 수업에서는 다음을 배웠습니다. 회문 분할 II는 두 단계의 DP를 사용합니다. 먼저 회문 표를 미리 계산한 다음 1차원 절단 DP를 실행합니다. 절단 점화식은 s[j..i]가 회문인 모든 j에 대해 cuts[i] = min(cuts[j-1] + 1)입니다. 또한 전체 복잡도는 O(n²) 시간과 O(n²) 공간입니다. 다음에는 영리한 역방향 구간 DP 접근법을 사용하는 풍선 터뜨리기 문제를 다룹니다.
자주 묻는 질문
“회문 분할 II” 강의는 무료인가요?
네 — “회문 분할 II” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“회문 분할 II”에서 뭘 배우나요?
미리 계산한 회문 표와 1차원 DP를 결합해 문자열을 회문들로 분할하는 데 필요한 최소 분할 횟수를 구합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“회문 분할 II” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.