[DP-2] 1차원 DP 대표 유형 정리

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가지

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

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)

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)

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