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