import Foundation let T = Int(readLine()!)! for _ in 0.. Int { var cache: [Int] = [1, 2, 4] guard n > 2 else { return n } for num in 3...n { cache.append(cache[num - 3] + cache[num - 2] + cache[num - 1]) } return cache[n-1] }

이 게시글은 개인적인 공부를 위해 작성된 게시물입니다. 이 글의 모든 출처는 https://babbab2.tistory.com/100 입니다. 동적 계획법 상향식 접근법으로 가장 작은 부분의 해답을 구한 후, 이를 저장하여 저장한 값을 이용해 상위 문제를 풀어가는 방법 동적 계획의 핵심은 Memoization(메모이제이션)이라는 기법인데 설명은 아래와 같습니다. 메모이제이션 동일한 계산을 반복해야할 때, 이전에 계산한 값을 메모리에 저장한 후 반복수행을 제거하여 프로그램 실행속도를 빠르게 하는 기법 피보나치 수열로 이해하기 0, 1, 2, 3, 5, 8, 13 ... 이런식으로 가장 처음 0, 1을 제외하고 내 앞의 두 놈을 더해서 나를 만드는 것이 피보나치 수열입니다. 재귀함수를 이용한 구현 func ..