동적 계획법 - 3. 실전 문제 응용

3. 실전 문제 응용동적 계획법(DP)을 실전 문제에 적용하면 최적의 해를 빠르게 구할 수 있습니다.이번 장에서는 경로 찾기, 문자열 및 수열 문제, 최적화 문제에서 DP를 활용하는 방법을 배웁니다.3-1. 경로 찾기 관련 문제📌 최단 경로 문제 (Minimum Path Sum) - 입력 검증 추가문제 설명m×n 크기의 2D 격자(grid)가 주어졌을 때,왼쪽 위에서 오른쪽 아래로 이동하는 최소 비용 경로를 찾는 문제입니다.이동 가능 방향: 오른쪽(→), 아래(↓)각 칸에는 이동 비용(양의 정수)이 주어짐.점화식dp[i][j]=min⁡(dp[i−1][j],dp[i][j−1])+grid[i][j]초기 조건:첫 번째 행과 첫 번째 열은 이동 경로가 1가지뿐이므로 누적합을 계산.시간 복잡도:O(m×n) (2..

2025.02.24