[프로그래머스] Swift - 피보나치 수 (LV.2)

👆문제풀러 가기👆

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

• 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

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

 

제한사항

• n은 2 이상 100,000 이하인 자연수입니다.

 

입출력 예제

n	return
3	2
5	5

 

풀이 [ 메모리: 16.3mb, 최대시간:  3.06ms ] 

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

문제를 받고 생각한 것.

1. 피보나치 수열 == 재귀(?)
2. 하지만 swift에서는 재귀함수를 호출할 수 있는 횟수가 제한되어 있다.
   (제한사항에서 n의 최댓값이 100,000이기에, 최대 10만번 호출될 수 있어야 한다.)
3. 따라서 반복문으로 해결해야된다고 판단했고, 식은 위와 같다.

 

Swift에서 재귀함수는 몇번이나 돌아갈 수 있을까?

이는 곧 스택이 얼마나 쌓일 수 있는가? 와 같은 질문이 된다.

함수는 동일하게 피보나치 수열을 재귀함수의 형태로 예제를 만들었다.

 

테스트 환경: Xcode

예제로 입력한 값: 10, 40~ 50, 100, 100000

 

결론적으로

• 1초 이내 출력: 40이하
• 10초 이내 출력: 45이하
• 50부터는 상당한 시간이 소요되었다.

피보나치 재귀 함수 처리시간 확인

하지만 위의 반복문 코드로 동일하게 하면,

Int 최댓값을 넘기는 overflow 외에는 10,000,000까지 2초 이내에 처리가 가능했다.

 

확실히 스택 영역에 함수가 생성, 삭제되는 과정이 시간복잡도를 상당히 높이는 것으로 보였고,

재귀함수는 현실적으로 40회 이하로 처리하는 것이 한계로 보였다. 물론 재귀 안의 재귀를 2회 호출하는 방식이기에 단일 호출을 하는 재귀함수를 새롭게 만들어봤다.

단일 재귀함수 최대 Depth

코드는 1씩 증가하는 재귀함수이고, 단순히 종료시점을 알기 위해 n의 최대값을 설정했다.

약 174,000번의 스택이 쌓일 수 있으나, 그 이상 쌓이면 Error가 발생하며 강제종료되었다.

아마도 스택오버플로우로 추측된다.

 

즉 재귀함수 내에서 몇 개의 재귀함수가 실행되는가에 따라 최대 실행횟수가 달라지며,

단일 재귀함수를 사용할 때에는 174,000회, 2^n의 재귀함수를 실행할 때에는 40회 정도가 최대라고 보는 게 좋을 것 같다.