[알고리즘] 동적 프로그래밍 (Dynamic Programming)

100·2025년 4월 3일

자료구조 & 알고리즘

목록 보기

18/20

🧠 동적 프로그래밍(DP) 개념 완전 정리 - Top-down / Bottom-up / 문제 접근 흐름

✅ DP란 무엇인가?

DP(Dynamic Programming)는
복잡한 문제를 더 작은 하위 문제로 나눠 해결하고,
중복되는 계산을 줄여서 효율적으로 푸는 알고리즘 기법이다.

완전 탐색으로 풀면 시간 초과가 나는 문제도
DP로 바꾸면 훨씬 빠르게 해결할 수 있다.

✅ DP가 가능한 문제의 조건

DP는 아무 문제에나 쓸 수 없다.
다음 두 조건이 모두 만족될 때만 가능하다.

1️⃣ 중복되는 부분 문제 (Overlapping Subproblems)

같은 하위 문제가 여러 번 반복되는 구조
예: 피보나치 수열 f(n) = f(n-1) + f(n-2)는 f(3)이 여러 번 계산됨

2️⃣ 최적 부분 구조 (Optimal Substructure)

문제의 정답이 하위 문제들의 정답을 조합해서 만들어질 수 있는 구조여야 한다
예: 최소 동전 개수 = min(각 동전으로 나눈 나머지 금액의 최소값 + 1)

이 두 가지 조건을 갖추지 않으면 DP가 아니라 DFS, 그리디, 백트래킹 등의 접근이 필요하다.

✅ Top-down 방식 (하향식 접근)

Top-down은 큰 문제에서 출발하여 작은 하위 문제로 내려가면서 계산하는 방식이다.
주로 재귀 함수를 사용하며, 중복 계산을 방지하기 위해
메모이제이션(Memoization) 기법을 함께 사용한다.

🔹 메모이제이션이란?

이미 계산한 결과를 저장해두고, 같은 입력이 다시 들어왔을 때 계산하지 않고 바로 반환하는 방식이다.

이를 통해 같은 하위 문제를 여러 번 재계산하지 않아도 되므로
속도와 효율이 크게 향상된다.

🔹 예제: 피보나치 수 (Top-down)

memo = {}
def fib_top_down(n):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib_top_down(n - 1) + fib_top_down(n - 2)
    return memo[n]

✔️ Top-down은 직관적이고 구현이 쉬우며,
✔️ DFS와 섞어서 경로 탐색, 조건 분기 등에 유연하게 쓸 수 있다.

❌ 단점은 재귀 깊이가 깊을 경우 스택 오버플로우 위험이 있고,
❌ 반복문보다 느릴 수 있다는 점이다.

✅ Bottom-up 방식 (상향식 접근)

Bottom-up은 가장 작은 문제부터 차례대로 해결해가며 테이블을 채워나가는 방식이다.
반복문과 배열(DP 테이블)을 사용하며,
재귀 없이 명확하고 빠른 구조로 동작한다.

🔹 예제: 피보나치 수 (Bottom-up)

def fib_bottom_up(n):
    if n == 0:
        return 0
    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]

✔️ Bottom-up은 보통 더 빠르고,
✔️ 메모리 사용이 안정적이며 스택 오버플로우 걱정도 없다.

❌ 대신 문제의 점화식을 명확히 이해하고,
❌ 테이블 구조를 설계해야 하므로 더 많은 설계력이 필요하다.

✅ Top-down vs Bottom-up 비교

항목	Top-down (재귀 + 메모이제이션)	Bottom-up (반복문 + 테이블)
구현 방식	재귀 함수	반복문
중복 계산 제거	메모이제이션	DP 테이블
속도	보통 느림	일반적으로 빠름
메모리	호출 스택 사용	배열만 사용
직관성	높음 (코드 간결)	낮을 수 있음
DFS 연계	매우 자연스러움	어려움
스택 오버플로우	가능성 있음	없음

✅ 어떤 방식으로 풀어야 할까?

상황	추천 방식	이유
탐색 중 경로 조건 분기, DFS 연동	Top-down	유연하고 코드 직관적
반복적 누적 구조, 점화식 명확	Bottom-up	속도와 안정성 우수
N이 크고 제한 시간이 빡빡	Bottom-up	더 빠름
먼저 구현 흐름을 잡고 싶음	Top-down	빠른 테스트 가능
메모이제이션으로도 시간 초과	Bottom-up	구조적으로 최적화 가능