[알고리즘] 피보나치 수 풀이

🔍 문제 설명

---

피보나치 수는 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

입출력 예 설명

• 피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

✍️ 문제 풀이

---

1. 처음 작성한 코드

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

• 배열과 반복문을 활용하여 구현

2. 변수와 반복문 활용

func solution(_ n: Int) -> Int {
    if n == 0 { return 0 }
    
    var a = 0
    var b = 1
    
    for _ in 2...n {
        let temp = (a + b) % 1234567
        a = b
        b = temp
    }
    
    return b
}

• 배열 대신 변수 2개만 써서 더 최적화됨

3. 재귀 활용

func solution(_ n: Int) -> Int {
    var memo = [Int: Int]()
    
    func fibo(_ x: Int) -> Int {
        if x <= 1 { return x }
        if let cached = memo[x] { return cached }
        let value = (fibo(x - 1) + fibo(x - 2)) % 1234567
        memo[x] = value
        return value
    }
    
    return fibo(n)
}

4. 고차함수 활용

func solution(_ n: Int) -> Int {
    if n < 2 { return n }
    
    let result = (2...n).reduce((0, 1)) { prev, _ in
        ((prev.1), (prev.0 + prev.1) % 1234567)
    }
    return result.1
}

• 깔끔하게 1줄로 피보나치 구현 가능

💡 % 1234567 나머지 연산이 필요한 이유

• 지수가 증가함에 따라 값이 기하급수적으로 커져서 오버플로우 발생
• 예: F(50) = 12,586,269,025 (약 120억 이상)
• 이런 큰 수는 Swift의 Int 범위를 초과할 수 있음
  → 따라서 계산 중간마다 나머지 처리 필요

👨🏻‍💻 튜터님 코드

• 추가 예정

💡 문제 출처
https://school.programmers.co.kr/learn/courses/30/lessons/12945