동적계획법(DP, Dynamic Programming)

1. 왜 만들어 졌을까?

어원(When)

• Dynamic: 시간에 따라 변하는 걸 의미하는 것이 아님!
• Programming: 코드 작성이 아니라, 계획(Plan)을 짠다는 의미

즉, 유동적으로 결정하는 계획 정도의 뜻

누가 만들었나?

• Richard Bellman(리처드 벨만), 1950년대
• 미 국방성 프로젝트 중 최적화 문제를 해결하기 위해 개발
•  
•  

왜? ‘Dynamic Programming’이라 이름 붙였나?벨만의 유명한 일화에 따르면:

내가 일하던 국방 프로젝트는 ‘수학’이나 ‘과학’이라는 단어에 거부감을 가진 관리들이 있었지
그래서 그들이 이해 못할 단어를 골라야 했어. 그래서 ‘다이내믹 프로그래밍’이라고 불렀지
즉, 본래 의미보다 정치적 이유(!)로 지어진 네이밍…

어떤 알고리즘이야?

큰 문제를 작은 문제를 나눠서 푼 뒤, 그 결과를 재사용하여 전체 문제를 효율적으로 해결하는 기법
즉, 중복되는 연산을 저장하여 시간 복잡도를 줄이는 방법

 

---

DP가 필요한 상황

• 문제를 작은 하위 문제로 분할 가능한지
• 하위 문제의 결과가 여러번 반복적으로 사용되는지

키워드

• 피보나치 수열
• 최장 공통 부분 수열(LCS)
• 배낭 문제
• 계단 오르기, 동전 교환 등

피보나치 예시

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

해결 고민: 어떻게 중복 계산을 줄일까?

→ 탑다운
→ 바텀업
→ 누적계산

해결 방법 선택

1. Top-down (재귀 + 메모이제이션)

int[] memo = new int[100];

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

2. Bottom-up

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

시간 복잡도를 고려하지 않고 잘못된 방식 사용

예시: 하향식 재귀만 쓰고 캐싱을 안한 경우

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

• 재귀로 간결해 보이나
• fib(5)를 호출하면 fib(3), fib(2) 등이 여러 번 계산됨
• 결과: 시간복잡도는 O(2^n) → 매우 비효율적

올바른 DP 사고방식 흐름

1. 문제를 하위 문제로 쪼갤 수 있는가?(예: n = n -1 + n-2)
2. 하위 문제의 결과가 중복되어 사용되는가?(예: fib(3)이 여러 번 등장)
3. 결과를 캐싱하거나 반복문으로 누적할 수 있는가?
4. 시간 복잡도가 실제로 줄어드는지 확인(예: O(n)인지 확인)