[Algorithm] 동적 프로그래밍 (DP, Dynamic Programming)

Dynamic Programming

동적 프로그래밍, 다이나믹 프로그래밍, 동적 계회법으로 불리는 Dynamic Programming은 큰 문제를 작은 문제로 나누고 작은 문제의 답들을 이용해 원래 문제의 답을 찾는 방법이다. 주어진 문제를 최대한 많이 이용할 수 있는 작은 문제들로 나누는 게 핵심이라고 생각한다. (그래야 재사용이 많이 가능하고, 메모리를 적게 쓴다)

출처: 나무위키

Dynamic Programming 의 예시

피보나치수열

가장 쉬운 예로는 피보나치 수열이 있다. 피보나치수열은 아래와 같이 표현할 수 있다.

f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2) when n > 1

 

만약 값을 재사용하지 않는다면...? 아래와 같이 5번째 값을 구하기 위해서는 15번의 연산이 필요하다.

 

아래와 같이 점화식을 통해 간단하게 n번째 피보나치수열을 구하는 함수를 만들 수 있다. 하지만 이 함수는 매우 비효율적이다. 매번 계산을 해줘야 하기 때문이다.

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

 

아래와 같이 count를 넣어보면 15번 계산이 된다는 것을 볼 수 있다.

import Foundation

var count = 0

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

print(fib(5)) // 8
print("count: \(count)") // count: 15

 

동적 프로그래밍으로 피보나치 수열 계산

Top-Down, Bottom-Up 방식이 존재한다. 둘 다 재사용할 결괏값을 저장할 메모리를 만드는 것은 동일하지만 Top-Down은 위에서부터 접근해서 결과값이 없다면 계산해주는 방식이고, Bottom-Up은 초기값으로부터 결과값을 모두 계산해 준 뒤 결과를 찾는 방식이다. 아래에 코드를 보면 좀 더 이해가 잘 될 것이다.

 

Top-Down 방식

큰 문제부터 시작해서 작은 문제로 분할해 가는 과정이다. 메모리를 만들어놓고 계산된 값을 넣어주고, 계산된 값이 없으면 계산해 준다. 불필요한 계산을 줄여줄 수 있다.

import Foundation

var memory = Array(repeating: 0, count: 6)

func fib(_ n: Int) -> Int {
    if n <= 1 {
        memory[n] = 1
        return 1
    } else if memory[n] != 0 {
        return memory[n]
    } else {
        memory[n] = fib(n-1) + fib(n-2)
        return memory[n]
    }
}

print(fib(5)) // 8
print(memory) // [1, 1, 2, 3, 5, 8]

 

Bottom-Up 방식

다양한 방식으로 구현할 수 있겠지만 내가 사용한 방식은 아래와 같다. 우선 배열을 만들어 준 후 초기값을 넣어 준 후 배열을 완성해 준다. 그리고 저장된 메모리에서 n번째를 return 해주면 된다. 이렇게 불필요한 반복계산을 줄여줄 수 있다.

import Foundation

func fib(_ n: Int) -> Int {
    var memory = Array(repeating: 0, count: n+1)
    
    memory[0] = 1
    memory[1] = 1
    
    if n >= 2 {
        for i in 2...n {
            memory[i] = memory[i-1] + memory[i-2]
        }
    }
    
    return memory[n]
}

print(fib(5)) // 8

 

어떻게 보면 계산한 값을 재활용한다는 간단한 아이디어인데 이런 아이디어만으로도 효율적으로 문제를 해결할 수 있다는 것이 신기하고 재밌다.