동적 계획법 (Dynamic Programming, DP)

개념

DP는 큰 문제를 작은 문제로 나누고, 그 결과를 저장하여 재활용하는 방식으로 문제를 해결하는 기법이다.

핵심 요약

• 같은 계산을 반복하지 않음
• 이전 단계의 최적 결과를 이용
• 중복 계산을 줄여 효율적으로 계산

---

DP 사고 과정

1. 문제를 쪼갤 수 있는지 확인

   • 큰 문제를 작은 하위 문제로 분리 가능해야 함
   • 예: “N일 때”를 “N-1일 때”로 표현 가능해야 함

2. 점화식 도출

   • 현재 상태를 이전 상태로 표현하는 식을 찾는 단계

3. 중복 계산 여부 확인

   • 같은 계산이 반복된다면 DP 적용 가능

4. 저장할 값 정의

   • dp 배열의 각 인덱스가 의미하는 값을 명확히 정의
   • 예: dp[i] = i번째 원소를 끝으로 하는 최대합 등

5. 기본값 설정

   • dp[0], dp[1] 등 최소 단위의 초기값 설정

6. 순차적 계산

   • 작은 인덱스부터 점화식에 따라 순서대로 계산

---

예시별 정리

1. 백준 11055 — 가장 큰 증가 부분 수열

문제 구조

• 입력: 수열
• 목표: 증가하는 부분 수열 중 합의 최대값

dp 정의

dp[i] = i번째 원소를 끝으로 하는 증가 부분 수열의 최대합

점화식

dp[i] = max(dp[i], dp[j] + arr[i])   (단, arr[j] < arr[i])

사고 과정

1. 현재 원소 arr[i]보다 작은 이전 원소 arr[j]를 탐색
2. 가능한 경우의 합 중 최댓값을 선택
3. dp 배열 중 최댓값이 전체 결과

핵심 요약

이전 원소 중 자신보다 작은 값에 이어붙인 최대합을 선택하는 구조

---

2. 백준 11052 — 카드 구매하기

문제 구조

• 입력: 카드팩 가격 배열
• 목표: 카드 N개를 구매할 때의 최대 금액

dp 정의

dp[i] = 카드 i개를 구매할 때의 최대 금액

점화식

dp[i] = max(dp[i - j] + arr[j - 1])   (1 ≤ j ≤ i)

사고 과정

1. i개를 만들기 위해 j개 + (i-j)개 조합을 고려
2. 모든 조합 중 최댓값 선택
3. dp[i]에 저장

핵심 요약

모든 가능한 조합을 비교하고, 최대값을 선택하는 반복 구조

---

3. 백준 10422 — 괄호

문제 구조

• 입력: 괄호 문자열의 길이 L
• 목표: 올바른 괄호 문자열의 개수

dp 정의

dp[n] = 길이 2n인 올바른 괄호 문자열의 개수

점화식

dp[n] = dp[0]*dp[n-1] + dp[1]*dp[n-2] + ... + dp[n-1]*dp[0]

사고 과정

1. 전체 괄호 문자열을 (A)B 형태로 분리
2. A, B 모두 각각 올바른 괄호 구조를 가져야 함
3. 가능한 모든 분할의 조합을 더함

핵심 요약

전체 구조를 좌우 두 부분으로 나누고, 각 조합의 곱을 누적하는 구조

---

세 문제를 통한 DP의 본질

문제	핵심 사고	저장 기준	점화식 형태
11055	이전 원소 합의 최댓값	마지막 원소 기준	누적 최대값
11052	가능한 구매 조합	카드 개수 기준	조합 최댓값
10422	괄호 구조 분할	괄호 쌍 개수 기준	곱의 누적

---

결론

DP는 단순한 배열 채우기가 아니라,
작은 단위 문제의 결과를 이용해 전체 문제를 해결하는 사고 과정이다.

핵심 포인트
1. dp[i]의 의미를 명확히 정의
2. 이전 결과로 현재를 유도하는 점화식 구성
3. 중복 계산 제거
4. 누적 계산을 통해 전체 문제 해결

세 문제 모두 공통적으로 “변하지 않는 하위 문제의 패턴”을 기반으로 동작하며,
이 패턴을 찾는 것이 DP 문제 해결의 핵심이다.