[코드트리] DP 쉽게 이해하기 (개념부터 구현까지 총정리)

알고리즘을 공부하다 보면 "이 문제는 DP로 풀어야 합니다"라는 말을 자주 듣게 됩니다. 하지만 처음에는 DP가 굉장히 어렵고 추상적으로 느껴졌습니다. 저 역시 처음에는 "그냥 규칙 찾고 배열에 저장하는 거 아닌가?" 정도로만 이해했었습니다.

이번 글에서는 제가 DP를 이해하게 된 방식으로, 최대한 쉽게 설명해보려고 합니다.

---

DP란 무엇일까?

DP(Dynamic Programming, 동적 계획법)는 "이미 계산한 결과를 저장해두고 다시 사용하는 방법" 입니다.

예를 들어 피보나치 수열을 생각해보겠습니다.

F(5)
= F(4) + F(3)

F(4)
= F(3) + F(2)

F(3)
= F(2) + F(1)

이렇게 재귀로 계산하면 F(3)이나 F(2)를 여러 번 계산하게 됩니다.

즉,

• 같은 계산을 반복한다.
• 불필요한 연산이 많아진다.

DP는 이 문제를 해결하기 위해

"한 번 계산한 값은 저장해두고 다음에 필요하면 가져다 쓰자"

라는 아이디어를 사용합니다.

---

저는 DP를 이렇게 이해했습니다

처음에는 DP라는 이름 때문에 굉장히 복잡한 알고리즘인 줄 알았습니다.

하지만 공부하면서 느낀 것은,

DP는 문제를 작은 문제로 나누고 그 결과를 저장하는 기술이라는 것입니다.

마치 계단을 올라간다고 생각하면 쉽습니다.

5번째 계단에 가기 위해서는

• 3번째 계단에서 2칸 올라오기
• 4번째 계단에서 1칸 올라오기

둘 중 하나가 가능합니다.

그렇다면

5번째 계단까지 가는 방법 수
=
3번째 계단까지 가는 방법 수
+
4번째 계단까지 가는 방법 수

 

처럼 이전 결과를 활용해서 현재 결과를 구할 수 있습니다.

DP 문제들은 대부분 이런 식으로

"현재 상태를 이전 상태로 표현할 수 있는가?"

를 찾는 것이 핵심입니다.

---

DP를 적용한 코드트리 문제 풀이

예제로 많이 등장하는 "계단 오르기" 유형을 생각해보겠습니다.

문제

• 1칸 또는 2칸씩 이동 가능
• N번째 계단까지 도달하는 방법의 수 구하기

---

1. DP 배열 정의하기

먼저 의미를 정합니다.

dp[i]
=
i번째 계단까지 도달하는 방법의 수

DP 문제는 항상

"dp 배열이 무엇을 의미하는지"

를 먼저 정의하는 것이 중요합니다.

---

2. 점화식 찾기

i번째 계단에 도착하려면

• i-1 계단에서 1칸 이동
• i-2 계단에서 2칸 이동

둘 중 하나입니다.

따라서

dp[i] = dp[i-1] + dp[i-2]

가 됩니다.

이 식을 점화식이라고 부릅니다.

---

3. 초기값 설정하기

점화식만으로는 계산할 수 없습니다.

시작점이 필요합니다.

dp[1] = 1
dp[2] = 2

---

4. 구현

n = int(input())

dp = [0] * (n + 1)

dp[1] = 1

if n >= 2:
    dp[2] = 2

for i in range(3, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

print(dp[n])

시간복잡도는 O(N)입니다.

---

DP 문제를 풀 때 사용하는 순서

DP 문제를 만나면 항상 아래 순서대로 생각합니다.

1단계

dp 배열의 의미 정의

dp[i]가 무엇을 의미하는가?

---

2단계

현재 상태를 이전 상태로 표현

dp[i]
=
?

---

3단계

초기값 설정

dp[0]
dp[1]

등의 시작값 확인

---

4단계

반복문으로 채우기

보통 작은 값부터 큰 값으로 진행합니다.

---

자주 하는 실수

1. DP 배열 의미를 정하지 않고 시작하기

가장 흔한 실수입니다.

DP는 코드를 먼저 쓰는 것이 아니라

dp[i]가 무엇인가?

를 먼저 정해야 합니다.

---

2. 초기값을 빼먹기

점화식이 맞더라도

dp[1]
dp[2]

가 없으면 계산이 불가능합니다.

---

3. 인덱스 범위 실수

for i in range(3, n + 1)

처럼 범위를 정확히 확인해야 합니다.

특히 n이 1 또는 2인 경우를 조심해야 합니다.

---

4. 무조건 DP라고 생각하기

문제를 풀다 보면 DP처럼 보여도

실제로는

• 그리디
• BFS
• DFS

로 더 쉽게 풀리는 경우가 많습니다.

DP는

"이전 결과를 저장하면서 재사용할 수 있는 구조인지"

를 먼저 확인해야 합니다.

---

마무리

제가 DP를 공부하면서 가장 크게 느낀 점은 "공식을 외우는 알고리즘이 아니다"라는 것입니다.

처음에는 점화식을 암기하려고 했지만, 실제로 중요한 것은

1. dp 배열의 의미를 정의하고
2. 현재 상태를 이전 상태로 표현하고
3. 초기값을 설정하는 것

이었습니다.

 

이 세 가지만 차근차근 생각하면 생각보다 많은 DP 문제를 해결할 수 있습니다.

DP가 어렵게 느껴진다면 점화식을 외우기보다,

"현재 상태를 이전 상태로 어떻게 만들 수 있을까?"

를 먼저 고민해보는 것을 추천합니다.

코드트리에서 다양한 DP 문제를 풀어보면서 감을 익혀보세요!

코드트리 바로가기: CodeTree