알고리즘(Swift) - DP(다이나믹 프로그래밍) 알고리즘

동적 계획법(Dynamic Programming, DP)

• 최적 부분 구조(Optimal Substructure)와 중복되는 부분 문제(Overlapping Subproblem)를 가진 문제를 해결하기 위한 알고리즘 기법
• 최적 부분 구조: 문제의 최적 해가 하위 문제들의 최적 해로 구성될 수 있는 성질
• 중복 되는 부분 문제: 동일한 하위 문제가 여러 번 반복적으로 계산되는 성질

 

DP의 핵심 개념

1. 메모이제이션(Memoization) (Top-Down 방식)
   • 문제를 재귀적으로 푸는 과정에서, 이미 계산한 값을 저장하여 중복 계산을 방지
   • 각 결과를 캐싱하여 필요할 때 다시 사용
2. 타뷸레이션(Tabulation) (Bottom-Up 방식)
   • 하위 문제를 작은 문제부터 해결하고, 이를 이용해 상위 문제를 점진적으로 해결
   • 보통 배열을 이용하여 값을 저장

 

DP 문제를 푸는 과정

→ 문제의 재귀적인 구조를 찾아야 중복된 계산을 줄일 수 있음

1. 문제의 재귀적인 구조 파악
2. 수식으로 표현
3. 초기값 처리 (기저 조건)

 

DP 사용 예시

[문제]

동전 1원, 3원, 4원을 가지고 N원을 만들어야 한다.

최소한의 동전의 개수로 N원을 만드는 경우를 출력하는 프로그램을 적성하시오. 답이 여러 가지인 경우 아무 경우나 출력하시오.

(단, N은 1,000,000 이하의 자연수이고, 시간 제한은 1초이다.)

시간 제한이 1초이므로, 약 1억 번의 연산을 넘기면 안 됨.

1. 문제의 재귀적인 구조 파악

어떤 자연수 i를 1, 3, 4의 합을 통해 만들어야 하는 상황

1, 3, 4의 합을 통해 i가 만들어지기 직전 상황을 생각해보면

1을 더해서 i가 되는 숫자 (i-1)

3을 더해서 i가 되는 숫자 (i-3)

4을 더해서 i가 되는 숫자 (i-4)

등의 후보가 존재함

2. 수식으로 표현

f(i) : 1, 3, 4의 합으로 i를 만들 때 드는 동전의 최소 개수

재귀적인 구조를 수식으로 나타내면

f(i) = min(f(i - 1), f(i - 3), f(i - 4)) + 1

→ f(i - 1): i - 1를 만드는 최소 동전의 개수

→ f(i - 3): i - 3를 만드는 최소 동전의 개수

→ f(i - 4): i - 4를 만드는 최소 동전의 개수

3. 초기값 처리

f(i) = min(f(i - 1), f(i - 3), f(i - 4)) + 1 식에서 i - 1, i - 3, i - 4이 음수가 될 수 있으니

1 ≤ i ≤ 4인 경우 예외 처리를 해주어야 함

let N = 6
var f = Array(repeating: 0, count: N + 1) // DP 테이블 (메모이제이션 활용)

// 1 ≤ i ≤ 4인 경우 예외 처리
f[1] = 1
f[2] = 2
f[3] = 1
f[4] = 1

// 5 ≤ i ≤ N인 경우 (반복문 이용)
for i in 5...N {
	f[i] = min(f[i - 1], f[i - 3], f[i - 4]) + 1
}
print(f[N])

 

DP의 대표적인 문제

1. 피보나치 수열

• 문제: n번째 피보나치 수를 구하라
• 점화식: F(n) = F(n - 1) + F(n-2)
• 기저 조건: F(0) = 0, F(1) = 1

// Top-Down 방식
func fibonacci(_ n: Int, _ memo: inout [Int]) -> Int {
    if n <= 1 { return n } // 기저 조건
    if memo[n] != -1 { return memo[n] } // 중복 방지
    memo[n] = fibonacci(n-1, &memo) + fibonacci(n-2, &memo)
    return memo[n]
}

var memo = Array(repeating: -1, count: 100)
print(fibonacci(10, &memo)) // Output: 55

// Bottom-Up 방식
func fibonacci(_ n: Int) -> Int {
    var dp = Array(repeating: 0, count: n + 1)
    dp[1] = 1
    for i in 2...n {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

print(fibonacci(10)) // Output: 55

 

2. 최장 공통 수열(LCS, Longest Common Subsqeunce)

• 문제: 두 문자열의 가장 긴 공통 부분 수열을 구하라
• 점화식:dp[i][j] = max(dp[i − 1][j], dp[i][j − 1]) (문자가 다를 경우)
• dp[i][j] = dp[i − 1][j − 1] + 1 (문자가 같을 경우)

 

3. 0/1 배낭 문제(Knapsack Problem)

• 문제: 무게 제한이 있는 배낭에 물건들을 담아 최대 가치를 구하라
• 점화식: dp[i][w] = dp[i − 1][w] (i번째 물건을 담지 않을 경우)
• dp[i][w] = max(dp[i − 1][w], dp[i − 1][w − weight[i]] + value[i]) (i번째 물건을 담을 경우)

 

DP의 장점

1. 중복 계산 방지로 속도 향상.
2. 직관적이고 체계적인 문제 해결 가능.
3. 최적 해를 보장.

DP의 단점

1. 초기 메모리 사용량이 많을 수 있음.
2. 점화식 도출이 어렵거나 문제 구조가 적합하지 않으면 적용 불가능.