최적 경로의 부분 구조
서울에서 부산까지의 최적 경로는 대전까지의 최적과 대전에서 부산까지의 최적으로 나뉜다. 부분 문제의 최적해가 전체의 최적해를 구성한다는 이 성질이 DP가 성립하는 조건이다.
격자 경로 문제의 DP 테이블 채우기와 역추적 과정 시각화.
격자의 값을 직접 바꾸며 DP 테이블이 한 칸씩 채워지는 과정을 보고, 완성된 표에서 역추적으로 최적 경로가 복원되는 원리를 단계 재생으로 확인합니다.
큰 문제를 겹치는 부분 문제로 쪼개고, 한 번 구한 답은 저장해 다시 쓴다. 이 격자에서는 왼쪽 위에서 오른쪽·아래로만 이동하며, 각 셀의 최적값은 위/왼쪽 중 더 좋은 값에 자신의 값을 더해 확정된다. 표가 모두 채워지면 역추적이 최적 경로를 복원한다.
시간복잡도 O(R * C)
dp[r][c] = a[r][c] + max(dp[r-1][c], dp[r][c-1])
서울에서 부산까지의 최적 경로는 대전까지의 최적과 대전에서 부산까지의 최적으로 나뉜다. 부분 문제의 최적해가 전체의 최적해를 구성한다는 이 성질이 DP가 성립하는 조건이다.
git diff, 맞춤법 교정, DNA 서열 정렬은 모두 편집 거리 DP다. 이 격자와 같은 2차원 테이블을 채운 뒤 역추적해 어떤 변경이 있었는지 복원한다.
순진한 재귀는 같은 부분 문제를 지수적으로 반복해서 푼다. 테이블에 답을 기록하는 것만으로 시간 복잡도가 O(2ⁿ)에서 O(n²)으로 줄어든다.