피보나치 메모이제이션

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

주어진 문제를 여러 개의 부분 문제로 나누어 푼 다음 그 결과들로 주어진 문제를 푼다.

분할정복과 매우 비슷하다. 그러나 둘 사이에는 결정적인 차이점이 있다. 분할 정복은 문제를 분할했을 때 겹치는 문제가 발생하지 않지만, DP는 겹치는 문제가 발생하기 때문에 메모이제이션이 필요하다.

디피는 자신보다 작은 부분문제 답을 모두 알면 이번 문제를 빨리 풀 수 있다. 이를 실제 구현 하려면 답을 저장하기 위해서 메모이제이션이 필요하다.

위에서 재귀호출과 반복문 을 사용해 피보나치 문제를 풀었는데 , 재귀호출 방법은

위에서 아래로 탑다운 방식이며,

반복문 방법은 아래에서 위로 바텀업 방식이다.

탑 다운 방식은 가독성이 좋고 본래 점화식을 이해하기 쉽다는 점이 있고,

바텀 업 방식은 함수를 별개로 호출할 필요가 없다는 점에서 시간과 메모리를 소량 더 절약 할 수 있다.

문제 풀이 접근 방식

1. dp[n] dp 테이블에 대한 정의. ex) dp(n)은 n번째 할 때
2. 점화식 세우기. ex) dp(n) = dp(n-1) *2  + dp(n-2)