1. BOJ_24416_알고리즘 수업 - 피보나치 수 1

let n = Int(readLine()!)!
// 메모이제이션 할 배열
var dp = [0, 1]

// 40까지 반복
for i in 2...40 {
    dp.append(dp[i-2] + dp[i-1])
}

// 아래 설명 참고
print(dp[n], n-2)

재귀 함수와 다이나믹 프로그래밍의 시간복잡도 차이를 실감나게 이해시키려는 문제인데,

우선 생각해보면 좋은 것이,

1. dp[3] 을 호출하는 것은 dp[2]+dp[1] 의 결과값으로 총 2번호출하게 된다.
2. dp[4] 는 dp[3]+dp[2] → dp[3] = 2번, dp[2] = 1 번 이었으니, 총 3번이 된다.
3. dp[5] 는 dp[4]+dp[3] → dp[4] = 3번, dp[3] = 2번 이었으니, 총 5번이다.

즉, 호출 횟수(n)가 결국 피보나치 수열의 n번째 요소와 동일하게 이루어지고 있다.

그럼 출력부분에서 dp[n] 을 그대로 출력하면 재귀 호출 횟수가 나타날 것이고,

다이나믹 프로그램 방식은 이미 이전 값들은 배열에 값이 있을테니 횟수는 단순하게 n-2 이다.

2. BOJ_9184_신나는 함수 실행

이미 주어진 점화식을 갖고 코드를 작성하는 문제로

이 문제를 해결하기 위해서는 2가지를 수행하면 된다.

1. 메모이제이션 할 배열 선택