동적 프로그래밍(Dynamic Programming) 완전 정복: 개념, 점화식, 실전 예제까지

동적 프로그래밍(Dynamic Programming) 완전 정복: 개념, 점화식, 실전 예제까지

동적 프로그래밍(DP)은 알고리즘 중 가장 강력하지만 가장 어려워하는 주제 중 하나입니다.
하지만 제대로 이해하면, 복잡한 문제를 빠르고 우아하게 해결할 수 있는 강력한 도구입니다.

이번 글에서는 동적 프로그래밍의 정의, 핵심 원리, 점화식 세우는 법, 탑다운/바텀업 방식, 실전 예제까지 단계별로 확실하게 정리합니다.

---

✅ 동적 프로그래밍(DP)이란?

동적 프로그래밍은 복잡한 문제를 여러 개의 작은 문제로 나누고, 각 문제의 정답을 저장하여 중복 계산을 방지하는 알고리즘 기법입니다.

🔹 언제 사용하는가?

• 문제를 작은 하위 문제(subproblem)로 나눌 수 있을 때
• 중복되는 하위 문제가 존재할 때
• 최적 부분 구조(optimal substructure)를 만족할 때

---

🧠 DP의 3대 원칙

원칙 설명

1. Overlapping Subproblems	같은 문제를 반복해서 계산한다
2. Optimal Substructure	전체 문제의 최적 해는 부분 문제의 최적 해로 구성된다
3. Memoization or Tabulation	중복 계산을 저장하여 속도를 높인다

---

🔧 점화식이란?

점화식은 이전 결과를 이용해 현재 결과를 계산하는 수식입니다.
DP를 설계하기 위한 출발점입니다.

예시 – 피보나치 수열

• 점화식:
  F(n) = F(n-1) + F(n-2)
• 기본 조건(Base case):
  F(0) = 0, F(1) = 1

---

🧪 피보나치 수열 – DP 방식으로 구현

반응형

1. 탑다운(Top-Down, 재귀 + 메모이제이션)

memo = {}

def fib(n):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

2. 바텀업(Bottom-Up, 반복문 + 테이블)

def fib_bottom_up(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]

두 방식 모두 시간복잡도 O(n), 공간복잡도 O(n)
→ 공간 최적화: 변수 2개로 줄이기 가능 (O(1))

---

🔥 실전 예제: 1로 만들기 (백준 1463)

❓ 문제

정수 n이 주어졌을 때, 다음 세 연산 중 최소 횟수로 1을 만드는 방법은?

• 1. n % 3 == 0 → n / 3
• 1. n % 2 == 0 → n / 2
• 1. n - 1

✅ 점화식 세우기

dp[n] = min(
    dp[n // 3] + 1 if n % 3 == 0,
    dp[n // 2] + 1 if n % 2 == 0,
    dp[n - 1] + 1
)

✅ 바텀업 코드

def make_one(n):
    dp = [0] * (n + 1)
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + 1
        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i // 2] + 1)
        if i % 3 == 0:
            dp[i] = min(dp[i], dp[i // 3] + 1)
    return dp[n]

print(make_one(10))  # 출력: 3 (10 → 9 → 3 → 1)

---

💡 DP 유형별 접근 전략

유형 설명 예시

최솟값/최댓값	최소 연산 횟수, 최대 점수 등	1로 만들기, 정수 삼각형
카운팅	경우의 수 계산	계단 오르기, 동전 문제
여부 결정	특정 조건 만족 여부 판단	부분 합, 배낭 문제
최장 수열	가장 긴 증가하는 수열 등	LIS, LCS

---

🧠 DP와 재귀의 차이점

항목 재귀 DP (Top-Down / Bottom-Up)

중복 계산	O(2ⁿ) 발생 가능	O(n), 캐싱을 통해 중복 제거
공간 사용량	재귀 스택 필요	배열 또는 변수, 예측 가능
속도	느림	빠름

---

📌 결론 및 요약

• 동적 프로그래밍은 중복 계산을 줄이고 최적 해를 구하는 알고리즘 기법입니다.
• 핵심은 점화식 도출과 상태 저장입니다.
• Top-Down(재귀 + 메모) vs Bottom-Up(반복 + 테이블) 방식 모두 숙지해야 합니다.
• 실전에서는 대부분 Bottom-Up 방식이 더 빠르고 안전하게 동작합니다.

👉 다음 글에서는 탐욕(Greedy) 알고리즘과 DP의 차이, 선택 기준 및 실전 예제를 다루겠습니다.

---

📚 참고자료 및 출처

• 『Do it! 알고리즘 코딩 테스트 with Python』
• 백준 온라인 저지 (BOJ 1463)
• GeeksforGeeks – Dynamic Programming

---

 

동적프로그래밍, dynamic programming, 점화식, 메모이제이션, 바텀업, 탑다운, 1로 만들기, 파이썬 DP, 알고리즘 패턴, SEO 최적화 10개