🔗 문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/12945
✅ 풀이
코테 공부하다보면 단골 문제인 피보나치 수!
그냥 수를 찾는 것이 아니라 이번 문제는 1234567 로 나눈 나머지를 구하는 문제이다
⌨️ 첫번째 풀이
import Foundation
func solution(_ n:Int) -> Int {
return fi(n) % 1234567
}
func fi(_ num: Int) -> Int {
if num <= 1 {
return num
}
return fi(num - 1) + fi(num - 2)
}피보나치 수를 구할 때 여러방법이 있는데 그중 재귀함수로 풀어보고자 했다
역시 한번에 풀리지 않는다..
재귀함수로 푼 시간복잡도는 O(2^n) 이다
n 은 2 이상 100,000 이하인 수 이기 때문에 만약 100,000 이라면...
계산할 수가 없다..
이미 2^100 은 1.2676506002 * 10^30 이다..
입력 범위를 생각하지 않고 바로 코드를 작성했기 때문에 생겨난 일이다....
⌨️ 두번째 풀이
func solution(_ n:Int) -> Int {
var fibonacci = [0, 1]
for i in 2...n {
fibonacci.append((fibonacci[i - 2] + fibonacci[i - 1]) % 1234567)
}
return fibonacci[n]
}고민 고민 해보니 피보나치 수를 구할때 더욱 효율적인 방법이 있다고 했다!
바로 동적 계획법이다!
흔히 DP 라고 불리우는 알고리즘의 특징은 반복을 일으키지 않고 이러한 반복은 어딘가 저장해놓고 갖다 쓰기 때문에 더육 효율적이다
위에서 푼 재귀함수를 보면 계산을 이미했지만 또 계산을 하는 중복이 생겨난다
F(2) = F(0) + F(1) = 0 + 1 = 1
F(3) = F(1) + F(2) = 1 + 1 = 2
F(4) = F(2) + F(3) = 1 + 2 = 3
F(5) = F(3) + F(4) = 2 + 3 = 5
하지만 DP 로는 F(0), F(1), F(2) .. 등의 계산을 배열에 저장하여 필요할 때마다 꺼내쓰는 형태이기 때문에 효율적이고
다음과 같이 깔끔하게 시간초과 없이 통과했다!
요즘 DFS,BFS 보다 DP 유형 코테가 많이 나오는거 같은데 DP 를 많이 공부해야겠다....
