내일배움캠프 70일차 - 자료구조 & 알고리즘 13주차 : 동적 프로그래밍 입문 (DP)
DP(동적 프로그래밍)란?
재귀(문제 안의 같은 문제)가 포함된 문제를 풀 때 같은 계산을 반복하지 않게 장치하는 프로그래밍을 의미한다.
재귀에서 함수를 호출할 때 같은 입력의 값으로 같은 결과를 출력하는 상황이 발생할 수 있는데 이를 방지하기 위해 입출력값을 기억하고 필요할 때 계산대신 꺼내 쓰는 방식을 DP라고 한다.
점화식
n번째 피보나치 수 F(n) 은 이렇게 정의됩니다.
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)
"n번째 항을 이진 항들로 표현하는 수식" = 점화식(Recurrence Relation)
점화식은 DP를 하기 위해 필요한 핵심 요소이다.
점화식을 세울 수 없다면 문제 풀이를 시작할 수 없다.
DP의 원리
① 피보나치는 왜 느릴까
피보나치는 점화식을 그대로 옮겨 쓰는 방식이기 때문에 재귀 코드에는 문제가 없다.
하지만 "같은 함수를 같은 입력으로 여러 번 호출" 한다는 점에서 문제가 발생한다.
이를 "중복 부분 문제(Overlapping Subproblems)"라고 하며, 불필요한 계산을 하므로 피보나치의 n값이 높아질수록 호출횟수가 기하급수적으로 많아진다.
② 메모이제이션 - 답을 메모에 적자
Memoization = "memo(메모)하다". 계산한 값을 배열에 저장
 |
| 재귀 구조는 그대로, 두 줄 추가가 전부. 큰 문제 → 작은 문제로 내려가며 결과 저장 = 탑다운(Top-Down) DP. |
F(40)이라면 약 3억 번 → 79번. 시간 복잡도 O(2^n) → O(n)
③ 바텀업 - 작은 것부터 채워 올리기
 |
| 재귀 없이 반복문으로. 같은 결과, 다른 방향. 작은 문제 → 큰 문제로 올라가며 결과 저장 = 바텀 업(Bottom-Up) DP. |
※ 탑다운 (재귀+memo): 직관적·재귀 오버헤드
※ 바텀업 (반복문+dp): 빠름·스택안전, 실전에서 더 흔함.
DP의 조건
① 중복 부분 문제
: 같은 하위 문제가 여러 번 등장한다.
ex) 피보나치 - F(3)등의 문제가 여러 번 호출. 중복 호출이 없으면 메모할 이유가 없음.
② 최적 부분 구조
: 작은 문제의 답으로, 큰 문제의 답을 구성.
= 점화식을 세울 수 있는 문제
두 조건을 모두 만족해야 점화식을 세우고 DP를 적용할 수 있다.
그리디 vs DP
그리디는 매 순간 최선의 선택을 하지만,
항상 최적해를 보장하지 않는다.
그리디
- "지금 가장 좋아보이는 것"을 골라 빠르게 진행.
- 한번 고르면 되돌아가지 않음.
- 빠르지만, 틀린 답이 나올 수 있다.
DP
- "작은 문제부터 답을 다 구해" 저장하고 조합.
- 같은 계산은 한 번만 하고 재사용
- 조금 더 느리지만 최적을 보장한다.
공통점: 둘 다 "작은 문제 → 큰 문제"로 풀어간다. (= 점화식이 세워지는 문제)
점화식 예제
① 계단 오르기
n개의 계단. 한 번에 1칸 또는 2칸씩 오를 수 있다.
n번째 계단에 도달하는 서로 다른 방법은 몇 가지일까?
n=1 → (1) = 1가지
n=2 → (1+1), (2) = 2가지
n=3 → (1+1+1), (1+2), (2+1) = 3가지
n=4 → (1+1+1+1), (1+1+2), (1+2+1), (2+1+1), (2+2) = 5가지
경우 A
: (n-1)번째 칸에 있다가 1칸 올라옴
→ dp[n-1] 가지
경우 B
: (n-2)번째 칸에 있다가 2칸 올라옴
→ dp[n-2] 가지
∴ dp[n] = dp[n-1] + dp[n-2]
※ 피보나치와 똑같은 점화식, 그래서 답도 피보나치 수열이다.
② 계단 오르기 변형
이번엔 1·2·3칸씩 오를 수 있다고 한다. 이때의 점화식은 어떻게 되는가?
경우 A: (n-1)번째 칸에 있다가 1칸 올라옴 → dp[n-1] 가지
경우 B: (n-2)번째 칸에 있다가 2칸 올라옴 → dp[n-2] 가지
경우 C: (n-3)번째 칸에 있다가 3칸 올라옴 → dp[n-3] 가지
∴ dp[n] = dp[n-1] + dp[n-2] + dp[n-3]
점화식 한 줄 만 바뀌면 코드도 그 한 줄만 바뀐다.
이것이 DP의 강력함, 점화식만 손에 쥐면 나머지는 자동.
DP의 4단계 순서
① 상태 정의
: dp[i]가 "무엇을 의미하는지" 한 문장으로
② 점화식
: dp[i]를 더 작은 dp값들의 식으로
③ 초기값
: 가장 작은 경우의 값을 직접 정의
④ 답 도출
: 어디서 정답을 꺼낼지 결정
※ 가장 어려운 단계는 ②점화식이다. 막히면 ①상태 정의로.
※ dp[i]의 의미를 한 문장으로 적지 못하면 점화식도 정확히 쓸 수 없다.
예시) 계단 오르기
① 상태
: dp[i] = i번째 계단에 도달하는 방법의 수
② 점화식
: dp[i] = dp[i-1] + dp[i-2]
③ 초기값
: dp[1] = 1, dp[2] = 2
④ 답 도출
: dp[n]
※ 이 4칸을 채울 수만 있다면 코드는 거의 자동으로 나온다.
DP 예제
① 동전 교환 - 그리디로 못 풀던 문제
12주차에서 동전 {500, 400, 100}으로 800원, 그리디는 4개라고 했지만 정답은 2개(400+400). 이를 DP로 풀어보자.
1) 정의
dp[i] = i원을 만드는 데 필요한 최소 동전 수
: dp[i]는 각 동전 종류(coins)를 순회하여 i에서 coin을 한번 소모한 뒤에 남은 최소 동전 수가 이미 정의된 상태이고(≠INT_MAX), 정의된 횟수+1이 dp[i]보다 낮으면 dp[i]를 해당 값으로 갱신한다.
2) 점화식
: dp[i] = min(dp[i-각 coin] + 1)
3) 초기값
: dp[0] = 0
--계산--
→ dp[100] = dp[100-100] + 1 = dp[0] + 1 = 1
→ dp[200] = dp[200-100] + 1 = dp[100] + 1 = 2
→ dp[300] = dp[300-100] + 1 = dp[200] + 1 = 3
→ dp[400] = dp[400-400] + 1 = dp[0] + 1 = 1
→ dp[500] = dp[500-500] + 1 = dp[0] + 1 = 1
→ dp[600] = dp[600-500] + 1 = dp[100] + 1 = 2
→ dp[700] = dp[700-500] + 1 = dp[200] + 1 = 3
→ dp[800] = dp[800-400] + 1 = dp[400] + 1 = 2
∴ 따라서 dp[i]는 성립하며, 정답은 2이다.
② 최소 비용 경로 - 2차원 DP
격자는 오른쪽·아래쪽으로만 이동이 가능하다.
grid[i][j] = 해당 칸의 비용
1) 정의
dp[i][j] = 좌상단에서 해당 칸까지의 최소 비용
: 좌상단에서 오른쪽, 아래로만 이동하여 두 방향 중 비용이 적은 방향으로 선택
2) 점화식
: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
3) 초기값
: dp[0][0] = 1
--계산--
→ dp[0][1] = dp[0][0] + grid[0][1] = 1 + 3 = 4
→ dp[0][2] = dp[0][1] + grid[0][2] = 4 + 1 = 5
→ dp[1][0] = dp[0][0] + grid[1][0] = 1 + 1 = 2
→ dp[1][1] = min(dp[0][1], dp[1][0]) + grid[1][1] = min(4, 2) + 5 = 7
→ dp[1][2] = min(dp[0][2], dp[1][1]) + grid[1][2] = min(5, 7) + 1 = 6
→ dp[2][0] = dp[1][0] + grid[2][0] = 2 + 4 = 6
→ dp[2][1] = min(dp[1][1], dp[2][0]) + grid[2][1] = min(7, 6) + 2 = 8
→ dp[2][2] = min(dp[1][2], dp[2][1]) + grid[2][2] = min(6, 8) + 1 = 7
∴ 따라서 dp[i][j]는 성립하며, 정답은 7이다.
③ 집 도둑
일렬의 집에 돈이 있고, 도둑은 인접한 두 집을 동시에 털 수 없다(보안 시스템). 훔칠 수 있는 금액의 최댓값은?
gold[i] = 해당 집에서 훔칠 수 있는 금액
dp[i] = 0번째부터 i번째 집까지만 고려했을 때 훔칠 수 있는 최대 금액
: i번째 집을 털지 않으면 dp[i] = dp[i-1]
: i번째 집을 털면 dp[i] = dp[i-2] + gold[i]
2) 점화식
: dp[i] = max(dp[i-1], dp[i-2] + gold[i])
3) 초기값
: dp[0] = 3
: dp[1] = 7
--계산--
→ dp[2] = max(dp[1], dp[0] + gold[2]) = max(7, 3 + 4) = 7
→ dp[3] = max(dp[2], dp[1] + gold[3]) = max(7, 7 + 6) = 13
→ dp[4] = max(dp[3], dp[2] + gold[4]) = max(13, 7 + 5) = 13
∴ 따라서 dp[i]는 성립하며, 정답은 13이다.
CS 돋보기
DP 메모 = 캐싱의 알고리즘 버전
"계산한 결과를 저장 → 같은 입력이면 즉시 반환" = 캐싱(Caching)
DP 메모이제이션
: F(3) = 2 저장
: 같은 F(3) 호출 → 즉시 반환
CPU 캐시
: 가져온 데이터 보관
: 같은 주소 접근 → 즉시 반환
ex) DRAM:100클럭, L2:10클럭, L1:4클럭 (DRAM 대비 25배 빠름)
웹·DB 캐시 - 같은 원리, 다른 규모
브라우저 캐시
: 이미지·CSS 한 번 로드 → 재방문 즉시
CDN 캐시
: 자주 요청되는 콘텐츠를 가까운 서버에
Redis DB 캐시
: 쿼리 결과 메모리에 저장 (100ms → 1ms)
"컴퓨터 과학에서 가장 어려운 두 가지: 캐시 무효화 와 이름 짓기" - Phil Karlton
DP에서는 안전(F(3)은 변하지 않음). 웹·DB는 원본 변경 시 "오래된 답"을 가져올 수 있다는 함정이 있음.
실전에서는?
게임
- 경로 탐색 캐싱
- RPG 장비 조합 (배낭)
- 물리 이전 프레임 재활용 (매 프레임 다시 계산하면 60fps 불가)
웹·서버
- API 응답 캐싱(Redis)
- 추천 시스템 접수 계산
- 요금/배송비 조합 최적화 (100ms → 1ms)
일반 CS
- 최단 경로 (벨만-포드)
- 편집 거리·LCS
- HMM·강화학습 가치함수
- DNA 서열 정렬
★ 코딩 테스트 빈출 - "점화식을 세울 수 있는가"가 핵심 역량
오늘의 핵심
점화식
: 큰 문제를 작은 문제의 식으로 쓰기. DP의 핵심 도구
DP 본질
: "같은 계산을 두 번 하지 마라"
: 한 번 계산한 답을 저장하고 재사용
두 가지 구현
: 탑다운(재귀+memo)
: 바텀업(반복문+dp)
→ 결과 같음
적용 조건
: ① 중복 부분 문제, ② 최적 부분 구조 (= 점화식을 세울 수 있는가?)
4단계 프레임
: 상태 → 점화식 → 초기값 → 답. 새 문제는 무조건 이 순서
결과: O(2^n) → O(n). 메모 한 줄로 3억 번이 79번으로 줄어든다.
댓글
댓글 쓰기