[DP] 파이썬으로 Dynamic Programming 정복하기

코테 문제를 풀다 보면, 자주 나오는 개념인 Dynamic Programming에 대해 정리하고자 한다.

DP는 큰 문제를 작은 문제로 나눠서 푸는 방식으로, 단순히 쪼개는 것 뿐 아니라 이미 계산한 결과를 저장해서 다시 계산하는 수고를 덜어주는 방법이다.

 

즉, 반복되는 계산을 줄이기 위해, 중간 결과를 저장(memoization 또는 tabulation) 해두고 재활용하는 방식이다.

 

🌱 DP는 언제 사용할까?

아래 두 조건을 만족할 때 쓸 수 있다.

1. 겹치는 부분 문제 : 같은 문제를 여러 번 다시 계산해야 하는 상황

2. 최적 부분 구조 : 큰 문제의 최적해가 작은 문제들의 최적해로 이루어져 있는 구조

가장 대표적인 예는 피보나치 수열을 구하는 문제이다.

 

🌱 DP 사용 방식은?

DP는 크게 두 가지 방식으로 사용법을 나눌 수 있다.

1. Top-down 방식 (재귀 + Memoization)

• 이름 그대로 위에서부터 내려오면서 계산하고, 중간 결과를 저장한다.
• 주로 재귀함수를 사용해서 구현할 수 있다.
• 대표적인 예가 피보나치 수열!

2. Bottom-up 방식 (반복문 + Tabulation)

• 이름대로 아래에서부터 차곡차곡 계산해서 최종 결과를 도출하는 방식이다.
• 주로 반복문으로 구현한다.

 

🌱 DP가 사용되는 문제 예시들

 

• 최대/최소값을 구하는 문제
• 특정 조건을 만족하는 개수를 구하는 문제
• 경로의 수, 방법의 수를 구하는 문제
• 배낭 문제(0/1 Knapsack), 동전 교환 문제 등
• 정수 분할 문제

 

🌱 정수 분할(Partition Problem) 문제 풀이 - 순서고려X

그 중, 문제를 풀며 가장 많이 주저했던 유형을 정리하고자 한다. 정수 분할문제는 다음과 같은 경우이다.

양의 정수들의 조합 중에서, 그 합이 정수 n이 되는 경우의 수 구하기

 

예를 들어, n = 4일 때, 가능한 조합(순서를 무시)은:

• 1 + 1 + 1 + 1
• 1 + 1 + 2
• 2 + 2
• 1 + 3
• 4

→ 총 5가지

 

이러한 경우의 수를 구하는 DP를 구현해보자.

def count_combinations(n):
    dp = [0] * (n + 1)
    dp[0] = 1  # 합이 0이 되는 방법은 '아무것도 선택하지 않는 1가지'뿐

    # 1부터 n까지의 숫자를 사용해서 조합을 만듦
    for num in range(1, n + 1):
        for i in range(num, n + 1):
            dp[i] += dp[i - num]

    return dp[n]

 

 

• dp[i]는 "합이 i가 되는 조합의 수"를 저장한다.
• 처음엔 dp[0] = 1 → 아무것도 안 써서 0을 만드는 경우 한 가지.
• 그 다음, 숫자 1부터 n까지 차례대로 사용하면서, 각 숫자를 사용해서 만들 수 있는 합들을 업데이트 한다.
• 이때는 중복 조합은 허용하지만 순서는 무시.

 

🌱 정수 분할(Partition Problem) 문제 풀이 - 순서고려O

순서를 고려하는 방법은 Permutation(순열) 문제이다.

def count_permutations(n):
    dp = [0] * (n + 1)
    dp[0] = 1  # base case

    for i in range(1, n + 1):
        for num in range(1, n + 1):
            if i - num >= 0:
                dp[i] += dp[i - num]

    return dp[n]