구간 DP 패턴과 채우기 순서
구간 DP 상태 dp[i][j]를 정의하고, 구간을 길이가 짧은 것부터 늘려 가며 채워야 하는 이유를 설명한 뒤 행렬 연쇄 곱셈에 패턴을 적용해 추적합니다.
구간 DP 패턴과 채우기 순서은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
구간 DP란 무엇인가요
구간 DP는 상태 dp[i][j]가 인덱스 i부터 j까지를 아우르는 하위 문제의 최적 답을 나타내는 동적 계획법 패턴입니다. 핵심 통찰은 더 작은 구간을 먼저 해결한 다음 전체 범위까지 확장해 나가는 것입니다. 이 패턴은 하위 문제의 경계가 범위의 왼쪽 및 오른쪽 끝점인 행렬 연쇄 곱셈, 회문 분할, 풍선 터뜨리기와 같은 문제를 자연스럽게 모델링합니다.
상태 정의 및 기본 사례
구간 DP에서 상태는 i <= j일 때의 dp[i][j]입니다. 기본 사례는 단일 요소 구간인 dp[i][i]입니다. 이는 자명하게 해결할 수 있습니다. 예를 들어 행렬 하나의 곱셈 비용은 0입니다. 두 요소 구간 dp[i][i+1]도 대개 간단한 답을 가집니다. 길이 1부터 n까지 구간 길이를 늘려 가며 표를 채웁니다.
n = 4
dp = [[0] * n for _ in range(n)]
# Base cases: single elements
for i in range(n):
dp[i][i] = 0 # length-1 intervals채우는 순서: 길이 증가
구간 DP에서 중요한 세부 사항은 채우는 순서입니다. 길이가 L인 모든 구간을 계산한 후에 길이가 L+1인 구간을 계산해야 합니다. 더 긴 구간이 더 짧은 하위 구간에 의존하기 때문입니다. 바깥쪽 반복문은 2부터 n까지 구간 길이를 순회하고, 중간 반복문은 왼쪽 경계 i를 설정하며, 오른쪽 경계는 j = i + L - 1로 계산합니다.
n = 5
dp = [[float('inf')] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 0
for length in range(2, n + 1): # interval length
for i in range(n - length + 1): # left boundary
j = i + length - 1 # right boundary
for k in range(i, j): # split point
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])행렬 연쇄 곱셈 설정
고전적인 구간 DP 문제는 행렬 연쇄 곱셈입니다. 크기가 dims[0..n]으로 주어진 행렬들의 곱을 계산할 때 필요한 스칼라 곱셈 횟수의 최솟값을 구하는 문제입니다. 크기 A(p×q)인 행렬과 B(q×r)인 행렬을 곱하는 데는 p*q*r번의 연산이 필요합니다. dp[i][j]는 i번째부터 j번째까지의 행렬을 곱하는 최소 비용입니다. 분할 지점 k는 수열을 두 하위 연쇄로 나눌 위치를 결정합니다.
def matrix_chain_order(dims):
n = len(dims) - 1 # number of matrices
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
dp[i][j] = min(dp[i][j], cost)
return dp[0][n-1]
print(matrix_chain_order([10, 30, 5, 60])) # 4500DP 표 추적
크기 [10, 30, 5, 60]인 행렬 연쇄 예를 따라가 보겠습니다. 이는 세 행렬 A(10×30), B(30×5), C(5×60)을 나타냅니다. dp[0][2]에서 k=0으로 분할하면 dp[0][0] + dp[1][2] + 10×30×60 = 0 + 9000 + 18000 = 27000이고, k=1로 분할하면 dp[0][1] + dp[2][2] + 10×5×60 = 1500 + 0 + 3000 = 4500입니다. 따라서 dp[0][2] = 4500이며, 이는 먼저 AB를 곱할 때 달성됩니다.
이 채우는 순서가 작동하는 이유
dp[i][j]를 계산할 때 [i, j-1]의 모든 k에 대해 dp[i][k]와 dp[k+1][j]를 참조합니다. 두 하위 구간 모두 [i, j]보다 길이가 엄격하게 짧습니다. 길이를 작은 것부터 큰 것까지 순회하면 필요한 모든 하위 구간이 사용되기 전에 계산됩니다. 이것이 구간 DP의 채우는 순서가 올바르다는 핵심 근거입니다. 짧은 구간은 항상 긴 구간의 의존 항목이 됩니다.
메모이제이션을 사용하는 하향식 구간 DP
또 다른 방법으로 구간 DP를 메모이제이션을 사용하는 하향식 방식으로 구현할 수 있습니다. 구간 [i, j]의 최적 비용을 반환하는 재귀 함수 solve(i, j)를 작성하고, 결과를 딕셔너리에 저장합니다. 재귀가 채우는 순서를 자동으로 처리합니다. 하향식 방식은 추론하기 더 쉬운 경우가 많지만 함수 호출 오버헤드가 발생할 수 있습니다. 반면 상향식 방식은 큰 입력에서 실제로 더 빠릅니다.
from functools import lru_cache
def matrix_chain_memo(dims):
n = len(dims) - 1
@lru_cache(maxsize=None)
def solve(i, j):
if i == j:
return 0
return min(
solve(i, k) + solve(k+1, j) + dims[i]*dims[k+1]*dims[j+1]
for k in range(i, j)
)
return solve(0, n-1)
print(matrix_chain_memo([10, 30, 5, 60])) # 4500시간 및 공간 복잡도
구간 DP에는 O(n²)개의 상태가 있으며(모든 쌍 (i, j)), 각 상태에서 O(n)개의 분할 지점을 순회하므로 전체 O(n³) time이 걸립니다. DP 표에 필요한 공간은 O(n²)입니다. 행렬 100개를 사용하는 행렬 연쇄 곱셈의 경우 이는 1,000,000번의 연산이므로 충분히 실행 가능합니다. 이 패턴은 어려운 LeetCode 문제에 많이 등장하며, 구조가 직관적이지 않기 때문에 FAANG 면접에서 특히 선호됩니다.
최적 solution 복원
비용뿐 아니라 실제 괄호 묶기를 복원하려면 각 상태에서 최솟값을 만든 k를 기록하는 별도의 split[i][j] 표를 저장하십시오. 그런 다음 분할을 재귀적으로 읽어 냅니다. reconstruct(i, j)는 [i, split[i][j]]와 [split[i][j]+1, j]에 대해 재귀를 수행하여 최적 그룹화를 출력합니다. 이 기법은 모든 구간 DP 문제에 적용할 수 있습니다.
def matrix_chain_with_split(dims):
n = len(dims) - 1
dp = [[0]*n for _ in range(n)]
split = [[0]*n for _ in range(n)]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
if cost < dp[i][j]:
dp[i][j] = cost
split[i][j] = k
return dp[0][n-1], split모든 구간 DP 문제를 위한 템플릿
범용 구간 DP 템플릿은 세 부분으로 구성됩니다. (1) 단일 요소에 대한 기본 사례를 초기화합니다. (2) 길이를 늘려 가며 반복하고, 각 길이에 대해 유효한 모든 왼쪽 경계를 순회하면서 오른쪽 경계를 계산합니다. (3) 각 구간에서 모든 분할 지점을 순회하고 문제에 맞는 점화식을 적용합니다. 문제마다 달라지는 부분은 가장 안쪽 반복문에 있는 점화식뿐입니다.
def interval_dp_template(n, base_cost, split_cost):
dp = [[float('inf')] * n for _ in range(n)]
for i in range(n):
dp[i][i] = base_cost(i) # problem-specific base case
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
for k in range(i, j):
# problem-specific recurrence
candidate = dp[i][k] + dp[k+1][j] + split_cost(i, k, j)
dp[i][j] = min(dp[i][j], candidate)
return dp[0][n-1]일반적인 구간 DP 문제
구간 DP를 사용하는 문제에는 다음이 있습니다. 행렬 연쇄 곱셈(연산 최소화), 풍선 터뜨리기(코인 최대화), 이상한 프린터(출력 연산 최소화), 다각형 최소 점수 삼각분할, 회문 분할 II입니다. 각 문제는 동일한 채우기 순서 뼈대를 사용하지만 점화식은 서로 다릅니다. 범위나 수열에 대한 최적 값을 구하고, 그 범위를 내부의 어느 지점에서든 나눌 수 있는 문제라면 이 패턴을 알아보십시오.
빠른 확인
이 수업에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념을 이해했는지 확인해 보십시오.
수업 요약
이 수업에서는 다음을 배웠습니다. 구간 DP는 dp[i][j]를 사용하여 범위에 대한 최적 답을 나타냅니다. 하위 구간을 먼저 계산할 수 있도록 채우는 순서는 구간 길이를 늘려 가는 방식이어야 합니다. 또한 범용 템플릿은 O(n³) time과 O(n²) 공간을 사용합니다. 다음으로 이 패턴을 사용하여 최장 회문 부분 수열과 회문 부분 문자열을 살펴보겠습니다.
자주 묻는 질문
“구간 DP 패턴과 채우기 순서” 강의는 무료인가요?
네 — “구간 DP 패턴과 채우기 순서” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“구간 DP 패턴과 채우기 순서”에서 뭘 배우나요?
구간 DP 상태 dp[i][j]를 정의하고, 구간을 길이가 짧은 것부터 늘려 가며 채워야 하는 이유를 설명한 뒤 행렬 연쇄 곱셈에 패턴을 적용해 추적합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“구간 DP 패턴과 채우기 순서” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 구간 DP 패턴과 채우기 순서
- 최장 회문 부분 수열과 부분 문자열
- 회문 분할 II
- 풍선 터뜨리기: 역방향 구간 DP