DP(Dynamic Programming)

2025. 6. 12.

💡 DP란? (Dynamic Programming)

"반복되는 계산을 저장해서 중복 계산을 줄이는 방법"

: 큰 문제를 → 작은 문제로 쪼개서 → 풀어놓고 → 그 결과를 재사용

---

🔧 왜 필요한가?

완전탐색(DFS 등)은 모든 경우를 다 탐색

→ 시간 오래 걸림 (O(2ⁿ), O(n!) 등)

그런데 중복되는 계산이 많다.

​

👉 이미 한 번 계산했던 결과를 저장해서 재활용하면 빠름!

DP는 중복되는 계산을 한 번만 수행하고 저장해서, 불필요한 반복을 없애줌

---

🔑 DP의 핵심 아이디어

개념	설명
최적 부분 구조	큰 문제의 최적해가 작은 문제의 최적해로 구성됨
중복 부분 문제	같은 계산이 반복됨
메모이제이션 (Memoization)	계산한 결과를 저장해서 재사용
상향식 (Bottom-up)	작은 문제부터 차근차근 풀어 올라감

작은 문제부터 차례로 풀고 저장

같은 문제가 또 나오면 → 기존 저장값 사용

보통 배열 dp[] 에 저장함.

---

📦 예시로 쉽게 보기

유명한 배낭 문제 (Knapsack problem)로 예를 들어보면

문제: N개의 물건이 있고, 무게 제한이 W일 때, 최대 가치 구하기

물건	가치	무게
A	60	10
B	100	20
C	120	30

무게 제한이 50일 때 최대 가치는?

단순 조합으로 전부 다 탐색하면 경우의 수 너무 많음.

​

DP로 풀면:

dp[i][w]: i번째 물건까지 고려했을 때, 무게 w에서의 최대 가치

 

이걸 점화식으로 만들어서 풀면 O(N * W) 시간만에 해결 가능함.

---

적용하기 좋은 경우	예시
중복 계산이 많다	피보나치, 조합, 최단경로 등
부분 문제 결과가 전체 결과에 도움이 된다	배낭문제, 최대 부분합 문제 등
최적해를 구할 때	가장 큰 값, 최소 비용 등

​

이 문제에서 고민할 것:

각 물건을 "넣을까? 말까?" → 이게 바로 조합의 핵심.

모든 경우를 다 확인하면 총 2^3 = 8가지 경우가 있지만

DP는 이렇게 다 확인하지 않고 중복된 계산을 줄인다.

​

<코딩>

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N = 3;  // 물건 3개
    int W = 50; // 최대 무게 50

    // 물건들의 무게, 가치
    vector<int> weight = {10, 20, 30};
    vector<int> value = {60, 100, 120};

    // dp 테이블 만들기: (N+1)행, (W+1)열
    vector<vector<int>> dp(N+1, vector<int>(W+1, 0));
    // dp[0][w]는 물건 0개일 때 항상 0 → 초기값 0으로 채움.

    for (int i = 1; i <= N; ++i) { // i: 1번 ~ N번 물건까지 고려
        for (int w = 0; w <= W; ++w) {  // w: 현재 배낭에 담은 무게
            if (w >= weight[i-1]) {  // 현재 무게 w가 이 물건을 담을 수 있을 때
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i-1]] + value[i-1]);
                /* 이 물건을 담을지 말지 선택해서 최적값 저장
                   dp[i-1][w] → 안 담은 경우
                   dp[i-1][w - weight[i-1]] + value[i-1] → 담은 경우 둘 중 더 큰 값을 선택 */
            } else {
                dp[i][w] = dp[i-1][w];
            } // 이 물건이 너무 무거워서 못 담으면 → 그냥 이전 값을 유지

    }
    cout << "최대 가치: " << dp[N][W] << endl;
    return 0;
}

최종 dp 테이블

i / w	0	10	20	30	40	50
0	0	0	0	0	0	0
1	0	60	60	60	60	60
2	0	60	100	160	160	160
3	0	60	100	160	180	220

dp[3][50] = 220 이 정답!

​

​

 

DP 핵심 아이디어

dp[i][w] = 앞에서 i번째 물건까지 고려했을 때, 무게 w 이하로 담아서 만들 수 있는 최대 가치

"이전까지 계산한 결과를 저장해놓고 재활용하자!" → 이게 DP.

​

DP 점화식 (가장 핵심) : 물건을 하나씩 보면서, 매번 두 가지 선택을 한다.

1️⃣ 이 물건을 안 담을 경우:

dp[i][w] = dp[i-1][w]

(이전 결과 그대로 가져오기)

2️⃣ 이 물건을 담을 경우:

담으려면 무게 w가 weight[i-1]보다 커야 한다.

그러면: dp[i][w] = dp[i-1][w - weight[i-1]] + value[i-1]

👉 이 둘 중에서 더 큰 값을 선택.

​

---

추가 예시

예제: 피보나치 수열

일반 재귀 (비효율적, O(2ⁿ))

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

DP로 최적화 (O(n))

int dp[100];

int fib(int n) {
    if (n <= 1) return n;
    if (dp[n] != 0) return dp[n];
    return dp[n] = fib(n-1) + fib(n-2);
}

→ 이미 구한 fib(n-1), fib(n-2)를 재사용

​

DP는 언제 쓰냐?

상황	DFS/백트래킹	DP
경우의 수가 적음	DFS	DFS
경우의 수가 많고 중복됨	DFS 느림	DP가 훨씬 빠름
최적해 구할 때	조건에 따라 다름	DP 추천

---

??? 근데 왜!!! 함수를 만들지 않고 main 함수에서 for문을 도는 방식을 사용하는가?!?!?!?

1️⃣ 지금까지 본 구조

for (int i = 1; i <= N; ++i) {
    for (int w = 0; w <= W; ++w) {
        ... dp 채우기 ...
    }
}

보통 DP 문제는 이렇게 **"테이블을 채워나가는 반복문"**으로 바로 푸는 경우가 많음

​

이 방식이 좋은 이유:

DP 테이블을 bottom-up 방식으로 한 번에 채워서 효율적.

불필요한 함수 호출이 없다 → 속도가 빠르다.

메모리와 시간 낭비가 적다.

​

2️⃣ 함수로 분리하는 방법

void knapsackDP(vector<int>& weight, vector<int>& value, int N, int W, vector<vector<int>>& dp) {
    for (int i = 1; i <= N; ++i) {
        for (int w = 0; w <= W; ++w) {
            if (w >= weight[i-1])
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i-1]] + value[i-1]);
            else
                dp[i][w] = dp[i-1][w];
        }
    }
}

int main() {
    ...
    knapsackDP(weight, value, N, W, dp);
    cout << dp[N][W];
}
3️⃣

 

3️⃣ 그럼 왜 보통 그냥 for문으로 작성하나?

​

✔ DP는 일반적으로 함수 호출이 반복적으로 필요하지 않음

→ 어차피 테이블 전체를 채우니까 호출보단 바로 채우는게 효율적

✔ 함수 호출 방식은

가독성은 조금 더 좋을 수 있음

속도는 약간 손해볼 수 있음 (매번 인자 전달 등)

✔ 특히 C++은 함수 호출 비용 (call overhead) 이 꽤 있기 때문에

for문으로 바로 채우는게 실전 대회, 알고리즘 문제 풀 때는 더 빠름.

​

4️⃣ 근데 함수로 쪼개야 할 때도 있음:

​

여러 DP 문제를 동시에 풀 때

knapsack 부분을 라이브러리화할 때

코드 재사용성을 높일 때

---

방식	특징	주로 사용하는 곳
for문 내부에서 DP	가장 빠르고 실전적	알고리즘 문제풀이, 대회
함수 분리 DP	코드 재사용성, 가독성	실무, 라이브러리 작성

"DP는 결국 테이블을 채우는 일이다" → 이걸 어떻게 조직하느냐가 차이일 뿐

​

---

✅ DFS + 백트래킹 (조합식 코드)와의 차이

DFS(깊이 우선 탐색)는 사실상 이런 식의 분기 구조를 가짐

 	 [시작]
         /   \
      선택   선택X
      /  \     ...
   선택 선택X

이처럼 *분기(branch)*가 계속 생기기 때문에, 재귀 함수로 표현하는 게 아주 직관적이고 깔끔함

void Combination(...) {
    if (...) {
        ...
    } else {
        // 선택하는 경우
        Combination(...);
        // 선택하지 않는 경우
        Combination(...);
    }
}

📌 이 방식의 특징:

상태공간 탐색 (State space search)

→ 가능한 모든 경우의 수를 재귀적으로 탐색.

매 선택마다 "뽑을까 말까" → 트리 구조로 분기.

재귀함수 호출이 자연스럽게 상태를 스택으로 유지해줘서

→ sum_s, sum_c 를 매 호출마다 별도로 관리 가능.

재귀 호출이 많긴 하지만 메모리는 적게 쓴다 (스택 활용).

​

✅ 함수 호출이 유리한 이유

항목	설명
각 단계마다 새로운 선택을 시도	재귀 호출로 분기마다 새로운 상태를 넘겨주기 쉬움
현재 상태(sum, idx 등) 보존	매 재귀 호출에서 지역 변수처럼 값이 유지됨
백트래킹이 자연스럽다	함수 호출이 끝나면 자동으로 이전 상태로 돌아감
코드가 짧고 직관적	직접 stack을 안 써도 스택처럼 동작함 (call stack)

각 단계에서 상태를 유지해주는 데 함수 호출 자체가 유용.

로직을 나누기도 간결함 (선택 vs 비선택)

백트래킹은 "불가능한 가지 빨리 자르기" 에 최적 → pruning 쉽게 가능

---

✅ DP (Dynamic Programming)

📌 DP의 특징:

중복되는 부분문제(subproblem)를 한번만 푼다 → 효율적.

테이블(dp[][] 등)을 만들어서 반복문으로 상태 저장.

함수 호출은 필요 없고, 주로 for문으로 채움.

상태 유지가 테이블에 있으므로 별도 스택 관리가 필요 없다.

상태가 많을수록(조합 수가 많을수록) 효율성이 급격히 올라간다.

---

✅ 비교표

방식	DFS + 백트래킹	DP
상태 관리	재귀 호출 스택	DP 테이블 (반복문 중심 or 재귀+메모이제이션)
코드 스타일	간결, 직관적	반복문 위주
시간복잡도	O(2^N) (완전탐색)	O(NW), O(N^2), 최적
중복계산	분기마다 계산 => 많음 (따라서 가지치기 필요)	전체 경우를 메모리에 저장 => 없음 (저장해둠)
문제 유형	작은 입력, 조합, 가지치기 조합/순열/게임판 탐색 등	큰 입력, 최적화 문제 최댓값/최솟값/경우 수 등
활용 목적	상태 추적/백트래킹이 목적	최적값 계산이 목적

---

✅ 쉽게 말하면:

| 🎯 DFS+백트래킹 → "경우의 수를 다 보는 문제" |

| 🎯 DP → "최적의 값을 구하는 문제" (부분문제 중복 존재) |

​

💡 결론

조합으로 합 최대 구하기 문제는:

DFS+백트래킹 → 재귀함수 매우 적합 (조합이 본질이니까)

배낭문제 (Knapsack Problem) → DP가 훨씬 유리 (부분문제 중복)

---

??? 이차원 배열을 만들면 vector의 크기가 너무 커지지 않는가?!?!?!?

​

vector<vector<int>> dp(N+1, vector<int>(W+1, 0));

​

2차원 DP 테이블을 만든다 → 공간 복잡도: O(N * W)

지금은 N=3, W=50 이니까: 3 * 50 = 150 칸 → 부담 없는데

만약 N=1000, W=100000 이 되면 → 메모리 초과 가능

​

그래서 공간 최적화가 자주 사용된다

​

사실 이 문제는

dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i-1]] + value[i-1]);

이렇게 이전 행(i-1행) 만 사용하니까

👉 매번 이전 결과만 유지하면 된다.

​

최적화된 1차원 DP (공간복잡도: O(W))

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N = 3;
    int W = 50;

    vector<int> weight = {10, 20, 30};
    vector<int> value = {60, 100, 120};

    vector<int> dp(W+1, 0);

    for (int i = 0; i < N; ++i) {
   //물건 하나씩 확인! 지금 보고 있는 물건의 무게 = weight[i], 이 물건의 가치 = value[i]
        for (int w = W; w >= weight[i]; --w) {
        // 지금 무게 w에서 물건을 넣을 수 있는지 확인 (w가 weight[i]보다 크거나 같아야 함)
        // 왜 거꾸로 도냐? 중복 사용을 막기 위해 (0-1 knapsack은 한 물건을 한 번만 선택 가능)
        //dp[w]를 덮어쓸 때 이미 현재 i번 물건을 쓰기 전의 dp[w-weight[i]]값을 사용하려고 거꾸로 감.
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
            //dp[w]: 현재 무게 w까지 넣었을 때 최대 가치
            // 선택지 2가지 중 더 큰 값을 dp[w]에 저장
            // 안 넣는다 → dp[w] 유지 / 넣는다 → dp[w - weight[i]] + value[i] (이전 무게에서 현재 물건 더하기)
        }
    }

    cout << "최대 가치: " << dp[W] << endl;

    return 0;
}

그니까 다시 설명하면

weight = {10, 20, 30}

value = {60, 100, 120}

W = 50

첫 번째 물건 (i=0, 무게 10, 가치 60)

w=50 → 10까지 거꾸로 가면서 dp 갱신:

// 첫 번째 물건 (i=0, 무게 10, 가치 60)
// w=50 → 10까지 거꾸로 가면서 dp 갱신:
w=50 → dp[50] = max(dp[50], dp[40]+60)
w=49 → dp[49] = max(dp[49], dp[39]+60)
...
w=10 → dp[10] = max(dp[10], dp[0]+60) → dp[10]=60
// 결과적으로 무게 10짜리 물건은 dp[10]에 들어감

// 두 번째 물건 (i=1, 무게 20, 가치 100)
w=50 → dp[50] = max(dp[50], dp[30]+100)
...
w=20 → dp[20] = max(dp[20], dp[0]+100)
// 이런 식으로 계속 누적!

​

2차원 DP	1차원 DP
dp[i][w]	dp[w]
공간복잡도 O(N*W)	공간복잡도 O(W)
구현은 더 직관적	조금 더 신경써야함 (역순 for문)

🔧 왜 역순으로 w를 순회?

​

1차원 dp에서 정순으로 하면 같은 i에서 업데이트한 dp[w]를 다음 w에서 또 써버림.

역순으로 하면 이전 i에서의 dp[w-weight[i]]를 안전하게 참조 가능.

​

앞에서 이미 i번째 물건이 반영된 dp[w]값을 또 사용하면 중복 사용 위험이 있어서.

0-1 knapsack은 한 물건은 최대 1번만 넣어야 하니까!

​

이전 상태를 그대로 보존하기 위해 w를 역순으로 돈다.

"위에서부터 쌓아가는 느낌이 아니라, 뒤에서부터 덮어쓰면서 쌓아간다"

---

??? 그런데 이 방법도 W만큼 용량을 사용하는거니까

W가 커지면 용량이 커지고 안쓰는 공간이 많아져서

공간 사용이 비효율적인게 아닐까?!?!?!?

W가 커지면? → "메모리 최적화 기법"을 고민해야 함

W가 커지면 메모리 공간은 여전히 O(W)만큼 필요

예를 들어 W=10^6 이라면 → dp[W+1] → 약 1MB~4MB 까진 괜찮지만,

W가 10^7 넘어가면 → 수십 MB, 수백 MB → 때로는 메모리 초과

실제로 채워지는 값들은 전체 W 중 일부만 사용될 수도 있다.

​

이 문제를 "희소한 knapsack" 이라고 해

W는 크고

실제로 접근하는 weight들은 제한적일 때

→ 메모리가 낭비되는 경우

​

그래서 나오는 고급 테크닉들

① map 기반 knapsack (희소 DP)

#include <map>
map<int, int> dp;

key: weight

value: 가치

→ 메모리를 weight가 실제로 필요한 경우에만 사용

하지만 속도는 일반 dp보다 느릴 수 있음 (logN 탐색)

​

② meet in the middle

(N이 크고 W도 큰 경우)

아이템을 반으로 나눠서 → 각각 부분합 전부 구함 → 합쳐서 최적해 찾음

시간복잡도 O(2^(N/2)) → N이 40정도까지 가능

​

③ bitset DP (정수 knapsack에서)

#include <bitset>
bitset<MAX_W> dp;

메모리 사용 최소화 (비트 1개 = 1bit)

일부 문제에서는 속도가 매우 빨라짐

​

✅ 정리하면:

방법	메모리	속도
2차원 DP	O(N*W)	빠름
1차원 DP	O(W)	빠름
map DP	희소 O(사용 weight 수)	느림
meet in the middle	O(2^(N/2))	N작을 때
bitset DP	비트당 1bit	특수 상황

​