동적 계획법 - 1. 개념과 기초 이해

 

1. 개념과 기초 이해

1-1. 동적 계획법이란?

📌 정의

동적 계획법(Dynamic Programming, DP)이란 큰 문제를 작은 문제로 나누고, 이미 해결한 작은 문제의 결과를 저장하여 중복 계산을 피하는 최적화 기법입니다.
이를 통해 연산 속도를 개선하고 효율적인 알고리즘을 설계할 수 있습니다.

---

📌 DP를 사용하는 이유

• 완전 탐색(Brute Force) 방식으로 문제를 해결하면 시간 복잡도가 기하급수적으로 증가하여 비효율적입니다.
• DP는 중복 계산을 제거하여 문제를 빠르게 해결하는 방법을 제공합니다.

---

📌 완전 탐색 vs 분할 정복 vs 동적 계획법

알고리즘 유형	개념	장점	단점
완전 탐색 (Brute Force)	가능한 모든 경우를 직접 계산	구현이 쉬움	비효율적 (시간 복잡도가 기하급수적으로 증가)
분할 정복 (Divide & Conquer)	문제를 작은 문제로 나누고, 해결 후 합쳐서 해결	구조적으로 단순하고 직관적	하위 문제들이 독립적이므로 중복 계산 방지가 어려움
동적 계획법 (DP)	작은 문제를 푼 결과를 저장하여, 동일한 계산을 반복하지 않음	최적화된 성능 제공, 시간 복잡도를 크게 줄임	DP를 적용할 수 있는 문제인지 확인해야 함

---

1-2. DP를 적용할 수 있는 문제의 특징

DP를 적용하기 위해서는 두 가지 주요 조건이 필요합니다.

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

• 작은 문제들의 최적해(Optimal Solution)를 활용하여 전체 문제의 최적해를 구할 수 있는 구조
• 즉, 각 하위 문제의 최적해를 모아 전체 문제의 최적해를 만들 수 있음

🔹 예시: 피보나치 수열
       F(n) = F(n − 1) + F(n − 2), where n ≥ 2

• F(n-1)과 F(n-2)가 최적해라면, 이를 조합하여 F(n)의 최적해를 구할 수 있음 → 최적 부분 구조 성립

---

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

• 동일한 작은 문제가 반복적으로 계산되는 경우
• DP는 이전에 계산한 값을 저장하여 불필요한 연산을 줄임

🔹 예시: 피보나치 수열

F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)
...

위처럼 F(3), F(2) 같은 값들이 여러 번 계산됨.
DP를 사용하면 한 번만 계산하고 저장하여 불필요한 중복 연산을 제거할 수 있음.

---

1-3. 메모이제이션 vs 탑다운/바텀업

DP를 구현하는 방식에는 탑다운(Top-Down) 방식과 바텀업(Bottom-Up) 방식이 있습니다.

---

📌 메모이제이션 (Memoization, Top-Down)

• 재귀(Recursion)를 활용하여 필요한 부분만 계산한 후 저장
• 이미 계산한 값이 있다면 재사용하여 불필요한 재귀 호출을 방지
• dict 또는 배열을 사용하여 값을 저장

🔹 피보나치 수열 (Top-Down, Memoization)

def fib_memo(n, memo=None):
    if n < 0:
        raise ValueError("n must be non-negative")  # ✅ 입력값 검증 추가
    if memo is None:
        memo = {}  # ✅ 새로운 딕셔너리 생성 (기본 인자로 사용 방지)
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

print(fib_memo(5))  # 출력: 5
print(fib_memo(7))  # 출력: 13

---

📌 바텀업 (Bottom-Up) 방식

• 반복문을 활용하여 모든 부분 문제를 순차적으로 계산
• 재귀를 사용하지 않음, 대신 배열을 사용하여 값을 저장
• 작은 문제의 결과를 바탕으로 큰 문제를 해결

🔹 피보나치 수열 (Bottom-Up)

def fib_bottom_up(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n <= 1:
        return 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(fib_bottom_up(5))  # 출력: 5
print(fib_bottom_up(7))  # 출력: 13

---

📌 바텀업 최적화 (Bottom-Up Optimized)

• 기존 바텀업 방식에서는 O(n) 크기의 배열을 사용하여 중간 값을 저장
• 공간 최적화(O(1)) 기법을 사용하면 배열 없이 두 개의 변수만 이용하여 해결 가능

🔹 피보나치 수열 (O(1) 공간 최적화)

def fib_optimized(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b

print(fib_optimized(5))  # 출력: 5
print(fib_optimized(7))  # 출력: 13

---

📌 최종 시간 복잡도 비교

방법	구현 방식	시간 복잡도	공간 복잡도	사용 사례
완전 탐색	재귀 호출	$O(2^n)$	$O(n)$	간단한 문제
메모이제이션 (Top-Down)	재귀 + 저장	$O(n)$	$O(n)$	필요한 부분만 계산
바텀업 (Bottom-Up)	반복문 + 저장	$O(n)$	$O(n)$	모든 부분을 순차적으로 계산
바텀업 최적화	반복문 + 변수 2개만 사용	$O(n)$	$O(1)$	메모리 제약이 있는 경우