알고리즘 기초 - 동적 프로그래밍(Dynamic Programming, DP)

---

DP란?

---

 

DP(Dynamic Programming)는 복잡한 문제를 작은 부분 문제로 나누어 풀고, 그 결과를 저장해 두었다가 재사용하는 알고리즘 기법이다.

 

핵심 아이디어는 "중복되는 부분 문제를 저장해서 다시 계산하지 않는다" 입니다.

---

DP의 조건

---

DP를 적용하려면 두 가지 조건이 성립해야 합니다

 

1. 최적 부분 구조 (Optimal Substructure)
   
   • 큰 문제의 정답을 작은 문제의 정답으로부터 구할 수 있어야 함
   • 즉, 부분 문제들을 조합하면 전체 문제의 답이 됨
2. 중복되는 부분 문제 (Overlapping Subproblems)
   
   • 같은 부분 문제가 여러 번 반복해서 나타나야 함
   • 한 번 계산한 값을 저장해 두고 다시 쓸 수 있어야 효율적

 

---

접근 & 구현 방식

---

 

(1) Top-Down (메모이제이션, 재귀 기반)

 

• 큰 문제를 먼저 풀려고 시도
• 계산 중에 작은 문제가 필요하면 재귀로 내려감
• 이미 구한 값은 memo(캐시)에 저장하고, 필요할 때 불러옴

장점: 코드가 직관적 (재귀 구조 그대로 작성 가능)
단점: 재귀 깊이가 깊으면 스택 오버플로우 위험

 

예시(피보나치)

memo = [0]*100

def pibo(num):
    if num == 1 or num == 2: # 1과2일 때 1을 메모에 저장
        memo[num] = 1
        return memo[num]
    
    if memo[num] != 0:  #메모에 이미 계산 값이 있으면 리턴
        return memo[num]

    memo[num] = pibo(num - 1) + pibo(num - 2) #재귀를 통해 새로운 값 계산
    return memo[num]
print(pibo(10))

 

 

 

(2) Bottom-Up (탭ulation, 반복문 기반)

• 작은 문제부터 차례대로 답을 구하고, 그 결과를 배열에 저장
• 큰 문제를 풀 때는 이미 계산된 작은 문제 값을 그대로 이용

장점: 재귀가 없어서 안정적이고 빠름
단점: 문제 구조를 잘 분석해서 점화식을 세워야 함

 

예시(피보나치)

def pibo(n):
    # n이 0이나 1일 경우 바로 반환
    if n == 0:
        return 0
    elif n == 1:
        return 1
    
    # DP 테이블(배열) 준비
    dp = [0] * (n + 1)   # 인덱스를 n까지 쓰기 위해 n+1 크기로 생성
    dp[0] = 0
    dp[1] = 1

    # 작은 문제부터 큰 문제까지 차례대로 계산
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]

    # 최종적으로 원하는 값 반환
    return dp[n]

# 예시 실행
print(pibo(10))  # 55

 

 

 

---

마무리

---

핵심 포인트 요약

 

• DP는 큰 문제를 작은 문제로 나누고, 중복 계산을 피하기 위해 결과를 저장하는 알고리즘
• 적용하려면 최적 부분 구조 + 중복되는 부분 문제 조건이 필요함
• 구현은 Top-Down(메모이제이션) 또는 Bottom-Up(탭ulation) 두 가지 방식이 있음

 

결국 DP는 '계산한 것을 또 하지 않는다'는 단순한 아이디어에서 출발합니다.
처음엔 점화식을 세우는 게 낯설지만, 많이 풀다 보면 "아, 이 문제도 DP네!" 하고 구조가 보이게 돼요.
그래서 DP는 문제 유형을 많이 접하고 점화식을 세우는 훈련을 하는 것이 가장 중요합니다.