동적 계획법 (Dynamic Programming: DP) 이란?

1️⃣ 동적 계획법(DP)이란?

정의:

동적 계획법(Dynamic Programming, DP)은 큰 문제를 여러 개의 작은 부분 문제로 나누어 그 해를 저장하면서 해결하는 방법입니다. 이를 통해 반복적인 계산을 줄이고, 문제를 효율적으로 해결할 수 있습니다.

핵심 아이디어:

부분 문제의 결과를 저장해서 같은 계산을 반복하지 않는 것이 핵심입니다.
DP는 최적화 문제에 주로 사용되며, 주어진 문제를 최적 부분 구조와 중복되는 부분 문제로 나눌 수 있을 때 사용됩니다.

2️⃣ DP가 필요한 이유는?

일반적인 재귀 방식은 같은 부분 문제를 반복해서 계산하기 때문에 비효율적일 수 있어요. 동적 계획법은 이러한 중복 계산을 제거함으로써 시간 복잡도를 크게 줄일 수 있습니다.

❌ 재귀만 사용하는 경우:

피보나치 수열과 같은 문제에서, 같은 값을 여러 번 계산하게 되어 시간이 매우 많이 소요됩니다.

✅ DP를 사용하는 경우:

한 번 계산한 값은 저장해서 이후에 다시 계산할 필요가 없도록 하여 불필요한 계산을 방지합니다.

3️⃣ DP의 핵심 개념

🟡 1. 최적 부분 구조 (Optimal Substructure)

큰 문제의 최적 해답이 작은 문제들의 최적 해답으로 구성될 수 있어야 합니다.
예를 들어, 최단 경로를 구할 때
A에서 B로 가는 최단 경로는
A에서 중간 경로까지의 최단 경로와
중간에서 B로 가는 최단 경로로
나눌 수 있습니다.

🟢 2. 중복되는 부분 문제 (Overlapping Subproblems)

여러 부분 문제를 해결할 때 같은 문제를 여러 번 반복하여 해결해야 하는 경우가 발생합니다.
예를 들어, 피보나치 수열에서 F(5)를 계산하기 위해 F(4)와 F(3)을 계산하게 되고,
F(4)를 계산할 때 다시 F(3)을 계산하게 됩니다.
DP는 이런 중복을 피할 수 있게 합니다.

4️⃣ DP의 구현 방식

DP를 구현하는 두 가지 방식:

1) 메모이제이션(Memoization, 탑다운 방식) 📝

"큰 문제를 해결하는 과정에서 작은 문제의 결과를 저장하고 재사용하는 방식"

✔ 탑다운(Top-Down) 방식으로, 재귀 호출을 사용하여 해결합니다.
✔ 이미 계산한 값은 배열(메모리)에 저장하고, 동일한 문제가 다시 나타나면 저장된 값을 재사용합니다.

📌 탑다운 방식의 동작 과정

a. 큰 문제를 먼저 해결하려고 시도
b. 해결 과정에서 더 작은 부분 문제를 재귀적으로 호출
c. 이미 해결한 문제라면 저장된 값을 반환하여 중복 계산을 방지
d. 처음 등장하는 문제라면 직접 계산하고, 그 결과를 저장 후 반환

예제 코드: 피보나치 수열 (메모이제이션 적용)

def fibonacci(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:  # 값이 저장되지 않았다면 계산
        memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]  # 저장된 값 반환

print(fibonacci(10))  # 55

memo 딕셔너리를 활용하여 중복 계산을 방지
재귀 호출을 통해 문제를 분할하여 해결

2) 타뷸레이션(Tabulation, 바텀업 방식)

"작은 문제부터 해결하면서 점진적으로 큰 문제를 해결하는 방식"

✔ 바텀업(Bottom-Up) 방식으로, 반복문을 사용하여 순차적으로 해결합니다.
✔ 배열에 값을 미리 저장하면서 작은 문제부터 차례로 큰 문제를 해결합니다.

📌 바텀업 방식의 동작 과정

a. 가장 작은 부분 문제부터 시작
b. 해결된 작은 문제의 결과를 활용하여 점점 더 큰 문제를 해결
c. 반복문을 통해 모든 문제를 해결한 후, 최종 값을 반환

예제 코드: 피보나치 수열 (타뷸레이션 적용)

def fibonacci(n):
    dp = [0] * (n + 1)  # 결과 저장 배열
    dp[1] = 1  # 초기값 설정

    for i in range(2, n + 1):  # 작은 문제부터 해결
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

print(fibonacci(10))  # 55

배열 dp를 활용하여 값을 저장하면서 점진적으로 해결
반복문을 사용하여 재귀 호출 없이 문제를 해결

메모이제이션 vs. 타뷸레이션 비교

	메모이제이션(탑다운)	타뷸레이션(바텀업)
접근 방식	큰 문제를 먼저 해결, 작은 문제를 재귀적으로 호출	작은 문제부터 해결하여 큰 문제를 점진적으로 해결
사용 방식	재귀 함수 + 저장	반복문 + 배열
메모리 사용량	함수 호출 스택 + 저장 배열	저장 배열만 사용
속도	재귀 호출로 인해 함수 호출 오버헤드 발생 가능	반복문으로 처리하여 속도가 빠름
적합한 경우	특정 경우에만 필요한 부분 문제를 해결할 때	모든 부분 문제를 한 번에 계산할 때

✔ 재귀 호출이 많아지는 경우, 스택 오버플로우 위험이 있으므로 바텀업 방식이 유리
✔ 반면, 불필요한 부분 문제를 계산하지 않고 넘어갈 수 있는 경우에는 메모이제이션이 유리

결론: 언제 어떤 방식을 선택해야 할까?

✅ 메모이제이션 (탑다운) 방식이 적합한 경우

부분 문제 중 불필요한 계산을 줄일 필요가 있는 경우
특정 부분 문제만 필요할 때
재귀 호출이 가능한 경우

✅ 타뷸레이션 (바텀업) 방식이 적합한 경우

모든 부분 문제를 한 번씩 계산해야 하는 경우
재귀 호출이 너무 깊어지는 경우 (스택 오버플로우 방지)
반복문을 활용하는 것이 더 직관적이고 효율적인 경우

=> 한 줄 요약:

"부분 문제를 선택적으로 계산해야 한다면 → 메모이제이션(탑다운)"
"모든 부분 문제를 계산해야 한다면 → 타뷸레이션(바텀업)"

5️⃣ DP를 적용할 수 있는 문제들

동적 계획법은 다양한 최적화 문제에서 자주 사용되며, 대표적인 문제 유형은 다음과 같습니다:

1. 피보나치 수열 문제

피보나치 수열을 구하는 문제는 동일한 부분 문제를 여러 번 반복해서 계산해야 하므로, DP로 해결할 수 있습니다.

2. 최단 경로 문제

다익스트라 알고리즘이나 플로이드-와샬 알고리즘에서 DP를 사용해 최단 경로를 구할 수 있습니다.

3. 배낭 문제 (Knapsack Problem)

물건을 배낭에 담아 최대 가치를 얻는 문제에서, DP는 부분 문제를 저장하고 재사용해 최적 해답을 구할 수 있습니다.

4. 최소 동전 거스름돈 문제

주어진 동전 종류로 특정 금액을 맞추는 문제에서, DP를 사용해 최소 동전 개수를 찾을 수 있습니다.

5. 최장 공통 부분 수열 (Longest Common Subsequence, LCS)

두 문자열에서 공통된 부분 문자열을 찾는 문제에서도 DP를 사용해 효율적으로 해답을 구할 수 있습니다.

💡 DP를 잘 사용하기 위한 팁

문제 분해: 문제를 작은 부분 문제로 나누고, 그 해답을 저장하는 구조로 바꿔 보세요.
메모이제이션 활용: 중복되는 부분 문제를 찾아 한 번 계산한 값을 재사용하면 성능이 크게 향상됩니다.
작은 문제부터 해결( 타뷸레이션 ): 큰 문제를 해결하기 위해 작은 문제부터 해결하는 방법(바텀업 방식)이 더 효율적일 때도 있습니다.

🎯 DP를 사용하는 기준

동적 계획법을 적용할 수 있는 문제인지 확인하는 기준은 두 가지입니다:

최적 부분 구조: 큰 문제를 작은 문제로 나누어 해결할 수 있나요?
중복되는 부분 문제: 작은 문제를 여러 번 반복해서 계산하게 되나요?

✅ DP를 적용하려면 반드시 "최적 부분 구조"와 "중복되는 부분 문제"가 모두 성립해야 합니다!

📌 정리

개념	설명
동적 계획법 (DP)	큰 문제를 작은 부분 문제로 나누어 해결하고, 중복된 계산을 피하기 위해 그 결과를 저장해 최적의 해를 찾는 방법
최적 부분 구조	큰 문제의 해답이 작은 문제의 해답으로 구성될 수 있는 구조
중복되는 부분 문제	같은 문제를 반복해서 계산해야 하는 상황
메모이제이션	계산한 결과를 저장해, 같은 계산을 반복하지 않도록 하는 방식 (탑다운 방식)
타뷸레이션	작은 문제부터 차례대로 해결하는 방식 (바텀업 방식)

simple_dev_null