[프로그래머스] 피보나치 수

https://programmers.co.kr/learn/courses/30/lessons/12945?language=swift 

코딩테스트 연습 - 피보나치 수

 

지금까지 배워본 피보나치 구현 방법은 총 두 개가 있었다. 

 

바로  재귀와 DP !

// 재귀
func fibo(_ n: Int) -> Int {
	if n == 0 { return 0 }
	if n == 1 { return 1 }    
	return fibo(n-1) + fibo(n-2)
}

// Dynamic Programming
func fibo(_ n: Int) -> Int {
    var result = [0,1]
    for i in 2...n {
        result.append(result[i - 1] + result[i - 2])
    }
    return result[n]
}

피보나치를 재귀로 구현하는 경우 특정 수 이상 부터는 재귀의 깊이가 깊어지기에 시간적으로 비효율적이게 된다. 

그리하여 효율성을 따진다면 DP를 이용하는게 더 유리하다. 

 

해당 문제에서도 DP를 이용하여야 하는데, n의 입력이 100,000까지라는 것을 함께 고려해줘야 한다. 

반환해야 할 답은 1234567로 나눈 나머지 값이기 때문에, dp를 구하는 과정 중에 미리 나누어 계산이 필요한 수를 작게 유지한다.  

그러면 계속 작은 숫자로 값들로 채워나갈 수 있기에 효율성에 무리가 없게 된다. 

 

func solution(_ n:Int) -> Int {
    return fibo(n) % 1234567
}

func fibo(_ n: Int) -> Int {
    var res = [0,1]
    for i in 2...n {
        res.append(res[i - 1] % 1234567 + res[i - 2] % 1234567)
    }
    return res[n]
}

 

기존 DP에서 얼마나 더 효율적으로 코드를 구성할 수 있는지 보고자 한 것 같다. 

수학적인 개념도 같이 들어간 느낌.

 

큰 입력이 들어오는 것을 고려하여 수를 줄여주는 방법을 다각도로 고민해볼 필요가 있을 것 같다. 

끄읕