CodingTest/자료구조-알고리즘
[DP-2] 1차원 DP 대표 유형 정리
the.Dev.Cat
2026. 5. 9. 22:51
Python 코딩테스트 알고리즘 스터디 8주차 — 동적 계획법(DP) 내용을 정리한 글이다.
1차원 DP 문제는 점화식 도출 방법론을 익히면 대부분 같은 패턴으로 풀린다.
1. 점화식 도출 방법론
점화식을 도출하는 방법은 다음 세 단계를 따른다.
1단계: dp[i]의 의미를 먼저 정의한다
무엇을 저장할지 결정하는 것이 가장 중요하다. dp[i]가 무엇을 의미하는지 명확하게 써둔 뒤 코드를 짜야 실수가 없다.
2단계: 마지막 선택을 기준으로 경우를 분기한다
dp[i]를 만들기 직전 단계에 어떤 선택이 가능했는지 나열한다. 각 선택에서 이전 dp 값이 어떻게 연결되는지 찾으면 점화식이 보인다.
3단계: 초기값(base case)을 설정한다
가장 작은 입력에서의 정답을 직접 정의한다. base case가 잘못되면 이후 모든 값이 틀린다.
2. 계단 오르기
n개의 계단이 있고 한 번에 1칸 또는 2칸씩 오를 수 있다. n번째 계단에 도달하는 방법의 수를 구하라.
| dp[i]의 의미 | i번째 계단에 도달하는 방법의 수 |
| 마지막 선택 | (i-1)번째에서 1칸 → dp[i-1]가지 (i-2)번째에서 2칸 → dp[i-2]가지 |
| 점화식 | dp[i] = dp[i-1] + dp[i-2] |
| 초기값 | dp[1] = 1, dp[2] = 2 |
n=1: [1] → 1가지
n=2: [1,1], [2] → 2가지
n=3: [1,1,1], [1,2], [2,1] → 3가지
n=4: dp[3]+dp[2] = 3+2 = 5가지
n=5: dp[4]+dp[3] = 5+3 = 8가지
n=2: [1,1], [2] → 2가지
n=3: [1,1,1], [1,2], [2,1] → 3가지
n=4: dp[3]+dp[2] = 3+2 = 5가지
n=5: dp[4]+dp[3] = 5+3 = 8가지
def climb_stairs(n):
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(climb_stairs(5))
print(climb_stairs(10))
8
89
구조가 피보나치와 동일하다. dp의 의미만 바뀌었을 뿐, 점화식 형태는 같다.
3. 최대 부분합: Kadane's Algorithm
배열에서 연속된 부분 배열의 합 중 최댓값을 구하는 문제다.
| dp[i]의 의미 | i번째 원소에서 끝나는 연속 부분 배열의 최대 합 |
| 마지막 선택 | i번째 원소 혼자 시작: arr[i] 이전 부분합에 이어 붙이기: dp[i-1] + arr[i] 더 큰 것을 선택 |
| 점화식 | dp[i] = max(arr[i], dp[i-1] + arr[i]) |
| 초기값 | dp[0] = arr[0] |
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
dp[0] = -2
dp[1] = max(1, -2+1) = max(1, -1) = 1
dp[2] = max(-3, 1+(-3)) = max(-3, -2) = -2
dp[3] = max(4, -2+4) = max(4, 2) = 4
dp[4] = max(-1, 4+(-1)) = max(-1, 3) = 3
dp[5] = max(2, 3+2) = max(2, 5) = 5
dp[6] = max(1, 5+1) = max(1, 6) = 6
dp[7] = max(-5, 6+(-5)) = max(-5, 1) = 1
dp[8] = max(4, 1+4) = max(4, 5) = 5
최댓값 = max(dp) = 6
dp[0] = -2
dp[1] = max(1, -2+1) = max(1, -1) = 1
dp[2] = max(-3, 1+(-3)) = max(-3, -2) = -2
dp[3] = max(4, -2+4) = max(4, 2) = 4
dp[4] = max(-1, 4+(-1)) = max(-1, 3) = 3
dp[5] = max(2, 3+2) = max(2, 5) = 5
dp[6] = max(1, 5+1) = max(1, 6) = 6
dp[7] = max(-5, 6+(-5)) = max(-5, 1) = 1
dp[8] = max(4, 1+4) = max(4, 5) = 5
최댓값 = max(dp) = 6
def max_subarray(arr):
dp = arr[:]
for i in range(1, len(arr)):
dp[i] = max(arr[i], dp[i - 1] + arr[i])
return max(dp)
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray(arr))
6
[4, -1, 2, 1]의 합이 6으로 최대다.
핵심은 "이전 부분합이 음수라면 버리고 혼자 새로 시작하는 편이 낫다"는 판단을
max(arr[i], dp[i-1]+arr[i])한 줄로 표현한다는 점이다.
4. 동전 교환: 최소 동전 수
coins 종류의 동전으로 amount원을 만들 때 필요한 최소 동전 수를 구하라.
| dp[i]의 의미 | i원을 만들기 위한 최소 동전 수 |
| 마지막 선택 | 마지막으로 동전 c를 사용했다면 나머지 (i-c)원을 최소로 만든 뒤 +1 모든 동전 c에 대해 dp[i-c]+1을 계산하고 최솟값 선택 |
| 점화식 | dp[i] = min(dp[i-c] + 1) (c ≤ i인 모든 동전) |
| 초기값 | dp[0] = 0, 나머지는 float('inf')로 초기화 |
coins = [1, 2, 5], amount = 11
dp[0] = 0
dp[1] = min(dp[0]+1) = 1 (동전 1 사용)
dp[2] = min(dp[1]+1, dp[0]+1) = 1 (동전 2 사용)
dp[3] = min(dp[2]+1, dp[1]+1) = 2
dp[4] = min(dp[3]+1, dp[2]+1) = 2 (동전 2 두 개)
dp[5] = min(dp[4]+1, dp[3]+1, dp[0]+1) = 1 (동전 5)
...
dp[11] = 3 (5+5+1)
dp[0] = 0
dp[1] = min(dp[0]+1) = 1 (동전 1 사용)
dp[2] = min(dp[1]+1, dp[0]+1) = 1 (동전 2 사용)
dp[3] = min(dp[2]+1, dp[1]+1) = 2
dp[4] = min(dp[3]+1, dp[2]+1) = 2 (동전 2 두 개)
dp[5] = min(dp[4]+1, dp[3]+1, dp[0]+1) = 1 (동전 5)
...
dp[11] = 3 (5+5+1)
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i and dp[i - coin] != float('inf'):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change([1, 2, 5], 11))
print(coin_change([2], 3))
3
-1
그리디로 동전 문제를 풀면 반례가 생기는 경우가 있다. DP는 모든 동전 선택지를 탐색하므로 항상 최적해를 구한다.
5. 집 도둑: 인접 불가 최대합
N개의 집이 일렬로 있고 각 집에 돈이 있다. 인접한 두 집을 동시에 털 수 없을 때 최대로 얻을 수 있는 돈은 얼마인가?
| dp[i]의 의미 | i번째 집까지 고려했을 때 얻을 수 있는 최대 금액 |
| 마지막 선택 | i번째 집을 턴다: dp[i-2] + money[i] i번째 집을 안 턴다: dp[i-1] |
| 점화식 | dp[i] = max(dp[i-2] + money[i], dp[i-1]) |
| 초기값 | dp[0] = money[0] dp[1] = max(money[0], money[1]) |
money = [2, 7, 9, 3, 1]
dp[0] = 2
dp[1] = max(2, 7) = 7
dp[2] = max(dp[0]+9, dp[1]) = max(11, 7) = 11
dp[3] = max(dp[1]+3, dp[2]) = max(10, 11) = 11
dp[4] = max(dp[2]+1, dp[3]) = max(12, 11) = 12
최대 금액 = 12 (집 0, 2, 4 → 2+9+1=12)
dp[0] = 2
dp[1] = max(2, 7) = 7
dp[2] = max(dp[0]+9, dp[1]) = max(11, 7) = 11
dp[3] = max(dp[1]+3, dp[2]) = max(10, 11) = 11
dp[4] = max(dp[2]+1, dp[3]) = max(12, 11) = 12
최대 금액 = 12 (집 0, 2, 4 → 2+9+1=12)
def house_robber(money):
n = len(money)
if n == 1:
return money[0]
dp = [0] * n
dp[0] = money[0]
dp[1] = max(money[0], money[1])
for i in range(2, n):
dp[i] = max(dp[i - 2] + money[i], dp[i - 1])
return dp[n - 1]
print(house_robber([2, 7, 9, 3, 1]))
print(house_robber([1, 2, 3, 1]))
12
4
6. 유형별 정리
아래 표는 1차원 DP에서 자주 등장하는 유형과 점화식 패턴을 정리한 것이다.
| 유형 | dp[i]의 의미 | 점화식 패턴 | 초기값 |
|---|---|---|---|
| 피보나치 | n번째 피보나치 수 | dp[i] = dp[i-1] + dp[i-2] |
dp[0]=0, dp[1]=1 |
| 계단 오르기 | i번째 계단까지의 경우의 수 | dp[i] = dp[i-1] + dp[i-2] |
dp[1]=1, dp[2]=2 |
| 최대 부분합 | i에서 끝나는 최대 연속합 | dp[i] = max(arr[i], dp[i-1]+arr[i]) |
dp[0]=arr[0] |
| 동전 교환 | i원 만들기 최소 동전 수 | dp[i] = min(dp[i-c]+1) |
dp[0]=0, 나머지 inf |
| 집 도둑 | i번째까지 최대 금액 | dp[i] = max(dp[i-2]+money[i], dp[i-1]) |
dp[0]=money[0] |
7. 시간 복잡도
| 유형 | 시간 복잡도 | 공간 복잡도 | 공간 최적화 |
|---|---|---|---|
| 피보나치 | O(n) | O(n) → O(1) | 변수 2개로 가능 |
| 계단 오르기 | O(n) | O(n) → O(1) | 변수 2개로 가능 |
| 최대 부분합 | O(n) | O(n) → O(1) | 변수 1개로 가능 |
| 동전 교환 | O(n × k) | O(n) | 최적화 어려움 |
| 집 도둑 | O(n) | O(n) → O(1) | 변수 2개로 가능 |
8. Python 자주 쓰는 메서드
DP 테이블 초기화
n = 6
dp_zero = [0] * n
dp_one = [1] * n
dp_inf = [float('inf')] * n
print(dp_zero)
print(dp_one)
print(dp_inf)
[0, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 1, 1]
[inf, inf, inf, inf, inf, inf]
[0] * n: 경우의 수, 누적합 DP의 기본 초기화[1] * n: 각 원소 자체가 기저 상태인 경우 (예: LIS 초기화)[float('inf')] * n: 최솟값을 구하는 DP에서 초기화
dp[i] = max(dp[i-1], ...) — 점화식 갱신 패턴
arr = [2, 7, 9, 3, 1]
n = len(arr)
dp = [0] * n
dp[0] = arr[0]
dp[1] = max(arr[0], arr[1])
for i in range(2, n):
dp[i] = max(dp[i - 2] + arr[i], dp[i - 1])
print(dp)
print(dp[-1])
[2, 7, 11, 11, 12]
12
dp[i] = max(...) 형태로 여러 전이 경로 중 최적을 선택하는 것이 1차원 DP의 핵심 패턴이다.
max() / min() — 여러 전이 중 최적 선택
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
dp = arr[:]
for i in range(1, len(arr)):
dp[i] = max(arr[i], dp[i - 1] + arr[i])
print(dp)
print(max(dp))
[-2, 1, -2, 4, 3, 5, 6, 1, 5]
6
max(a, b, c) 형식으로 인수를 여러 개 넘기면 가장 큰 값을 반환한다. min()도 동일하다.
enumerate() — 인덱스와 값을 동시에 순회
arr = [0, 3, 1, 6, 2, 2, 7]
dp = [1] * len(arr)
for i, val in enumerate(arr):
for j in range(i):
if arr[j] < val:
dp[i] = max(dp[i], dp[j] + 1)
print(dp)
print(max(dp))
[1, 2, 2, 3, 3, 3, 4]
4
enumerate()는 인덱스와 값을 동시에 받아 점화식에서 현재 원소와 이전 원소를 함께 다룰 때 유용하다. 위 코드는 LIS(가장 긴 증가하는 부분 수열) O(n²) 구현이다.
zip(dp, arr) — 두 배열 동시 순회
dp = [2, 7, 11, 11, 12]
arr = [2, 7, 9, 3, 1]
for d, a in zip(dp, arr):
print(f"dp={d}, arr={a}")
dp=2, arr=2
dp=7, arr=7
dp=11, arr=9
dp=11, arr=3
dp=12, arr=1
zip()으로 DP 테이블과 원본 배열을 동시에 순회하면 인덱스 실수를 줄일 수 있다.
sum(dp) — 최종 합산
dp = [1, 1, 2, 3, 5, 8]
print(sum(dp))
print(sum(dp[2:5]))
20
10
경우의 수를 합산하거나 슬라이싱과 결합해 특정 구간의 합을 구할 때 사용한다.
9. 연습 문제
초급
| 번호 | 문제 | 난이도 | 핵심 접근 |
|---|---|---|---|
| 12914 | 멀리 뛰기 | Lv.2 | dp[i] = dp[i-1] + dp[i-2], 계단 오르기와 구조 동일 |
| 12913 | 땅따먹기 | Lv.2 | 행별 최대값 누적, 1차원 DP를 2D 배열에 적용 |
| 12971 | 스티커 | Lv.3 | 원형 집 도둑, 첫/마지막 스티커 포함 여부로 두 경우 분리 |
중급
| 번호 | 문제 | 난이도 | 핵심 접근 |
|---|---|---|---|
| 42897 | 도둑질 | Lv.3 | 원형 집 도둑, 첫 집/마지막 집 포함 여부 두 경우 비교 |
| 43105 | 정수 삼각형 | Lv.3 | 꼭대기부터 최댓값 누적, 타뷸레이션 적용 |
| 42895 | N으로 표현 | Lv.3 | 사용 횟수별 만들 수 있는 수 집합 BFS/DP |