[Swift] 동적 계획법 (Dynamic Programming) 이해하기

이 게시글은 개인적인 공부를 위해 작성된 게시물입니다.

이 글의 모든 출처는 https://babbab2.tistory.com/100 입니다.

---

동적 계획법

상향식 접근법으로 가장 작은 부분의 해답을 구한 후,
이를 저장하여 저장한 값을 이용해 상위 문제를 풀어가는 방법

동적 계획의 핵심은 Memoization(메모이제이션)이라는 기법인데

설명은 아래와 같습니다.

메모이제이션

동일한 계산을 반복해야할 때, 이전에 계산한 값을 메모리에 저장한 후
반복수행을 제거하여 프로그램 실행속도를 빠르게 하는 기법

 

피보나치 수열로 이해하기

0, 1, 2, 3, 5, 8, 13 ...

이런식으로 가장 처음 0, 1을 제외하고 내 앞의 두 놈을 더해서 나를 만드는 것이 피보나치 수열입니다.

피보나치 수열 점화식

재귀함수를 이용한 구현

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

만약 위 함수로 fibo(4)를 호출한다면

fibo(0)을 구하는 함수를 2번 중복 실행하고,

fibo(1)을 구하는 함수를 3번 중복 실행하고,

fibo(2)를 구하는 함수를 2번 중복실행해야합니다.

하나의 결과 값을 도출하는데 중복되는 값을 얻기위해 실행되는 함수가 너무 많습니다.

이런 방법은 숫자가 커질수록 프로그램의 실행속도를 떨어뜨립니다.

 

동적 계획법을 이용한 구현

동적 계획법에서는 메모이제이션을 사용합니다.

가장 작은 단위부터 계산하고 저장하여, 큰 단위 값을 도출합니다.

동적 계획법에서는 작은 단위를 저장할 저장 공간이 필요합니다.

func fibo(_ n: Int) -> Int{
    var cache: [Int] = [0, 1]
    
    for num in 2...n {
        cache.append(cache[num - 1] + cache[num - 2])
    }
    return cache[n]
}

이렇게 cache라는 저장 공간을 활용해서, 가장 작은 단위 0, 1부터 도출되는 값을 계속 저장해나갑니다.

만약 4번째 수를 구하기 위해 아래와 같이 실행하면

fibo(4)

4보다 작은 값들인 0, 1, 2, 3번째 값까지를 먼저 구하여 저장하고,

이 값들이 저장되어 있는 메모리를 이용하여,

2번째 index + 3번째 index의 값을 더해 구하는 것입니다.

이미 저장되어 있는 값을 활용하는 것이기 때문에, 중복 실행 할 필요가 없습니다.

이런 과정들로 인해 실행속도를 빨라집니다.