[Swift] Dynamic Programming (동적 계획법)

DP(Dynamic Programming; 동적 계획법)

큰 문제를 작은 문제로 쪼개어 푸는 알고리즘 기법으로 이미 계산한 작은 문제의 정답을 저장(메모이제이션) 해 두고, 필요할 떄 재사용하여 중복 계산을 방지해서 효율적이다. 대표적으로 경로탐색, 최적화(최대/최소/방법 수), 조합 문제 등에서 사용할 수 있다.

대표적인 예로 피보나치 수열을 풀어볼려고 한다. 우선 기존에는 대표적인 재귀함수 문제로 재귀함수로 코드를 구현했다.

func fibRecursive(_ n: Int) -> Int {
    if n <= 1 { return n }
    return fibRecursive(n - 1) + fibRecursive(n - 2)
}

print(fibRecursive(10)) // 55

 

이것도 문제를 풀 수 있지만 n이 커지면 연산량이 많아지고, 현재 같은 계산을 계속 반복하고 있어 시간이 오래 걸린다.

연산을 했던 것을 저장하여 저장된 것이 있다면 꺼내서 사용하는 DP 알고리즘으로 구현해보았다.

import Foundation

func fib(_ n: Int, memo: inout [Int: Int]) -> Int {
    if let value = memo[n] {
        return value
    }
    
    let nthFibo = fib(n - 1, memo: &memo) + fib(n - 2, memo: &memo)
    memo[n] = nthFibo
    return nthFibo
}

var memo: [Int: Int] = [
    1: 1,
    2: 2
]

let result = fib(50, memo: &memo)
print(result) // 20365011074

 

memo라는 Dictionary에 연산 값을 저장하여 만약 memo 안에 값이 있다면 꺼내 사용하여 구현하였다.