import Foundation
var input = Int(readLine()!)!
var arr = Array(repeating: -1, count: input + 1)
func fibo(n: Int) -> Int{
// base case
if n == 0 {
return 0
}
if n == 1 {
return 1
}
// 계산된 적이 있는 경우 바로 리턴
if arr[n] != -1 {
return arr[n]
}
// 아니면 계산하고 값을 저장한뒤 리턴
arr[n] = fibo(n-2) + fibo(n-1)
return arr[n]
}
print(fibo(n: input))
미리 배열을 -1로 모두 초기화 한뒤,
계산한적이 있는지 확인 후 계산된 적이 있다면 추가 재귀 호출 없이 그 값을 바로 리턴하고, 계산된 적이 없다면 지금 계산해서 배열에 그 값을 저장해 다음번에 호출되면 바로 가져다 쓸 수 있도록 한다.
import Foundation
var input = Int(readLine()!)!
var arr = Array(repeating: 0, count: input + 1)
arr[1] = 1
for i in 2..<input {
arr[i] = arr[i-1] + arr[i-2]
}
print(fibo(n: input))
위 코드를 보면 재귀 호출 없이 반복문으로 구현하고 있다.
import Foundation
var input = Int(readLine()!)!
var arr = Array(repeating: 0, count: input + 3)
arr[1] = 1
for i in 0..<input {
arr[i+2] += arr[i]
arr[i+1] += arr[i]
}
print(fibo(n: input))
좀더 코드를 비틀면 이런 식으로도 구현 가능하다.
주어진 문제를 여러 개의 부분 문제로 나누어 푼 다음 그 결과들로 주어진 문제를 푼다.
분할정복과 매우 비슷하다. 그러나 둘 사이에는 결정적인 차이점이 있다. 분할 정복은 문제를 분할했을 때 겹치는 문제가 발생하지 않지만, DP는 겹치는 문제가 발생하기 때문에 메모이제이션이 필요하다.
디피는 자신보다 작은 부분문제 답을 모두 알면 이번 문제를 빨리 풀 수 있다. 이를 실제 구현 하려면 답을 저장하기 위해서 메모이제이션이 필요하다.
위에서 재귀호출과 반복문 을 사용해 피보나치 문제를 풀었는데 , 재귀호출 방법은
위에서 아래로 탑다운 방식이며,
반복문 방법은 아래에서 위로 바텀업 방식이다.
탑 다운 방식은 가독성이 좋고 본래 점화식을 이해하기 쉽다는 점이 있고,
바텀 업 방식은 함수를 별개로 호출할 필요가 없다는 점에서 시간과 메모리를 소량 더 절약 할 수 있다.
1. dp[n] dp 테이블에 대한 정의. ex) dp(n)은 n번째 할 때
2. 점화식 세우기. ex) dp(n) = dp(n-1) *2 + dp(n-2)