1️⃣ 문제
2️⃣ 풀이 방법 및 코드
1️⃣ 처음 풀이한 코드
레벨2 맞아?, 너무 쉬운 거 아냐!??? 하면서 자신있게 제출했지만 테케 7~14번 다 시간초과 뜸.
알아보니 이 문제는 재귀로 풀 수 있는 문제가 아니라고 한다.
func fibonacci(_ n: Int) -> Int {
if n < 2 { return n }
else {
return fibonacci(n - 1) % 1234567 + fibonacci(n - 2) % 1234567
}
}
func solution(_ n:Int) -> Int {
return fibonacci(n) % 1234567
}
2️⃣ 최종 수정 코드
재귀로 유명한 피보나치라지만,
숫자가 크다면 중복된 계산을 할 수 있다는 단점이 있다.
이와 같은 문제점을 해결하기 위해, 중복된 계산을 하지 않고 계산된 값을 저장하고 참조할 수 있는 동적 프로그래밍으로 해결하였다.
func solution(_ n:Int) -> Int {
var f = [0, 1]
for i in 2...n {
f += [(f[i - 2] + f[i - 1]) % 1234567]
}
return f[n]
}