개요
아래 내용은 DP(동적 프로그래밍)의 핵심 개념을 먼저 정리한 뒤, A5DP 패키지에 있는 실습 코드(계단/동전/최대·최소/수열/배낭)를 통해 “문제 정의 → 상태(state) 설계 → 점화식 → 초기값 → 반복 순서(탑다운/바텀업)”를 한 흐름으로 정리한 글이다.
DP(동적 프로그래밍)란?
DP는 큰 문제를 작은 하위 문제로 나누고, 하위 문제의 답을 한 번만 계산해 저장해두었다가 재사용하면서 전체 최적해를 만드는 방식이다.
이 “저장해두고 재사용한다”는 아이디어 때문에 DP를 메모이제이션(memoization) 관점에서 이해하는 것도 자연스럽다.
왜 DP가 필요한가 (피보나치 예시)
피보나치를 재귀로만 풀면 (f(n)=f(n-1)+f(n-2)) 구조 때문에 같은 값을 여러 번 다시 계산하면서 연산이 폭발한다.
DP는 계산한 (f(i))를 배열 등에 저장해두고 다시 꺼내 쓰므로 중복 계산을 제거해 성능을 크게 개선한다.
DP 접근 순서(사고 흐름)
DP는 “공식부터”가 아니라 “정의부터” 시작하는 게 핵심이다.
- 문제를 케이스로 나누고, 무엇을 저장할지(상태/state) 정의한다.
- 점화식(이전 상태로부터 현재 상태를 만드는 규칙)을 만든다.
- 초기값(바닥 조건)을 세팅하고, 반복 순서를 정해 전체를 채운다.
실습 1: 동전 문제로 DP 감 잡기 (A02동전문제)
Greedy로는 “가장 큰 동전부터”가 항상 정답이 아니기 때문에(예: 1,4,5로 13 만들기에서 5부터 고르면 막히는 상황) DP로 최소 개수를 구해야 한다는 흐름이 나온다.
이때 핵심은 “현재 금액 i를 만들려면 직전 금액들(i-coin)을 이미 최소로 만들어놨다”는 전제를 깔고 점화식을 세우는 것이다.
상태 정의
dp[i] = i원을 만드는 최소 동전 개수
점화식 아이디어
i원을 만드는 경우는 결국 “어떤 동전 coin 하나를 마지막에 추가”한 형태뿐이다.
그래서 후보는 dp[i - coin] + 1 들이고, 그 중 최솟값이 정답이다.
코드에서 개선 포인트(중요)
현재 실습 코드는 dp 초기값이 기본 0이라, “만들 수 없는 금액”이 있어도 0처럼 취급될 위험이 있다.
실전(예: 백준 2294 동전2)에서는 Arrays.fill(dp, INF) 같은 큰 값 초기화 + dp[0]=0 세팅이 사실상 필수다.
실습 2: 계단/멀리뛰기류 (A01계단관련)
계단/멀리뛰기는 “현재 위치에 도달하는 방법이 이전 몇 칸에서만 온다”는 구조가 깔끔해서 DP 입문용으로 좋다.
예를 들어 1칸 또는 2칸 이동만 가능하면, dp[i]는 dp[i-1]과 dp[i-2]의 조합으로 표현된다.
실습 3: 최대·최소 DP (A03최대값최소값)
정수삼각형, RGB거리, 내려가기 같은 문제들은 매 칸에서 “다음 선택지”가 제한되고, 그 중 최대/최소 누적 값을 구하는 형태로 자주 나온다.
포인트는 dp[i]를 “i까지 왔을 때의 최적값”으로 정의하고, 이전 상태들 중 가능한 것만 골라 최적을 갱신하는 것이다.
실습 4: 수열/문자열 DP (A04문자열수열)
LIS(가장 긴 증가하는 부분 수열) 같은 문제는 “현재 원소를 끝으로 하는 최적값”을 dp로 두면 점화식이 만들어진다.
또 “답(길이)”뿐 아니라 “경로(수열 자체)”를 복원해야 하면, 직전 인덱스를 저장하는 배열을 추가로 두고 역추적(backtracking)하는 방식이 자주 쓰인다.
실습 5: 배낭 문제 패밀리 (A05배낭문제)
배낭 문제는 “자원 한도(무게/비용/시간) 내에서 선택 조합을 구성해 최대/최소를 구하는 문제”로 이해하면 된다.
한 번만 선택 가능(0/1 배낭)인지, 여러 번 선택 가능(무한 배낭)인지에 따라 dp 갱신 순서가 달라지는 게 핵심 포인트다.
- 평범한 배낭(12865), 벼락치기(14728): 각 아이템을 1번만 사용
- 호텔(1106): 같은 도시 홍보를 여러 번 사용 가능(무한)
