DP(다이나믹 프로그래밍), 중복 계산을 줄여주는 알고리즘

DP(다이나믹 프로그래밍), 중복 계산을 줄여주는 알고리즘

이번에는 코딩테스트에서 자주 나오는 DP, 다이나믹 프로그래밍에 대해 공부했다.

처음에는 이름부터 어렵게 느껴졌다.
Dynamic Programming이라는 이름만 보면 뭔가 복잡한 알고리즘처럼 보이지만, 핵심은 생각보다 단순하다.

한 번 계산한 값은 다시 계산하지 말고 저장해두었다가 재사용하는 것이다.

즉, DP는 이전에 구한 작은 문제의 답을 이용해서 더 큰 문제의 답을 구하는 방식이다.

---

1. DP란 무엇인가?

DP는 Dynamic Programming의 줄임말이고, 한국어로는 동적 계획법이라고 부른다.

하지만 이름보다 중요한 것은 개념이다.

DP의 핵심은 다음과 같다.

 

핵심 개념설명

저장	한 번 구한 답을 배열 등에 저장한다
재사용	같은 계산이 필요할 때 다시 계산하지 않고 꺼내 쓴다
작은 문제	작은 문제의 답을 먼저 구한다
큰 문제	작은 문제의 답을 이용해 큰 문제의 답을 만든다

쉽게 말하면 DP는 계산 결과를 적어두는 노트와 비슷하다.

한 번 계산한 값을 노트에 적어두면, 다음에 같은 값이 필요할 때 다시 계산하지 않아도 된다.
코딩에서는 이 노트 역할을 dp 배열이 한다.

int[] dp = new int[n + 1];

---

2. 왜 DP가 필요할까?

예를 들어 계단을 오른다고 생각해보자.

한 번에 1칸 또는 2칸씩 올라갈 수 있다고 할 때,
5칸 계단을 오르는 방법은 몇 가지인지 구해야 한다.

직접 하나씩 세어볼 수도 있지만, 계단이 10칸, 100칸, 1,000칸으로 늘어나면 직접 세기 어렵다.

이럴 때 DP를 사용할 수 있다.

계단 문제에서는 이런 식으로 생각할 수 있다.

5칸에 도착하는 방법은
4칸에서 1칸 올라오는 방법과
3칸에서 2칸 올라오는 방법을 합친 것이다.

즉, 5칸의 답을 구하기 위해 4칸의 답과 3칸의 답을 사용한다.

dp[5] = dp[4] + dp[3]

이처럼 DP는 이전 답을 이용해서 현재 답을 구하는 방식이다.

---

3. 계단 오르기 예시로 이해하기

한 번에 1칸 또는 2칸씩 오를 수 있다고 하자.

각 칸까지 가는 방법의 수를 표로 정리하면 다음과 같다.

계단 칸 수방법 수

1칸	1
2칸	2
3칸	3
4칸	5
5칸	8

규칙을 보면 다음과 같다.

3칸 = 2칸까지 가는 방법 + 1칸까지 가는 방법
4칸 = 3칸까지 가는 방법 + 2칸까지 가는 방법
5칸 = 4칸까지 가는 방법 + 3칸까지 가는 방법

즉, 현재 칸까지 가는 방법은 바로 전 칸과 두 칸 전의 방법 수를 더하면 된다.

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

이 식이 바로 이 문제의 규칙이다.

---

4. dp 배열의 의미 정하기

DP 문제를 풀 때 가장 먼저 해야 할 일은 dp[i]의 의미를 정하는 것이다.

계단 오르기 문제에서는 이렇게 정할 수 있다.

dp[i] = i칸까지 올라가는 방법의 수

이 의미를 정하지 않고 바로 코드를 작성하려고 하면 헷갈리기 쉽다.

DP 문제는 결국 dp 배열에 무엇을 저장할 것인가를 정하는 것이 중요하다.

문제 유형dp 의미 예시

계단 오르기	dp[i] = i칸까지 가는 방법 수
최소 비용	dp[i] = i번째까지 가는 최소 비용
최대 점수	dp[i] = i번째까지 얻을 수 있는 최대 점수
타일링	dp[i] = i길이를 채우는 방법 수

DP는 dp[i]의 의미를 잘 잡으면 절반은 해결한 것과 비슷하다.

---

5. 초기값 정하기

DP에서는 모든 값을 점화식으로만 구할 수 없다.
처음 시작이 되는 값은 직접 정해주어야 한다.

계단 문제에서는 다음과 같다.

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

1칸까지 가는 방법은 1가지이다.

1

2칸까지 가는 방법은 2가지이다.

1 + 1
2

그래서 dp[1]과 dp[2]는 직접 정해준다.

그다음부터는 이전 값을 이용해서 구할 수 있다.

---

6. 점화식 찾기

점화식은 쉽게 말하면 규칙이다.

DP에서는 현재 값을 이전 값들로 어떻게 만들 수 있는지 찾아야 한다.

계단 문제에서는 다음과 같다.

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

이유는 간단하다.

i번째 칸에 도착하는 방법은 두 가지이다.

도착 방법설명

i - 1칸에서 1칸 올라오기	바로 전 칸에서 오는 경우
i - 2칸에서 2칸 올라오기	두 칸 전에서 오는 경우

그래서 두 경우를 더하면 i칸까지 가는 전체 방법 수가 된다.

 

---

7. Java 코드로 작성하기

계단 오르기 문제를 Java 코드로 작성하면 다음과 같다.

class Main {
    public static void main(String[] args) {
        int n = 5;

        int[] dp = new int[n + 1];

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

        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        System.out.println(dp[n]);
    }
}

출력 결과는 다음과 같다.

8

여기서 가장 중요한 코드는 이 부분이다.

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

이 한 줄이 이전에 구한 답을 사용해서 현재 답을 만드는 부분이다.

---

8. DP 접근 순서

DP 문제를 풀 때는 아래 순서로 접근하면 된다.

순서질문

1	dp[i]는 무엇을 의미하는가?
2	초기값은 무엇인가?
3	이전 값으로 현재 값을 어떻게 만들 수 있는가?
4	답은 dp[n]인가, 아니면 dp 배열 중 최댓값/최솟값인가?

나는 특히 1번이 가장 중요하다고 느꼈다.

dp[i]의 의미를 정하지 않으면 점화식도 세우기 어렵다.

DP 문제를 만나면 무작정 코드를 쓰기보다, 먼저 dp[i]가 무엇을 저장하는지부터 정해야 한다.

---

9. DP와 DFS의 차이

이전에 DFS 문제를 공부하면서 모든 경우의 수를 탐색하는 문제를 풀어보았다.

DFS는 보통 모든 경우를 직접 내려가며 탐색한다.

+를 선택하는 경우
-를 선택하는 경우
모든 가지를 끝까지 확인한다

반면 DP는 중복 계산을 줄이는 데 초점이 있다.

이미 계산한 답은 저장해두고 다시 사용한다

구분DFSDP

핵심	모든 경우를 탐색	중복 계산을 저장하고 재사용
느낌	가지를 끝까지 내려감	이전 답을 이용해 다음 답을 만듦
자주 쓰는 문제	경로 탐색, 모든 경우의 수	최댓값, 최솟값, 방법의 수
중요한 질문	어떤 선택지가 있는가?	이전 답으로 현재 답을 만들 수 있는가?

DP도 재귀로 구현할 수 있지만, 처음 공부할 때는 반복문 + dp 배열 방식이 더 이해하기 쉬운 것 같다.

---

10. DP는 언제 떠올리면 좋을까?

문제에서 다음과 같은 느낌이 나오면 DP를 의심해볼 수 있다.

가장 큰 값
가장 작은 값
방법의 수
경우의 수가 너무 많음
같은 계산이 반복됨
이전 결과를 이용할 수 있음

특히 중요한 질문은 이것이다.

현재 답을 이전 답으로 만들 수 있는가?

이 질문에 “그렇다”라고 답할 수 있다면 DP일 가능성이 높다.

---

11. DP 문제에서 자주 나오는 유형

코딩테스트에서 DP는 다양한 형태로 나온다.

유형예시

방법의 수	계단 오르기, 타일링
최댓값	정수 삼각형, 카드 구매하기
최솟값	최소 비용, 동전 문제
경로 수	격자에서 이동하는 경우의 수
문자열 비교	LCS, 편집 거리

처음부터 어려운 문제를 풀기보다, 아래 유형부터 연습하는 것이 좋을 것 같다.

피보나치
계단 오르기
타일링
정수 삼각형
최소 비용 문제

---

12. 시간복잡도와 공간복잡도

계단 오르기 DP를 기준으로 보면, 1부터 n까지 한 번씩 계산한다.

따라서 시간복잡도는 다음과 같다.

O(N)

dp 배열에 n개만큼 값을 저장하므로 공간복잡도도 다음과 같다.

O(N)

구분복잡도이유

시간복잡도	O(N)	1부터 N까지 한 번씩 계산
공간복잡도	O(N)	dp 배열에 N개 값을 저장

만약 이전 두 값만 필요하다면 배열을 쓰지 않고 변수 두 개만으로도 풀 수 있다.
그 경우 공간복잡도는 O(1)로 줄일 수 있다.

하지만 처음 DP를 공부할 때는 dp 배열을 직접 만들어보는 것이 이해에 더 도움이 된다.

---

13. 내가 이해한 DP 핵심

이번에 DP를 공부하면서 가장 크게 이해한 점은 이것이다.

DP는 한 번 구한 답을 저장해두고 다시 사용하는 방식이다.

그리고 DP 문제를 풀 때 가장 먼저 해야 할 일은 dp[i]의 의미를 정하는 것이다.

dp[i]는 무엇을 저장하는가?

계단 문제에서는 다음과 같다.

dp[i] = i칸까지 올라가는 방법의 수

그다음 초기값을 정하고, 이전 값으로 현재 값을 만드는 규칙을 찾으면 된다.

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

---

마무리

DP는 이름은 어렵지만, 핵심은 단순하다.

한 번 구한 답을 저장해두고 다시 쓰는 것이다.

코딩테스트에서 DP 문제를 만나면 바로 점화식부터 찾으려고 하기보다,
먼저 아래 순서로 생각해야겠다.

1. dp[i]의 의미를 정한다.
2. 초기값을 정한다.
3. 이전 값으로 현재 값을 만드는 규칙을 찾는다.
4. 반복문으로 dp 배열을 채운다.